logo search
tsvpis

2.4.2. Быстрое умножение матриц

Оценим трудоемкость обычного умножения двух матриц n×n. Трудоемкость будет иметь порядок n3, т.к. в матрице-результате перемножения будет n×n = n2 элементов и каждый из них вычисляется за n операций попарного умножения и сложения.

Попробуем применить ту же идею, что и быстрого умножения чисел, при перемножении двух матриц n×n. Разделим каждую из них на 4 матрицы вдвое меньшего размера:

Итак, при применении обычных формул блочного произведения матриц получаем рекуррентную формулу:

трудоемкость перемножения матриц вдвое меньшего размера.

трудоемкость сложений.

Соответственно по Теореме 2.2 получаем T(n) = , то есть трудоемкость такая же, как и при обычном умножении.

Однако существуют формулы Штрассена для блочного умножения матриц. В этих формулах будет не 8, а 7 попарных умножений матриц размера .

Формула Штрассена:

M1 = (A2 – A4)(B3 + B4)

M2 = (A1 + A4)(B1 + B4)

M3 = (A1 – A3)(B1 + B2)

M4 = (A1 + A2)B4

M5 = A1(B2 – B4)

(2.11)

M6 = A4 (B3 – B1)

M7 = (A3 + A4)B1

C1 = M1 +M2 – M4 + M6

C2 = M4 + M5

C3 = M6 +M7

C4 = M2 – M3 + M5 – M7

7 умножений и 18 сложений и вычитаний в этих формулах.

Следовательно, по Теореме 2.2 получаем