Задача матричного умножения требует для своего решения выполнения большого количества арифметических операций.

Пусть `A, B, C` – квадратные матрицы `n xx n` , `C = AB` . Тогда компоненты матрицы `C` рассчитываются по следующей формуле

`c_(ij)=sum_(k=1)^n (a_(ik) b_(kj))` , `i,j=1,...,n` . (2.14)

Из (2.14) видно, что для вычисления одного элемента матрицы `C` необходимо `n` умножений и `n` сложений. Учитывая общее количество таких элементов, можно сосчитать, что операция умножения матриц потребует выполнения `n^3` скалярных умножений и `n^3` сложений на обычном последовательном компьютере:

`T_1=(t_(m u)+t_(a d))n^3` .

Произведение матриц может рассматриваться как `n^2` независимых скалярных произведений, либо как `n` независимых произведений матрицы на вектор. В каждом случае используются различные алгоритмы.

Производительность умножения матриц может быть улучшена путем изменения порядка циклов `ijk` в (2.14). Каждый язык программирования характеризуется различным способом хранения в памяти компьютера элементов массивов. На языке высокого уровня Fortran элементы матриц располагаются последовательно в памяти по столбцам матрицы, т.е. `{a_(11),a_(21),...,a_(n1),a_(12),a_(22),...,a_(n2),a_(13),...,a_(n n)}` . Размещаемые в кэш-памяти элементы матриц `A,B,C` эффективно используются, когда доступ к ним или их модификация в алгоритме умножения матриц осуществляется с последовательно с переходом к соседней ячейке памяти. Поэтому порядок следования циклов `kji` при умножении матриц в программе, написанной на фортране, будет увеличивать производительность вычислений:

do i = 1, n

do j = 1, n

do k = 1, n

c(i, j) = c(i, j)+a(i, k)*b(k, j)

end do

do k = 1, n

do j = 1, n

do i = 1, n

c(i, j) = c(i, j)+a(i, k)*b(k, j)

end do

B(1:n,J)

A(I,1:n)

= + * – цикл `ijk`

B(k,j)

= + * – цикл `kji`

Рис.2.10. Схема доступа к элементам матриц