WikiSort.ru - Не сортированное

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

В отличие от традиционного алгоритма умножения матриц (по формуле ${\displaystyle c_{i,k}=\sum a_{i,j}b_{j,k}}$ ), работающего за время ${\displaystyle \Theta (n^{\log _{2}8})=\Theta (n^{3})}$ , алгоритм Штрассена умножает матрицы за время ${\displaystyle \Theta (n^{\log _{2}7})=O(n^{2.81})}$ , что даёт выигрыш на больших плотных матрицах начиная, примерно, от 64×64.

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

Алгоритм

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

${\displaystyle \mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in R^{2^{n}\times 2^{n}}}$

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

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

${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1,1}&\mathbf {A} _{1,2}\\\mathbf {A} _{2,1}&\mathbf {A} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {B} ={\begin{bmatrix}\mathbf {B} _{1,1}&\mathbf {B} _{1,2}\\\mathbf {B} _{2,1}&\mathbf {B} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {C} ={\begin{bmatrix}\mathbf {C} _{1,1}&\mathbf {C} _{1,2}\\\mathbf {C} _{2,1}&\mathbf {C} _{2,2}\end{bmatrix}}}$

где

${\displaystyle \mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in R^{2^{n-1}\times 2^{n-1}}}$

тогда

${\displaystyle \mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}}$

${\displaystyle \mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}}$

${\displaystyle \mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}}$

${\displaystyle \mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}}$

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

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

${\displaystyle \mathbf {P} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})}$

${\displaystyle \mathbf {P} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}}$

${\displaystyle \mathbf {P} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})}$

${\displaystyle \mathbf {P} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})}$

${\displaystyle \mathbf {P} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}}$

${\displaystyle \mathbf {P} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})}$

${\displaystyle \mathbf {P} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})}$

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

${\displaystyle \mathbf {C} _{1,1}=\mathbf {P} _{1}+\mathbf {P} _{4}-\mathbf {P} _{5}+\mathbf {P} _{7}}$

${\displaystyle \mathbf {C} _{1,2}=\mathbf {P} _{3}+\mathbf {P} _{5}}$

${\displaystyle \mathbf {C} _{2,1}=\mathbf {P} _{2}+\mathbf {P} _{4}}$

${\displaystyle \mathbf {C} _{2,2}=\mathbf {P} _{1}-\mathbf {P} _{2}+\mathbf {P} _{3}+\mathbf {P} _{6}}$

Рекурсивный процесс продолжается n раз, до тех пор пока размер матриц C_{i, j} не станет достаточно малым, далее используют обычный метод умножения матриц. Это делают из-за того, что алгоритм Штрассена теряет эффективность по сравнению с обычным на малых матрицах в силу большего числа сложений. Оптимальный размер матриц для перехода к обычному умножению зависит от характеристик процессора и языка программирования и на практике лежит в пределах от 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 начались активные поиски более быстрого алгоритма. Самым асимптотически быстрым алгоритмом на сегодняшний день является алгоритм Копперсмита — Винограда, позволяющий перемножать матрицы за ${\displaystyle {\rm {O}}(n^{2.376})}$ операций^[1], предложенный в 1987 году и усовершенствованный в 2011 году до уровня ${\displaystyle {\rm {O}}(n^{2.3727})}$ ^[1]. Этот алгоритм не представляет практического интереса в силу астрономически большой константы в оценке арифметической сложности. Вопрос о предельной в асимптотике скорости перемножения матриц не решен. Существует гипотеза Штрассена о том, что для достаточно больших n существует алгоритм перемножения двух матриц размера ${\displaystyle n\times n}$ за ${\displaystyle {\rm {O}}(n^{2+\varepsilon })}$ операций, где ${\displaystyle \varepsilon }$ сколь угодно малое наперед заданное положительное число. Эта гипотеза имеет сугубо теоретический интерес, так как размер матриц, для которых ${\displaystyle \varepsilon }$ действительно мало, по всей видимости очень велик.

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

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

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

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

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

${\displaystyle \mathbf {S} _{1}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})}$

${\displaystyle \mathbf {S} _{2}:=(\mathbf {S} _{1}-\mathbf {A} _{1,1})}$

${\displaystyle \mathbf {S} _{3}:=(\mathbf {A} _{1,1}-\mathbf {A} _{2,1})}$

${\displaystyle \mathbf {S} _{4}:=(\mathbf {A} _{1,2}-\mathbf {S} _{2})}$

${\displaystyle \mathbf {S} _{5}:=(\mathbf {B} _{1,2}-\mathbf {B} _{1,1})}$

${\displaystyle \mathbf {S} _{6}:=(\mathbf {B} _{2,2}-\mathbf {S} _{5})}$

${\displaystyle \mathbf {S} _{7}:=(\mathbf {B} _{2,2}-\mathbf {B} _{1,2})}$

${\displaystyle \mathbf {S} _{8}:=(\mathbf {S} _{6}-\mathbf {B} _{2,1})}$

${\displaystyle \mathbf {P} _{1}:=\mathbf {S} _{2}\mathbf {S} _{6}}$

${\displaystyle \mathbf {P} _{2}:=\mathbf {A} _{1,1}\mathbf {B} _{1,1}}$

${\displaystyle \mathbf {P} _{3}:=\mathbf {A} _{1,2}\mathbf {B} _{2,1}}$

${\displaystyle \mathbf {P} _{4}:=\mathbf {S} _{3}\mathbf {S} _{7}}$

${\displaystyle \mathbf {P} _{5}:=\mathbf {S} _{1}\mathbf {S} _{5}}$

${\displaystyle \mathbf {P} _{6}:=\mathbf {S} _{4}\mathbf {B} _{2,2}}$

${\displaystyle \mathbf {P} _{7}:=\mathbf {A} _{2,2}\mathbf {S} _{8}}$

${\displaystyle \mathbf {T} _{1}:=\mathbf {P} _{1}+\mathbf {P} _{2}}$

${\displaystyle \mathbf {T} _{2}:=\mathbf {T} _{1}+\mathbf {P} _{4}}$

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

${\displaystyle \mathbf {C} _{1,1}:=\mathbf {P} _{2}+\mathbf {P} _{3}}$

${\displaystyle \mathbf {C} _{1,2}:=\mathbf {T} _{1}+\mathbf {P} _{5}+\mathbf {P} _{6}}$

${\displaystyle \mathbf {C} _{2,1}:=\mathbf {T} _{2}-\mathbf {P} _{7}}$

${\displaystyle \mathbf {C} _{2,2}:=\mathbf {T} _{2}+\mathbf {P} _{5}}$

Примечания

Литература

• Strassen V. Gaussian Elimination is not Optimal // Numer. Math — Springer Science+Business Media, 1969. — Vol. 13, Iss. 4. — P. 354–356. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF02165411
  <a href='https://wikidata.org/wiki/Track:Q176916'></a><a href='https://wikidata.org/wiki/Track:Q7069670'></a><a href='https://wikidata.org/wiki/Track:Q21694537'></a><a href='https://wikidata.org/wiki/Track:Q65212'></a>
• Левитин А. В. Глава 4. Метод декомпозиции: Умножение больших целых чисел и алгоритм умножения матриц Штрассена // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 189–195. — 576 с. — ISBN 978-5-8459-0987-9
  <a href='https://wikidata.org/wiki/Track:Q21694518'></a><a href='https://wikidata.org/wiki/Track:Q21694521'></a><a href='https://wikidata.org/wiki/Track:Q21694522'></a>
• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 28. Работа с матрицами // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — С. 833 - 839. — ISBN 5-8459-0857-4.