Computational complexity of matrix multiplication: Difference between revisions

Revision as of 14:45, 3 September 2023

Revision as of 17:45, 8 November 2023

Line 1:

{{Short description|Algorithmic runtime requirements for matrix multiplication}}

{{unsolved|computer science|What is the fastest algorithm for matrix multiplication?}}

In [[theoretical computer science]], the '''computational complexity of matrix multiplication''' dictates [[Analysis of algorithms|how quickly]] the operation of [[matrix multiplication]] can be performed. [[Matrix multiplication algorithm]]s are a central subroutine in theoretical and [[numerical algorithm|numerical]] algorithms for [[numerical linear algebra]] and [[optimization]], so finding the rightfastest amountalgorithm offor timematrix it should takemultiplication is of major practical relevance.

Directly applying the mathematical definition of matrix multiplication gives an algorithm that requires {{math|''n''³}} [[Field (mathematics)|field]] operations to multiply two {{math|''n'' × ''n''}} matrices over that field ({{math|Θ(''n''³)}} in [[big O notation]]). Surprisingly, algorithms exist that provide better running times than this straightforward "schoolbook algorithm". The first to be discovered was [[Strassen algorithm|Strassen's algorithm]], devised by [[Volker Strassen]] in 1969 and often referred to as "fast matrix multiplication".<ref name="strassen69">