Алгоритм Штрассена

Алгоритм Штрассена предназначен для быстрого умножения матриц. Он был разработан Штрассеном в 1969 году как обобщение метода умножения Карацубы на матрицы.

В отличие от традиционного алгоритма умножения матриц (по формуле cik = Σaijbjk), работающего за время Θ(n³) = Θ(nlog2 8), А.Ш. умножает матрицы за время Θ(nlog2 7) = Θ(n2.81), что даёт заметный выигрыш на больших плотных матрицах (начиная, примерно, от 64×64).

Несмотря на то, что А.Ш. является не самым быстрым из существующих алгоритмов быстрого умножения матриц, он проще программируется, поэтому именно он чаще используется на практике. 

Пусть A, B — две квадратные матрицы над кольцом R. Матрица C получается по формуле:

Если размер умножаемых матриц n не является натуральной степенью двойки, мы дополняем исходные матрицы дополнительными нулевыми строками и столбцами. При этом мы получаем удобные для рекурсивного умножения размеры, но теряем в эффективности за счёт дополнительных ненужных умножений.

Разделим матрицы A, B и C на равные по размеру блочные матрицы

где

тогда

Однако с помощью этой процедуры нам не удалось уменьшить количество умножений. Как и в обычном методе, нам требуется 8 умножений.

Теперь определим новые элементы

которые затем используются для выражения Ci, j. Таким образом, нам нужно всего 7 умножений на каждом этапе рекурсии. Элементы матрицы C выражаются из Pk по формулам

Итерационный процесс продолжается n раз, до тех пор пока матрицы Ci, j не выродятся в числа (элементы кольца R). На практике итерации останавливают при размере матриц от 32 до 128 и далее используют обычный метод умножения матриц. Это делают из-за того, что А.Ш. теряет эффективность по сравнению с обычным на малых матрицах из-за дополнительных копирований массивов. 

Приведён пример реализации А.Ш. на Фортране. Предполагается, что все матрицы квадратные, их размер является степенью 2.

MODULE STRASSEN_MUL

CONTAINS

! X = A * B

! V - dimension of matrices

RECURSIVE SUBROUTINE MUL(A, B, V, C)

INTEGER, INTENT(IN) :: V

DOUBLE PRECISION, INTENT(IN) :: A( : , : ), B( : , : )

INTEGER :: H ! H = V/2 (see below)

DOUBLE PRECISION, INTENT(OUT) :: C(V, V)

DOUBLE PRECISION, DIMENSION(:,:), ALLOCATABLE :: P1, P2, P3, P4, P5, P6, P7

DOUBLE PRECISION, DIMENSION(:,:), ALLOCATABLE :: A11, A12, A21, A22, B11, B12, B21, B22

IF (V <= 64) THEN ! if dimension equals 64 use MUL2

CALL MUL2 (A, B, V, C)

RETURN

ENDIF

H = V/2

ALLOCATE (P1(H,H), P2(H,H), P3(H,H), P4(H,H), P5(H,H), P6(H,H), P7(H,H))

ALLOCATE (A11(H,H), A12(H,H), A21(H,H), A22(H,H), B11(H,H), B12(H,H), B21(H,H), B22(H,H))

A11 (1:H, 1:H) = A (1:H, 1:H)

A12 (1:H, 1:H) = A (1:H, H+1:V)

A21 (1:H, 1:H) = A (H+1:V, 1:H)

A22 (1:H, 1:H) = A (H+1:V, H+1:V)

B11 (1:H, 1:H) = B (1:H, 1:H)

B12 (1:H, 1:H) = B (1:H, H+1:V)

B21 (1:H, 1:H) = B (H+1:V, 1:H)

B22 (1:H, 1:H) = B (H+1:V, H+1:V)

!$OMP PARALLEL

CALL MUL(A11 + A22, B11 + B22, H, P1) ! P1 = (A11 + A22) * (B11 + B22)

CALL MUL(A21 + A22, B11, H, P2) ! etc. ...

CALL MUL(A11, B12 - B22, H, P3)

CALL MUL(A22, B21 - B11, H, P4)

CALL MUL(A11 + A12, B22, H, P5)

CALL MUL(A21 - A11, B11 + B12, H, P6)

CALL MUL(A12 - A22, B21 + B22, H, P7)

!$OMP END PARALLEL

DEALLOCATE (B11, B12, B21, B22)

DEALLOCATE (A11, A12, A21, A22)

C (1:H, 1:H) = P1 + P4 + P7 - P5

C (1:H, H+1:V) = P3 + P5

C (H+1:V, 1:H) = P2 + P4

C (H+1:V, H+1:V) = P1 - P2 + P3 + P6

DEALLOCATE (P1, P2, P3, P4, P5, P6, P7)

RETURN

END SUBROUTINE MUL

! X = A * B using standard method

SUBROUTINE MUL2 (A, B, V, X)

IMPLICIT NONE

INTEGER, INTENT(IN) :: V

DOUBLE PRECISION, INTENT(IN) :: A( : , : ), B( : , : )

DOUBLE PRECISION, INTENT(OUT), DIMENSION (:,:) :: X

INTEGER :: I, J, K

DO I = 1, V

DO J = 1, V

X (I, J) = 0

DO K = 1, V

X (I, J) = X (I, J) + A (I, K) * B (K, J)

ENDDO

ENDDO

ENDDO

RETURN

END SUBROUTINE MUL2

END MODULE STRASSEN_MUL

Вычисления промежуточных матриц P1 — P7 можно проводить параллельно при использовании таких библиотек как OpenMP или MPI, что позволяет значительно повысить скорость работы алгоритма на многопроцессорных машинах. 

Штрассен был первым, кто показал возможность умножения матриц более эффективным способом, чем стандартный. После публикации его работы в 1969 начались активные поиски более быстрого алгоритма. Самым быстрым алгоритмом на сегодняшний день является алгоритм Копперсмита — Винограда, позволяющий перемножать матрицы за O(n2.375) операций. Существует гипотеза Штрассена о том, что для больших n существует алгоритм перемножение двух матриц размера  за O(n2 + ε) операций.

Существует модификация А.Ш., для которой требуется 7 умножений и 15 сложений (вместо 18 для обычного А.Ш.).

Матрицы A, B и C делятся на блочные подматрицы как показано выше.

Вычисляются промежуточные матрицы S1 — S8, P1 — P7, T1 — T2

Элементы матрицы C вычисляются по формулам

Литература:

• Ананий В. Левитин Глава 4. Метод декомпозиции: Умножение больших целых чисел и алгоритм умножения матриц Штрассена // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms — М.: «Вильямс», 2006. — С. 189-195. — ISBN 0-201-74395-7.

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд Глава 28. Работа с матрицами // Алгоритмы: построение и анализ = Introduction to Algorithms — 2-e издание. — М.: «Вильямс», 2005. — С. 833 - 839. — ISBN 5-8459-0857-4.