Алгоритм Штрассена: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Алгоритм Штрассена''' (''V.Strassen, 1968'') - алгоритм умножения двух <math>(2 \times 2)</math>...)
(нет различий)

Версия от 14:30, 24 сентября 2009

Алгоритм Штрассена (V.Strassen, 1968) - алгоритм умножения двух [math]\displaystyle{ (2 \times 2) }[/math]-матриц с элементами из произвольного кольца, в котором достаточно семи умножений. Рекурсивно применяя этот метод, можно умножить две [math]\displaystyle{ (n \times n) }[/math]-матрицы за время [math]\displaystyle{ {\cal O}(n^{\log 7}) }[/math].

Литература

[Ахо-Хопкрофт-Ульман]