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

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

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

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

Алгоритм Штрассена, описанный в 1969 году Фолькером Штрассеном, предназначен для умножения двух произвольных матриц при условии согласованности их размеров. В данном варианте алгоритма будет рассмотрен только частный случай умножения квадратных матриц порядка [math]\displaystyle{ n }[/math] над полем вещественных чисел [math]\displaystyle{ \mathbb{R} }[/math].
В 1965 году Штрассен нашел способ умножения двух матриц размера [math]\displaystyle{ 2 \times 2 }[/math] с использованием семи умножений, в то время как классический алгоритм перемножения матриц требует восьми умножений. Стоит отметить, что данный способ не использует свойство коммутативности для операции перемножения чисел. Рассмотрим этот способ подробнее: пусть [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] - произвольные квадратные матрицы порядка [math]\displaystyle{ 2 }[/math]:

[math]\displaystyle{ 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]

тогда их произведение

[math]\displaystyle{ C = AB = \begin{bmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \end{bmatrix} }[/math]

может быть получено последовательными вычислениями по следующим формулам:

[math]\displaystyle{ \alpha_{1} = (a_{11} + a_{22})(b_{11} + b_{22}) }[/math]

[math]\displaystyle{ \alpha_{2} = (a_{21} + a_{22})b_{11} }[/math]

[math]\displaystyle{ \alpha_{3} = a_{11}(b_{12} − b_{22}) }[/math]

[math]\displaystyle{ \alpha_{4} = a_{22}(b_{21} − b_{11}) }[/math]

[math]\displaystyle{ \alpha_{5} = (a_{11} + a_{12})b_{22} }[/math]

[math]\displaystyle{ \alpha_{6} = (a_{21} − a_{11})(b_{11} + b_{12}) }[/math]

[math]\displaystyle{ \alpha_{7} = (a_{12} − a_{22})(b_{21} + b_{22}) }[/math]

[math]\displaystyle{ c_{11} = \alpha_{1} + \alpha_{4} - \alpha_{5} + \alpha_{7} }[/math]

[math]\displaystyle{ c_{12} = \alpha_{3} + \alpha_{5} }[/math]

[math]\displaystyle{ c_{21} = \alpha_{2} + \alpha_{4} }[/math]

[math]\displaystyle{ c_{22} = \alpha_{1} + \alpha_{3} - \alpha_{2} + \alpha_{6} }[/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]. На данный момент известны и более быстрые методы умножения матриц, однако алгоритм Штрассена относительно прост в реализации и эффективен на плотных матрицах не очень больших размеров, поэтому всё ещё широко используется.