Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Computational complexity of matrix multiplication
open-in-new
Unsolved problem in computer science: What is the fastest algorithm for matrix multiplication? <a href="/facts/List_of_unsolved_problems_in_computer_science/QySnBJ5E">(more unsolved problems in computer science)</a> <p>In <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, the computational complexity of matrix multiplication dictates <a href="/facts/Analysis_of_algorithms/pStoBgBn">how quickly</a> the operation of <a href="/facts/Matrix_multiplication/lYDB6Ro2">matrix multiplication</a> can be performed. <a href="/facts/Matrix_multiplication_algorithm/VrYWxfDt">Matrix multiplication algorithms</a> are a central subroutine in theoretical and <a href="/facts/Numerical_algorithm/QT9cYa9z">numerical</a> algorithms for <a href="/facts/Numerical_linear_algebra/jnS6Tteb">numerical linear algebra</a> and <a href="/facts/Optimization/oRn8Iv5I">optimization</a>, so finding the fastest algorithm for matrix multiplication is of major practical relevance. </p><p>Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires <i>n</i>3 <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> operations to multiply two <i>n</i> × <i>n</i> matrices over that field (Θ(<i>n</i>3) in <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a>). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". The first to be discovered was <a href="/facts/Strassen_algorithm/rrIGRSNp">Strassen's algorithm</a>, devised by <a href="/facts/Volker_Strassen/YrULq6nE">Volker Strassen</a> in 1969 and often referred to as "fast matrix multiplication". The optimal number of field operations needed to multiply two square <i>n</i> × <i>n</i> matrices <a href="/facts/Big_O_notation/weFFjSWg">up to constant factors</a> is still unknown. This is a major open question in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>. </p><p>As of January 2024<a href="https://en.wikipedia.org/w/index.php?title=Computational_complexity_of_matrix_multiplication&action=edit">[update]</a>, the best bound on the <a href="/facts/Time_complexity/77T62gmf">asymptotic complexity</a> of a matrix multiplication algorithm is O(<i>n</i>2.371339). However, this and similar improvements to Strassen are not used in practice, because they are <a href="/facts/Galactic_algorithm/Q17Y5kP8">galactic algorithms</a>: the constant coefficient hidden by the <a href="/facts/Big_O_notation/weFFjSWg">big O notation</a> is so large that they are only worthwhile for matrices that are too large to handle on present-day computers. </p>