Abstract:
Finding nontrivial solutions of trilinear Brent equations corresponds to the construction of asymptotically fast matrix multiplication algorithms and is considered as an important but generally very hard computational problem. Based on symmetries of matrix multiplication tensor, some new parametrizations of Brent equations are proposed which admit for several times reduction in the number of unknowns and equations. The arising equations are solved numerically over complex numbers using a specialized derivative-free nonlinear least squares solver. For the resulting fast matrix multiplication algorithms many known values of rank are reproduced and even improved. In particular, an algorithm for the multiplication of 4th order matrices in 48 bilinear multiplications is found.
Key words:Brent equations, fast matrix multiplication, Strassen algorithm, nonlinear least squares problem.
Cited by