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

Если перед нами стоит задача получить произведение C двух матриц A и B размера n×n, то это можно сделать несколькими способами. Лобовой алгоритм, умножающий по формуле cik = Σaijbjk, работает за время Θ(n3) = Θ(nlog2 8). Другой простой алгоритм работает рекурсивно и разбивает каждую из умножаемых матриц на 4 части так, что произведение C = AB представимо следующим образом:

\begin{pmatrix} r & s \\ t & u \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix} \begin{matrix}& & r = ae + bf & t= ce + df \\ \ & & s = ag + bh & u= cg + dh\end{matrix}

Он производит 8 умножений матриц размером n⁄2, поэтому также работает за время Θ(nlog2 8). Алгоритм Штрассена, обозначает схему, при которой в рекурсивном алгоритме можно обойтись семью умножениями матриц размера n⁄2, тем самым сократив трудоемкость до Θ(nlog2 7) = Θ(n2.81), что дает заметный выигрыш на больших плотных матрицах (начиная, примерно, от 64×64).

Описание алгоритма
Вначале мы проверяем, является ли размер умножаемых матриц n натуральной степенью двойки. Если нет, мы дополняем исходные матрицы дополнительными нулевыми строками и столбцами, оставляя на главной диагонали единицы. При этом мы получаем удобные для рекурсивного умножения размеры, но теряем в эффективности за счет дополнительных ненужных умножений. Алгоритм Штрассена умножает две (n×n)-матрицы A и B следующим образом:

  1. Каждая из матриц A и B разбивается на 4 блока по схеме, приведенной выше.
  2. Строятся 14 матриц A1, B1, A2, B2, …, A7, B7 размера (n/2×n⁄2) (для чего нужно Θ(n2) операций сложения/вычитания чисел).
  3. Рекурсивно вычисляются 7 произведений матриц меньшего размера Pi = AiBi (i = 1, …, 7).
  4. Вычисляются части r, s, t, u искомой матрицы C. Они являются линейными комбинациями матриц Pi с коэффициентами из множества {−1, 0, 1}, и вычисление их требует Θ(n2) операций сложения/вычитания чисел.



Формулы, по которым происходит умножение

i Ai Bi Pi = AiBi
1 a g - h ag - ah
2 a + b h ah + bh
3 c + d e ce + de
4 d f − e df − de
5 a + d e + h ae + ah + de + dh
6 b − d f + h bf + bh − df − dh
7 a − c e + g ae + ag − ce − cg

r = P5 + P4 − P2 + P6 = ae + bf
s = P1 + P2 = ag + bh
t = P3 + P4 = ce + df
u = P5 + P1 − P3 − P7 = cg + dh

Тем не менее, самый асимптотически быстрый из известных на сегодняшний день способ умножения матриц был опубликован Копперсмитом и Виноградом в 1987-м году и позволяет перемножать квадратные матрицы за время Θ(n2.38). На практике же метод Штрассена гораздо проще программируется и имеет меньшую константу в оценке трудоемкости.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home