On the complexity of the multiplication of matrices of small formats

DOI10.1016/S0885-064X(02)00007-9zbMath1026.68062MaRDI QIDQ1394936

Markus Bläser

Publication date: 25 June 2003

Published in: Journal of Complexity (Search for Journal in Brave)

zbMATH Keywords

matrix multiplication

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

A General Theory of Singular Values with Applications to Signal Denoising, Unnamed Item, Tensor Rank is Hard to Approximate, On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry, An adaptive prefix-assignment technique for symmetry reduction, Unnamed Item, Flip Graphs for Matrix Multiplication, A normal form for matrix multiplication schemes, On the exact and approximate bilinear complexities of multiplication of \(4\times 2\) and \(2\times 2\) matrices, Optimization techniques for small matrix multiplication, Semisimple algebras of almost minimal rank over the reals, The geometry of rank decompositions of matrix multiplication. II: \(3 \times 3\) matrices, Two bilinear \((3\times3)\)-matrix multiplication algorithms of complexity 25, Equivalent polyadic decompositions of matrix multiplication tensors, Fast commutative matrix algorithms, An introduction to the computational complexity of matrix multiplication, On bilinear complexity of multiplying \(2 \times 2\)-matrix by \(2 \times m\)-matrix over finite field, New ways to multiply \(3 \times 3\)-matrices, Improved method for finding optimal formulas for bilinear maps in a finite field, A bilinear algorithm of length \(22\) for approximate multiplication of \(2\times 7\) and \(7\times 2\) matrices, Tensor surgery and tensor rank, On the inequivalence of bilinear algorithms for \(3\times 3\) matrix multiplication, Improving the Numerical Stability of Fast Matrix Multiplication, The bilinear complexity and practical algorithms for matrix multiplication, Group-Theoretic Lower Bounds for the Complexity of Matrix Multiplication, Geometry and the complexity of matrix multiplication

Cites Work

• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Lectures on the complexity of bilinear problems
• On varieties of optimal algorithms for the computation of bilinear mappings. I. The isotropy group of a bilinear mapping
• On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for \(2\times 2\)-matrix multiplication
• On the algorithmic complexity of associative algebras
• On the optimal evaluation of a set of bilinear forms
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Lower bounds for the multiplicative complexity of matrix multiplication
• Gaussian elimination is not optimal
• On multiplication of 2 \(\times\) 2 matrices
• Relative bilinear complexity and matrix multiplication.
• Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix Multiplication
• Partial and Total Matrix Multiplication
• A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
• On Winograd's Algorithm for Inner Products
• On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
• Lower bounds for the bilinear complexity of associative algebras