An introduction to the computational complexity of matrix multiplication
From MaRDI portal
Publication:2176822
DOI10.1007/s40305-019-00280-xzbMath1463.90252OpenAlexW2992295113WikidataQ126636991 ScholiaQ126636991MaRDI QIDQ2176822
Jie Wang, Yan Li, Zheng-Hai Huang, Sheng-Long Hu
Publication date: 5 May 2020
Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s40305-019-00280-x
Abstract computational complexity for mathematical programming problems (90C60) Complexity of computation (including implicit computational complexity) (03D15) Basic linear algebra (15A99)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On sunflowers and matrix multiplication
- The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
- A note on border rank
- Matrix multiplication via arithmetic progressions
- Rank and optimal computation of generic tensors
- Typical tensorial rank
- On the complexity of computing bilinear forms with \(\{0,1\}\) constants
- Relations between exact and approximate bilinear algorithms. Applications
- \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
- On the complexity of the multiplication of matrices of small formats
- Lower bounds for the multiplicative complexity of matrix multiplication
- Gaussian elimination is not optimal
- On multiplication of 2 \(\times\) 2 matrices
- Sur le calcul des produits de matrices. (Calculation of the product of matrices.)
- The bilinear complexity and practical algorithms for matrix multiplication
- New lower bounds for the border rank of matrix multiplication
- Tensor rank is NP-complete
- Intersection Theorems for Systems of Sets
- The border rank of the multiplication of $2\times 2$ matrices is seven
- Powers of tensors and fast matrix multiplication
- Fast Output-Sensitive Matrix Multiplication
- On the complexity of some algorithms of matrix multiplication
- Partial and Total Matrix Multiplication
- Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
- On the Asymptotic Complexity of Matrix Multiplication
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
- A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications
- A $2{\mathbf{n}}^2-{\text{log}}_2({\mathbf{n}})-1$ lower bound for the border rank of matrix multiplication
- On the Geometry of Border Rank Decompositions for Matrix Multiplication and Other Tensors with Symmetry
- Multiplying matrices faster than coppersmith-winograd
- New Lower Bounds for the Rank of Matrix Multiplication
- On Minimizing the Number of Multiplications Necessary for Matrix Multiplication
This page was built for publication: An introduction to the computational complexity of matrix multiplication
