Computational complexity of matrix multiplication: Difference between revisions

Revision as of 23:49, 24 May 2021

Revision as of 22:29, 25 May 2021

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]], anthe active'''computational areacomplexity of researchmatrix ismultiplication''' determiningdictates [[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 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 {{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">