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

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

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]. На данный момент известны и более быстрые методы умножения матриц, однако алгоритм Штрассена относительно прост в реализации и эффективен на плотных матрицах не очень больших размеров, поэтому всё ещё широко используется.