A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications

DOI10.1090/S0002-9904-1976-13988-2zbMath0322.65021WikidataQ114094111 ScholiaQ114094111MaRDI QIDQ4085178

Julian Laderman

Publication date: 1976

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Mathematics Subject Classification ID

Related Items (35)

Fast algorithms for the basic operation of cellular methods of linear algebra ⋮ The trace invariant and matrix inversion ⋮ Fast commutative matrix algorithms ⋮ Compressible FHE with applications to PIR ⋮ An introduction to the computational complexity of matrix multiplication ⋮ The bilinear complexity and practical algorithms for matrix multiplication ⋮ Unnamed Item ⋮ On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry ⋮ Geometry and the complexity of matrix multiplication ⋮ On the complexity of the multiplication of matrices of small formats ⋮ Towards Practical Fast Matrix Multiplication based on Trilinear Aggregation ⋮ Flip Graphs for Matrix Multiplication ⋮ Pebbling Game and Alternative Basis for High Performance Matrix Multiplication ⋮ On bilinear complexity of multiplying \(2 \times 2\)-matrix by \(2 \times m\)-matrix over finite field ⋮ A normal form for matrix multiplication schemes ⋮ Recursive cellular methods of matrix multiplication ⋮ On the inequivalence of bilinear algorithms for \(3\times 3\) matrix multiplication ⋮ New fast hybrid matrix multiplication algorithms ⋮ New cellular methods for matrix multiplication ⋮ A unified cellular method for matrix multiplication ⋮ On the exact and approximate bilinear complexities of multiplication of \(4\times 2\) and \(2\times 2\) matrices ⋮ New ways to multiply \(3 \times 3\)-matrices ⋮ An ultrafast cellular method for matrix multiplication ⋮ The geometry of rank decompositions of matrix multiplication. II: \(3 \times 3\) matrices ⋮ Tensor Rank is Hard to Approximate ⋮ Numerical CP decomposition of some difficult tensors ⋮ Optimization techniques for small matrix multiplication ⋮ Improved method for finding optimal formulas for bilinear maps in a finite field ⋮ A new fast recursive matrix multiplication algorithm ⋮ An adaptive prefix-assignment technique for symmetry reduction ⋮ Two bilinear \((3\times3)\)-matrix multiplication algorithms of complexity 25 ⋮ A noncommutative algorithm for multiplying 5 X 5 matrices using 103 multiplications ⋮ A fast recursive algorithm for multiplying matrices of order \(n = 3^q\) \((q > 1)\) ⋮ Equivalent polyadic decompositions of matrix multiplication tensors ⋮ A bilinear algorithm of length \(22\) for approximate multiplication of \(2\times 7\) and \(7\times 2\) matrices

Cites Work

• Gaussian elimination is not optimal
• Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
• On multiplication of 2 \(\times\) 2 matrices
• Sur le calcul des produits de matrices. (Calculation of the product of matrices.)
• Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
• On the Number of Multiplications Required for Matrix Multiplication
• A New Algorithm for Inner Product
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication

This page was built for publication: A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications