Мы хотим найти произведение
A1A2×…×An (1)
последовательности п матриц (A1, A2, ….., An). Мы будем пользоваться стандартным алгоритмом перемножения двух матриц в качестве подпрограммы. Но прежде надо расставить скобки в (1), чтобы указать порядок умножений.
Будем говорить, что в произведении матрицполностью расставлены, если это произведение либо состоит из одной-единственной матрицы, либо является заключенным в скобки произведением двух произведений с полностью расставленными скобками.
Поскольку умножение матриц ассоциативно, конечный результат вычислений не зависит от расстановки скобок.
В произведении A1A2A3A4 можно полностью расставить скобки пятью разными способами:
(A1(A2(A3A4)))
(A1((A2A3)A4))
((A1A2)(A3A4))
((A1(A2A3))A4)
(((A1A2)A3)A4)
Способ расстановки скобок может сильно повлиять на стоимость перемножения матриц.
Стандартный алгоритм перемножения матриц.
rows и columns - количество строк и столбцов матрицы
MATRIX-MULTIPLY (A, B)
1 if columns [A] ¹ rows [B]
2 then error “умножить нельзя”
3 else for i ¬ 1 to rows [A]
4 do for j ¬ 1 to columns [B]
5 do C[i,j] ¬ 0
6 for k ¬ 1 to columns [A]
7 do C[i,j] ¬ C[i,j]+A[i,k]×B[k,j]
8 returnC
Если А – это ( p х q ) матрица, а В – это (q х r) матрица, то их произведение С является (p х r) матрицей.