User:Fawly/Computational complexity of matrix multiplication: Difference between revisions

Revision as of 21:21, 23 May 2021

Revision as of 21:51, 23 May 2021

Line 36:

== Matrix multiplication ==

{{Main|Matrix multiplication}}

If ''A'', ''B'' are {{math|''n'' × ''n''}} matrices over a field, then their product ''AB'' is also an {{math|''n'' × ''n''}} matrix over that field, defined entrywise as

:<math>

(AB)_{ij} = \sum_{k = 1}^n A_{ik} B_{kj}.

</math>

=== Schoolbook algorithm ===

{{For|implementation techniques (in particular parallel and distributed algorithms)|Matrix multiplication algorithm}}

The simplest approach to computing the product of two {{math|''n'' × ''n''}} matrices ''A'' and ''B'' is to compute the arithmetic expressions coming from the definition of matrix multiplication. In pseudocode:

The matrix multiplication [[algorithm]] that results of the definition requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications of scalars and {{tmath|(n-1)n^2}} additions for computing the product of two square {{math|''n''×''n''}} matrices. Its [[computational complexity]] is therefore {{tmath|O(n^3)}}, in a [[model of computation]] for which the scalar operations require a constant time (in practice, this is the case for [[floating point]] numbers, but not for integers).

initialize C to be an n by n matrix of all zeros

for i from 1 to n:

for j from 1 to n:

for k from 1 to n:

C[i][j] = C[i][j] + A[i][k]*B[k][j]

return C

The matrix multiplicationThis [[algorithm]] that results of the definition requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications of scalars and {{tmath|(n-1)n^2}} additions for computing the product of two square {{math|''n''×''n''}} matrices. Its [[computational complexity]] is therefore {{tmath|O(n^3)}}, in a [[model of computation]] forwhere whichfield theoperations scalar(addition operationsand requiremultiplication) atake constant time (in practice, this is the case for [[floating point]] numbers, but not necessarily for integers).

=== Strassen's algorithm ===