Версия 22:20, 16 октября 2017

Основные авторы описания: Ю.В.Рябкова

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм Штрассена, описанный в 1969 году Фолькером Штрассеном, предназначен для умножения двух произвольных матриц при условии согласованности их размеров. В данном варианте алгоритма будет рассмотрен только частный случай умножения квадратных матриц порядка [math]n[/math] над полем вещественных чисел [math]\mathbb{R}[/math].
В 1965 году Штрассен нашел способ умножения двух матриц размера [math]2 \times 2[/math] с использованием семи умножений, в то время как классический алгоритм перемножения матриц требует восьми умножений. Стоит отметить, что данный способ не использует свойство коммутативности для операции перемножения чисел.
Теперь предположим, что [math]n = 2^L[/math], [math] L \in \mathbb{N} [/math], и будем рассматривать матрицы [math]A[/math] и [math]B[/math] как блочные [math]2 \times 2[/math]-матрицы с размером блоков [math]\frac{n}{2} \times \frac{n}{2} [/math]. Так как для блочных матриц правила умножения остаются теми же, как если бы на месте блока стояло число, а в методе Штрассена умножения [math]2 \times 2[/math]-матриц не используется коммутативность, этот метод подходит и для умножения блочных [math]2 \times 2[/math]-матриц. Таким образом, от задачи умножения [math]2 \times 2[/math]-матриц с семью умножениями можно перейти к задаче умножения [math]n \times n[/math]-матриц, требующей не более чем [math] O(7n^{\log_27}) [/math] операций, что асимптотически лучше классического способа умножения матриц [math](O(n^3))[/math]. На данный момент известны и более быстрые методы умножения матриц, однако алгоритм Штрассена относительно прост в реализации и эффективен на плотных матрицах не очень больших размеров, поэтому всё ещё широко используется.

1.2 Математическое описание алгоритма

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

@@ Строка 7: / Строка 7: @@
 '''Алгоритм Штрассена''', описанный в 1969 году Фолькером Штрассеном, предназначен для умножения двух произвольных матриц при условии согласованности их размеров. В данном варианте алгоритма будет рассмотрен только частный случай умножения квадратных матриц порядка <math>n</math> над полем вещественных чисел <math>\mathbb{R}</math>. <br>
-В 1965 году Штрассен нашел способ умножения двух матриц размера <math>2 \times 2</math> с использованием семи умножений, в то время как классический алгоритм перемножения матриц требует восьми умножений. Стоит отметить, что данный способ не использует свойство коммутативности для операции перемножения чисел. Рассмотрим этот способ подробнее: пусть <math>A</math> и <math>B</math> - произвольные квадратные матрицы порядка <math>2</math>: <br>
+В 1965 году Штрассен нашел способ умножения двух матриц размера <math>2 \times 2</math> с использованием семи умножений, в то время как классический алгоритм перемножения матриц требует восьми умножений. Стоит отметить, что данный способ не использует свойство коммутативности для операции перемножения чисел. <br>
-: <math> A =
-\begin{bmatrix}
-  a_{11} & a_{12} \\
-  a_{21} & a_{22}
-\end{bmatrix}, \: \:
-B =
-\begin{bmatrix}
-  b_{11} & b_{12} \\
-  b_{21} & b_{22}
-\end{bmatrix},
-</math> <br>
-тогда их произведение <br>
-: <math> C = AB =
-\begin{bmatrix}
-  c_{11} & c_{12} \\
-  c_{21} & c_{22}
-\end{bmatrix}</math> <br>
-может быть получено последовательными вычислениями по следующим формулам:
-:<math> \alpha_{1} = (a_{11} + a_{22})(b_{11} + b_{22}) </math>
-:<math> \alpha_{2} = (a_{21} + a_{22})b_{11} </math>
-:<math> \alpha_{3} = a_{11}(b_{12} − b_{22}) </math>
-:<math> \alpha_{4} = a_{22}(b_{21} − b_{11}) </math>
-:<math> \alpha_{5} = (a_{11} + a_{12})b_{22} </math>
-:<math> \alpha_{6} = (a_{21} − a_{11})(b_{11} + b_{12}) </math>
-:<math> \alpha_{7} = (a_{12} − a_{22})(b_{21} + b_{22}) </math>
-:<math> c_{11} = \alpha_{1} + \alpha_{4} - \alpha_{5} + \alpha_{7} </math>
-:<math> c_{12} = \alpha_{3} + \alpha_{5} </math>
-:<math> c_{21} = \alpha_{2} + \alpha_{4} </math>
-:<math> c_{22} = \alpha_{1} + \alpha_{3} - \alpha_{2} + \alpha_{6} </math>
 Теперь предположим, что <math>n = 2^L</math>, <math> L \in \mathbb{N} </math>, и будем рассматривать матрицы <math>A</math> и <math>B</math> как блочные <math>2 \times 2</math>-матрицы с размером блоков <math>\frac{n}{2} \times \frac{n}{2} </math>. Так как для блочных матриц правила умножения остаются теми же, как если бы на месте блока стояло число, а в методе Штрассена умножения <math>2 \times 2</math>-матриц не используется коммутативность, этот метод подходит и для умножения блочных <math>2 \times 2</math>-матриц. Таким образом, от задачи умножения <math>2 \times 2</math>-матриц с семью умножениями можно перейти к задаче умножения <math>n \times n</math>-матриц, требующей не более чем <math> O(7n^{\log_27}) </math> операций, что асимптотически лучше классического способа умножения матриц <math>(O(n^3))</math>. На данный момент известны и более быстрые методы умножения матриц, однако алгоритм Штрассена относительно прост в реализации и эффективен на плотных матрицах не очень больших размеров, поэтому всё ещё широко используется.

Участник:Y.ryabkova/Умножение матриц методом Штрассена: различия между версиями