Алгоритм Штрассена

Материал из WEGA
Версия от 13:44, 18 ноября 2010; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Литература

  • Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.