Метод Штрассена

Метод Штрассена

Если перед нами стоит задача получить произведение 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 & g \\ f & h \end{pmatrix} 
\begin{matrix}& & r = ae + bf & t= ce + df \\ \ &
 & s = ag + bh & u= cg + dh\end{matrix}

Он производит 8 умножений матриц размером n \over 2, поэтому также работает за время Θ(nlog2 8). Алгоритм Штрассена, обозначает схему, при которой в рекурсивном алгоритме можно обойтись семью умножениями матриц размера n \over 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 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.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Метод Штрассена" в других словарях:

  • Метод умножения Шёнхаге — Метод умножения Шёнхаге  Штрассена (англ. Schönhage–Strassen algorithm)  быстрый метод умножения больших целых чисел. Основной идеей алгоритма является быстрое преобразование Фурье. Он был построен Арнольдом Шёнхаге и Фолькером… …   Википедия

  • Метод умножения Шёнхаге — Штрассена — Метод умножения Шёнхаге  Штрассена (англ. Schönhage–Strassen algorithm)  это асимптотически быстрый метод умножения для больших целых чисел. Является обобщением метода Карацубы с применением Быстрого Преобразования Фурье и умножения по… …   Википедия

  • Метод умножения Шёнхаге-Штрассена — это асимптотически быстрый метод умножения для больших целых чисел. Он был построен Арнольдом Шёнхаге и Фолькером Штрассеном в 1971.[1] Битовая сложность метода есть , а арифметическая сложность .[2] Этот метод использует быстрые преобразования… …   Википедия

  • Метод квадратичных форм Шенкса — метод факторизации целых чисел, основанный на применении квадратичных форм, разработанный Даниелем Шенксом (англ. Daniel Shanks).[1] в 1975 году, как развитие метода факторизации Ферма. Для 32 разрядных компьютерах алгоритмы, основанные на… …   Википедия

  • Алгоритм Штрассена — предназначен для быстрого умножения матриц. Он был разработан Штрассеном в 1969 году как обобщение метода умножения Карацубы на матрицы. В отличие от традиционного алгоритма умножения матриц (по формуле cik = Σaijbjk), работающего за время Θ(n³) …   Википедия

  • Алгоритм Фюрера — (англ. Fürer’s algorithm)  быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером[1] из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Умножение матриц — одна из основных операций над матрицами. Матрица, получаемая в результате операции умножения, называется произведением матриц. Содержание 1 Определение 2 Иллюстрация 3 Мотивировка …   Википедия

  • Тест простоты — Тест простоты  алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»