- Метод Штрассена
-
Если перед нами стоит задача получить произведение C двух матриц A и B размера n×n, то это можно сделать несколькими способами. Лобовой алгоритм, умножающий по формуле cik = Σaijbjk, работает за время Θ(n3) = Θ(nlog2 8). Другой простой алгоритм работает рекурсивно и разбивает каждую из умножаемых матриц на 4 части так, что произведение C = AB представимо следующим образом:
Он производит 8 умножений матриц размером
, поэтому также работает за время Θ(nlog2 8). Алгоритм Штрассена, обозначает схему, при которой в рекурсивном алгоритме можно обойтись семью умножениями матриц размера
, тем самым сократив трудоемкость до Θ(nlog2 7) = Θ(n2.81), что дает заметный выигрыш на больших плотных матрицах (начиная, примерно, от 64×64).
Описание алгоритма
Вначале мы проверяем, является ли размер умножаемых матриц n натуральной степенью двойки. Если нет, мы дополняем исходные матрицы дополнительными нулевыми строками и столбцами. При этом мы получаем удобные для рекурсивного умножения размеры, но теряем в эффективности за счет дополнительных ненужных умножений. Алгоритм Штрассена умножает две (n×n)-матрицы A и B следующим образом:
- Каждая из матриц A и B разбивается на 4 блока по схеме, приведенной выше.
- Строятся 14 матриц A1, B1, A2, B2, …, A7, B7 размера (n/2×n⁄2) (для чего нужно Θ(n2) операций сложения/вычитания чисел).
- Рекурсивно вычисляются 7 произведений матриц меньшего размера Pi = AiBi (i = 1, …, 7).
- Вычисляются части r, s, t, u искомой матрицы C. Они являются линейными комбинациями матриц Pi с коэффициентами из множества {−1, 0, 1}, и вычисление их требует Θ(n2) операций сложения/вычитания чисел.
Формулы, по которым происходит умножение
i Ai Bi Pi = AiBi 1 a f - h af - ah 2 a + b h ah + bh 3 c + d e ce + de 4 d g − e dg − de 5 a + d e + h ae + ah + de + dh 6 b − d g + h bg + bh − dg − dh 7 a − c e + f ae + af − ce − cf 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). На практике же метод Штрассена гораздо проще программируется и имеет меньшую константу в оценке трудоемкости.
Литература
- Ананий В. Левитин Глава 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
Wikimedia Foundation. 2010.