Matrix multiplication algorithm
Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).
- Comment
- enBecause matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).
- Depiction
- Has abstract
- enBecause matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network). Directly applying the mathematical definition of matrix multiplication gives an algorithm that takes time on the order of n3 field operations to multiply two n × n matrices over that field (Θ(n3) in big O notation). Better asymptotic bounds on the time required to multiply matrices have been known since the Strassen's algorithm in the 1960s, but the optimal time (that is, the computational complexity of matrix multiplication) remains unknown. 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 algorithm is a galactic algorithm because of the large constants and cannot be realized practically.
- Is primary topic of
- Matrix multiplication algorithm
- Label
- enMatrix multiplication algorithm
- Link from a Wikipage to an external page
- github.com/flame/how-to-optimize-gemm
- Link from a Wikipage to another Wikipage
- Analysis of algorithms
- Asymptotic notation
- Basic Linear Algebra Subprograms
- Big O notation
- Block matrix
- Cache-oblivious algorithm
- Cannon's algorithm
- Category:Articles with example pseudocode
- Category:Matrix multiplication algorithms
- Category:Matrix theory
- Category:Numerical linear algebra
- Communication-avoiding algorithm
- Computational complexity of mathematical operations
- Computational complexity of matrix multiplication
- CPU cache
- Critical path length
- CYK algorithm
- DeepMind
- Distributed computing
- Divide-and-conquer algorithm
- Don Coppersmith
- Field (mathematics)
- File:Block matrix multiplication.svg
- File:MatrixMultComplexity svg.svg
- File:Matrix multiplication on a cross-wire two-dimensional array.png
- File:Row and column major order.svg
- Finite field
- Fork–join model
- Freivalds' algorithm
- Galactic algorithm
- GF(2)
- Graph (graph theory)
- Locality of reference
- Loop tiling
- Loop unrolling
- MapReduce
- Master theorem (analysis of algorithms)
- Matrix chain multiplication
- Matrix multiplication
- Mesh networking
- Method of Four Russians
- Monte Carlo algorithm
- Multiprogramming
- Neural network
- Numerical algorithm
- Numerical stability
- Parallel algorithm
- Parallel computing
- Pattern recognition
- Pseudocode
- Recursion
- Row- and column-major order
- Scalar multiplication
- Scientific computing
- Shared-memory multiprocessor
- Shmuel Winograd
- Sparse matrix–vector multiplication
- Speedup
- Strassen algorithm
- Theoretical computer science
- Time complexity
- Virginia Vassilevska Williams
- Volker Strassen
- SameAs
- Algoritam množenja matrica
- fs4i
- m.010prbtk
- m.012ngj92
- Matrix multiplication algorithm
- Q17082383
- Алгоритм перемножування матриць
- Алгоритм умножения матриц
- الگوریتمهای ضرب ماتریس
- Subject
- Category:Articles with example pseudocode
- Category:Matrix multiplication algorithms
- Category:Matrix theory
- Category:Numerical linear algebra
- Thumbnail
- WasDerivedFrom
- Matrix multiplication algorithm?oldid=1124066606&ns=0
- WikiPageLength
- 33776
- Wikipage page ID
- 21450030
- Wikipage revision ID
- 1124066606
- WikiPageUsesTemplate
- Template:=
- Template:As of
- Template:Cite journal
- Template:Framebox
- Template:Frame-footer
- Template:Further
- Template:Math
- Template:Mvar
- Template:Numerical linear algebra
- Template:R
- Template:Radic
- Template:Refbegin
- Template:Refend
- Template:Reflist
- Template:Rp
- Template:Sfrac
- Template:Short description
- Template:Sqrt
