Finding Complex-Valued Solutions of Brent Equations Using Nonlinear Least Squares
Author:
- 1 September 2024
- journal article
- research article
- Published by Pleiades Publishing Ltd in Computational Mathematics and Mathematical Physics
- Vol. 64 (9) , 1881-1891
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.Keywords
This publication has 14 references indexed in Scilit:
- Discovering faster matrix multiplication algorithms with reinforcement learningNature, 2022
- Equivalent polyadic decompositions of matrix multiplication tensorsJournal of Computational and Applied Mathematics, 2022
- Optimization and Applications2021
- The geometry of rank decompositions of matrix multiplication II: 3 × 3 matricesJournal of Pure and Applied Algebra, 2019
- The bilinear complexity and practical algorithms for matrix multiplicationComputational Mathematics and Mathematical Physics, 2013
- Minimization methods for approximating tensors and their comparisonComputational Mathematics and Mathematical Physics, 2006
- On a Class of Nonlinear Equation Solvers Based on the Residual Norm Reduction over a Sequence of Affine SubspacesSIAM Journal on Scientific Computing, 1995
- A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplicationsBulletin of the American Mathematical Society, 1976
- On Minimizing the Number of Multiplications Necessary for Matrix MultiplicationSIAM Journal on Applied Mathematics, 1971
- Gaussian elimination is not optimalNumerische Mathematik, 1969