Computational complexity of matrix multiplication: Difference between revisions

Revision as of 23:58, 23 May 2021

Revision as of 02:37, 24 May 2021

Line 60:

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:

'''input''' is ''A'' and ''B'', both ''n'' by ''n'' matrices

'''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'']

'''output''' ''C'' (as A*B)

This [[algorithm]] requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications of scalars and {{tmath|n^3 - n}} 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]] where field operations (addition and multiplication) take constant time (in practice, this is the case for [[floating point]] numbers, but not necessarily for integers).