Computational complexity of matrix multiplication
In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the right amount of time it should take is of major practical relevance.
- Comment
- enIn theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the right amount of time it should take is of major practical relevance.
- Depiction
- Has abstract
- enIn theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the right amount of time it should take is of major practical relevance. Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires n3 field operations to multiply two n × n matrices over that field (Θ(n3) in big O notation). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". The first to be discovered was Strassen's algorithm, devised by Volker Strassen in 1969 and often referred to as "fast matrix multiplication". The optimal number of field operations needed to multiply two square n × n matrices up to constant factors is still unknown. This is a major open question in theoretical computer science. As of October 2022, the best announced bound on the asymptotic complexity of a matrix multiplication algorithm is O(n2.37188) time, given by Duan, Wu and Zhou announced in a preprint. This improves on the bound of O(n2.3728596) time, given by Josh Alman and Virginia Vassilevska Williams. However, this and similar improvements to Strassen are not used in practice, because they are galactic algorithms: the constant coefficient hidden by the Big O notation is so large that they are only worthwhile for matrices that are too large to handle on present-day computers.
- Is primary topic of
- Computational complexity of matrix multiplication
- Label
- enComputational complexity of matrix multiplication
- Link from a Wikipage to an external page
- fmm.univ-lille.fr/
- Link from a Wikipage to another Wikipage
- Abelian group
- Algorithm
- Analysis of algorithms
- Arithmetic circuit complexity
- Balázs Szegedy
- Basic Linear Algebra Subprograms
- Big O notation
- Block matrix
- Category:Computational complexity theory
- Category:Computer arithmetic algorithms
- Category:Matrix theory
- Category:Unsolved problems in computer science
- Chris Umans
- Computational complexity
- Computational complexity of mathematical operations
- CYK algorithm
- Determinant
- Divide-and-conquer algorithm
- Don Coppersmith
- Duality (optimization)
- Field (mathematics)
- File:MatrixMultComplexity svg.svg
- Finite field
- Floating point
- Freivalds' algorithm
- Galactic algorithm
- Gaussian elimination
- Group theory
- Henry Cohn
- Hermite normal form
- LU decomposition
- Matrix chain multiplication
- Matrix inversion
- Matrix multiplication
- Matrix multiplication algorithm
- Model of computation
- Monte Carlo algorithm
- Numerical algorithm
- Numerical linear algebra
- Numerical stability
- Optimization
- Ran Raz
- Robert Kleinberg
- Shmuel Winograd
- Smith normal form
- Sparse matrix–vector multiplication
- Strassen algorithm
- Sunflower conjecture
- Theoretical computer science
- Time complexity
- Triple product property
- Virginia Vassilevska Williams
- Volker Strassen
- Worst-case complexity
- Wreath product
- SameAs
- FuZW8
- Q106996431
- Subject
- Category:Computational complexity theory
- Category:Computer arithmetic algorithms
- Category:Matrix theory
- Category:Unsolved problems in computer science
- Thumbnail
- WasDerivedFrom
- Computational complexity of matrix multiplication?oldid=1121125201&ns=0
- WikiPageLength
- 33132
- Wikipage page ID
- 24107400
- Wikipage revision ID
- 1121125201
- WikiPageUsesTemplate
- Template:=
- Template:As of
- Template:Citation needed
- Template:Cite journal
- Template:For
- Template:Further
- Template:Main
- Template:Math
- Template:Mvar
- Template:Reflist
- Template:Short description
- Template:Tmath
- Template:Unsolved
