New ways to multiply \(3 \times 3\)-matrices (Q2229749): Difference between revisions

The well-known Strassen algorithm for multiplying two \(2 \times 2\) matrices uses a minimum number of seven multiplications to produce certain `auxiliary' quantities which are then combined using only addition and subtraction to obtain the final product matrix. This paper utilizes a generalization of this result for \(3 \times 3\) matrices in the form of the Brent equations, which involves making an ansatz for the coefficients of various linear combinations of a prescribed number of multiplications (in this case, 23), enforcing the necessary conditions imposed by matrix multiplication, and then solving the resulting system of polynomial equations to be able to obtain the terms in the product matrix. Computing Gröbner bases would in principle allow one to achieve this goal. Nevertheless, it is unrealistic from a computational point of view. In this context the authors propose a more streamlined approach, where the Brent equations are viewed as equations for \(\mathbb{Z}_2\): its elements are truth values that are combined via the operations of exclusive or (additions) and conjunction (multiplications). Encoding the problem as propositional formulas allows one to process the equations via SAT solvers. While this kind of encoding may produce incredibly difficult SAT problems, the authors note that adding certain constraints can simplify the encoding. Accordingly, they present four such streamlining procedures and note that performance analytics can be found in their other paper [\textit{M. J. H. Heule} et al., Lect. Notes Comput. Sci. 11628, 155--163 (2019; Zbl 1441.68225)]. After determining solutions, the next steps involve the elimination of redundancies and some simplifications. For the former, an algorithm to identify equivalent solutions is proposed, with the authors acknowledging a more sophisticated version in [\textit{G. O. Berger} et al., J. Comput. Appl. Math. 406, Article ID 113941, 17 p. (2022; Zbl 1486.15030)]. For the latter, a weight is introduced as an indicator of a particular solution's effectiveness in identifying new, non-equivalent schemes. Minimizing such a weight allows for some schemes to be replaced with a `better' (but still equivalent) one. These two procedures enable the reduction of roughly 300,000 solutions (i.e., ways to multiply the matrices) to 17,000 distinct multiplication schemes modulo equivalence (over \(\mathbb{Z}_2\)). The authors also propose a system-solving procedure that would work in any coefficient ring by applying a `lifting' to recover solutions over \(\mathbb{Z}\) (or \(\mathbb{Q}\)) that may have been lost in using the coefficient field \(\mathbb{Z}_2\). Lastly, the nonlinear system of equations from the original set of Brent equations can be converted into a linear one by introducing fresh parameters to obtain families of schemes. For several of the families with 17 parameters it is reported that the parameters can be shown to be linearly independent. The authors conclude that the set of these 17,000 schemes form a manifold of at least dimension 17. It is still unknown whether or not a scheme of 22 multiplications (or less) exists when the coefficients are restricted to non-commutative domains.