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

Алгоритм Штрассена — это алгоритм умножения матриц, разработанный немецким математиком Фолькером Штрассеном в 1969 году. Он является первым алгоритмом, который продемонстрировал, что умножение матриц может быть выполнено быстрее, чем за кубическое время (O(n³)), характерное для классического «школьного» метода. Алгоритм основан на рекурсивном разбиении матриц на блоки и использовании специальной схемы вычислений, позволяющей сократить количество операций умножения за счёт увеличения числа операций сложения. Алгоритм Штрассена имеет асимптотическую сложность O(n^log₂7) ≈ O(n².⁸⁰⁷), что делает его более эффективным для больших матриц по сравнению с традиционным подходом.

История

До появления алгоритма Штрассена считалось, что умножение матриц размера n×n требует порядка n³ арифметических операций. Этот результат следовал из прямого применения определения умножения матриц, где каждый элемент результирующей матрицы вычисляется как сумма произведений соответствующих элементов строки и столбца. В 1969 году Фолькер Штрассен, работая в то время в Стэнфордском университете, опубликовал статью, в которой показал, что можно обойтись меньшим числом умножений, используя рекурсивное разбиение и нетривиальную комбинацию операций. Его работа стала важным прорывом в теории сложности вычислений и положила начало поиску ещё более быстрых алгоритмов умножения матриц.

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

Основная идея

Алгоритм Штрассена применим к квадратным матрицам, размер которых является степенью двойки (n = 2^k). Если исходные матрицы не удовлетворяют этому условию, их дополняют нулевыми строками и столбцами до ближайшей степени двойки. Алгоритм рекурсивно делит каждую матрицу на четыре блока равного размера:

A = [[A₁₁, A₁₂], [A₂₁, A₂₂]], B = [[B₁₁, B₁₂], [B₂₁, B₂₂]].

Классический метод потребовал бы 8 умножений блоков и 4 сложения. Штрассен предложил вычислять 7 специальных произведений (P₁, P₂, ..., P₇), которые затем комбинируются с помощью сложений и вычитаний для получения блоков результирующей матрицы C.

Семь произведений Штрассена

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

1. P₁ = A₁₁ · (B₁₂ – B₂₂)
2. P₂ = (A₁₁ + A₁₂) · B₂₂
3. P₃ = (A₂₁ + A₂₂) · B₁₁
4. P₄ = A₂₂ · (B₂₁ – B₁₁)
5. P₅ = (A₁₁ + A₂₂) · (B₁₁ + B₂₂)
6. P₆ = (A₁₂ – A₂₂) · (B₂₁ + B₂₂)
7. P₇ = (A₁₁ – A₂₁) · (B₁₁ + B₁₂)

Сборка результирующей матрицы

Блоки матрицы C = A · B получаются путём сложения и вычитания этих произведений:

• C₁₁ = P₅ + P₄ – P₂ + P₆
• C₁₂ = P₁ + P₂
• C₂₁ = P₃ + P₄
• C₂₂ = P₅ + P₁ – P₃ – P₇

Таким образом, вместо 8 умножений выполняется только 7, но число сложений возрастает с 4 до 18. Для малых размеров матриц это невыгодно, но при рекурсивном применении асимптотическая сложность снижается.

Асимптотическая сложность

Алгоритм Штрассена имеет рекуррентное соотношение для времени работы T(n) = 7·T(n/2) + O(n²), где O(n²) — затраты на сложения и вычитания. Решение этого соотношения даёт T(n) = O(n^log₂7) ≈ O(n².⁸⁰⁷). Для сравнения, классический алгоритм имеет сложность O(n³), а алгоритм Винограда (оптимизированная версия классического) — O(n³) с меньшей константой. Практический выигрыш от алгоритма Штрассена становится заметным при размерах матриц от нескольких сотен до тысяч элементов, хотя точный порог зависит от реализации и аппаратного обеспечения.

Применение

Алгоритм Штрассена используется в вычислительной математике, физике, машинном обучении и других областях, где требуется умножение больших матриц. Однако на практике его применение ограничено из-за следующих факторов:

• Численная устойчивость: Алгоритм менее устойчив к ошибкам округления по сравнению с классическим методом, что может быть критично для задач с плавающей точкой.
• Сложность реализации: Требуется тщательная оптимизация для работы с матрицами произвольного размера и учёт кэш-памяти.
• Порог эффективности: Для малых матриц (например, до 100×100) классический метод часто быстрее из-за меньших накладных расходов.

Тем не менее, алгоритм Штрассена является основой для многих современных библиотек линейной алгебры, таких как BLAS и LAPACK, где он применяется в комбинации с другими методами для достижения оптимальной производительности.

Критика и ограничения

Основные недостатки алгоритма Штрассена связаны с его численной устойчивостью и практической реализацией. Исследования показывают, что при использовании арифметики с плавающей точкой ошибки округления могут накапливаться быстрее, чем в классическом алгоритме, особенно для плохо обусловленных матриц. Кроме того, рекурсивная природа алгоритма приводит к дополнительным затратам памяти и времени на управление рекурсией. В связи с этим для многих практических задач предпочтение отдаётся оптимизированным версиям классического умножения, таким как алгоритм Копперсмита — Винограда (сложность O(n².³⁷⁶)) или его современные улучшения, хотя они ещё более сложны в реализации и редко применяются на практике.

Интересные факты

• Алгоритм Штрассена стал первым в серии «быстрых» алгоритмов умножения матриц. Впоследствии были разработаны методы с ещё более низкой сложностью, например, алгоритм Копперсмита — Винограда (1987) и его последующие улучшения, однако их практическое применение ограничено из-за огромных констант.
• Фолькер Штрассен также известен своими работами в области теории сложности вычислений, включая доказательство того, что задача проверки простоты числа может быть решена за полиномиальное время (тест Миллера — Рабина).
• Алгоритм Штрассена часто используется в учебных курсах по алгоритмам и структурам данных как пример «разделяй и властвуй» и метода снижения асимптотической сложности.