An introduction to the computational complexity of matrix multiplication

Complexity of computation (including implicit computational complexity) (03D15) Basic linear algebra (15A99) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

scientific article; zbMATH DE number 727424
scientific article; zbMATH DE number 4088834
Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
Powers of tensors and fast matrix multiplication
On obtaining upper bounds on the complexity of matrix multiplication

Cites work

\(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
A \(2\mathbf{n}^2-\log_2(\mathbf{n})-1\) lower bound for the border rank of matrix multiplication
A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
A note on border rank
Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
Fast Output-Sensitive Matrix Multiplication
Gaussian elimination is not optimal
scientific article; zbMATH DE number 5968745 (Why is no real title available?)
scientific article; zbMATH DE number 976329 (Why is no real title available?)
scientific article; zbMATH DE number 6159604 (Why is no real title available?)
Intersection Theorems for Systems of Sets
Lower bounds for the multiplicative complexity of matrix multiplication
Matrix multiplication via arithmetic progressions
Multiplying matrices faster than coppersmith-winograd
New lower bounds for the border rank of matrix multiplication
New lower bounds for the rank of matrix multiplication
On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
On multiplication of 2 2 matrices
On sunflowers and matrix multiplication
On the Asymptotic Complexity of Matrix Multiplication
On the complexity of computing bilinear forms with \(\{0,1\}\) constants
On the complexity of some algorithms of matrix multiplication
On the complexity of the multiplication of matrices of small formats
On the geometry of border rank decompositions for matrix multiplication and other tensors with symmetry
Partial and Total Matrix Multiplication
Powers of tensors and fast matrix multiplication
Rank and optimal computation of generic tensors
Relations between exact and approximate bilinear algorithms. Applications
Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
Sur le calcul des produits de matrices. (Calculation of the product of matrices.)
Tensor rank is NP-complete
The bilinear complexity and practical algorithms for matrix multiplication
The border rank of the multiplication of 2\times 2 matrices is seven
The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
Typical tensorial rank

Cited in

(6)

Complexities of special matrix multiplication problems
The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented algorithms
Certifying the global optimality of quartic minimization over the sphere
Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
scientific article; zbMATH DE number 727424 (Why is no real title available?)
Discovering faster matrix multiplication algorithms with reinforcement learning

This page was built for publication: An introduction to the computational complexity of matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2176822)