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

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

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

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

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

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

Пусть [math]\displaystyle{ A, B \in \mathbb{R}^{n \times n} }[/math] — заданные плотные матрицы. Вычислим матрицу [math]\displaystyle{ C \in \mathbb{R}^{n \times n} }[/math], такую, что [math]\displaystyle{ C = AB }[/math].
Для удобства будем полагать, что [math]\displaystyle{ n = 2^L, L \in \mathbb{N} }[/math]. Это предположение не ограничивает общности рассуждений, так как если это свойство не выполнено и [math]\displaystyle{ n \lt 2^L }[/math], то можно рассмотреть квадратные матрицы [math]\displaystyle{ \tilde{A} }[/math] и [math]\displaystyle{ \tilde{B} }[/math] порядка [math]\displaystyle{ 2^L }[/math] следующего вида:

[math]\displaystyle{ \tilde{A} = \begin{bmatrix} A & 0 \\ 0 & 0 \end{bmatrix}, \: \: \tilde{B} = \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix}, }[/math]

то есть матрицы, полученные из матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] дополнением их нулевыми строками и столбцами в позициях [math]\displaystyle{ i = \overline{n+1, 2^L} }[/math] до размера [math]\displaystyle{ 2^L \times 2^L }[/math]. По правилу перемножения блочных матриц:

[math]\displaystyle{ \tilde{C} = \tilde{A}\tilde{B} = \begin{bmatrix} AB & 0 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} C & 0 \\ 0 & 0 \end{bmatrix}. }[/math]

Таким образом, решая задачу для матриц [math]\displaystyle{ \tilde{A} }[/math] и [math]\displaystyle{ \tilde{B} }[/math], получим решение исходной задачи умножения матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] как левый верхний [math]\displaystyle{ n \times n }[/math]-блок матрицы [math]\displaystyle{ \tilde{C} }[/math].
Итак, [math]\displaystyle{ n = 2^L, L \in \mathbb{N} }[/math].