New ways to multiply 3 × 3-matrices. (May 2021)

• Record Type: Journal Article
• Authors: Heule, Marijn J.H.; Kauers, Manuel; Seidl, Martina
• Is Part Of: Journal of symbolic computation. Volume 104(2021)
• Page Start: 899
• Page End: 916
• Publication Date: 2021-05
• Subjects: Bilinear complexity -- Matrix multiplication -- Laderman's algorithm -- SAT solving; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2020.10.003
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: It is known since the 1970s that no more than 23 multiplications are required for computing the product of two 3 × 3 -matrices. For non-commutative coefficient rings, it is not known whether it can also be done with fewer multiplications. However, there are several mutually inequivalent ways of doing the job with 23 multiplications. In this article, we extend this list considerably by providing more than 17, 000 new and mutually inequivalent schemes for multiplying 3 × 3 -matrices using 23 multiplications. Moreover, we show that the set of all these schemes is a manifold of dimension at least 17.