2.4.1.1 — семь произведений блоков вместо восьми, и кубический барьер падает2.4.1.1 — seven block products instead of eight, and the cubic barrier falls
Умножение Карацубы (2.4.1.2) сократило число рекурсивных умножений при работе с числами с 4 до 3. Фолькер Штрассен (1969) применил ровно ту же идею к матрицам: наивное блочное умножение n×n матрицы, разбитой на 4 блока n/2×n/2, требует 8 рекурсивных умножений блоков — и даёт ту же O(n³), что и школьный тройной цикл, без всякого выигрыша от рекурсии. Штрассен нашёл способ вычислить те же 4 блока результата через 7 хитрых линейных комбинаций сумм и разностей подматриц вместо 8 прямых произведений — ценой более сложной алгебры на шаге объединения, точно так же, как у Карацубы.Karatsuba multiplication (2.4.1.2) cut the number of recursive multiplications for numbers from 4 to 3. Volker Strassen (1969) applied exactly the same idea to matrices: naive block multiplication of an n×n matrix split into 4 blocks of size n/2×n/2 requires 8 recursive block multiplications — yielding the same O(n³) as the schoolbook triple loop, with no benefit from the recursion at all. Strassen found a way to compute the same 4 result blocks via 7 clever linear combinations of submatrix sums and differences instead of 8 direct products — at the cost of trickier combine-step algebra, exactly as with Karatsuba.
Пусть A и B — n×n матрицы, каждая разбита на 4 блока n/2×n/2: A = [[A11,A12],[A21,A22]], B = [[B11,B12],[B21,B22]]. Наивное блочное умножение вычисляет C11 = A11B11 + A12B21, C12 = A11B12 + A12B22, C21 = A21B11 + A22B21, C22 = A21B12 + A22B22 — 8 произведений блоков, T(n) = 8T(n/2) + O(n²), по Master theorem (2.1.2) это O(n³), то же самое, что и без всякой рекурсии.Let A and B be n×n matrices, each split into 4 blocks of size n/2×n/2: A = [[A11,A12],[A21,A22]], B = [[B11,B12],[B21,B22]]. Naive block multiplication computes C11 = A11B11 + A12B21, C12 = A11B12 + A12B22, C21 = A21B11 + A22B21, C22 = A21B12 + A22B22 — 8 block products, T(n) = 8T(n/2) + O(n²), which by the Master theorem (2.1.2) is O(n³), the same as without any recursion.
Штрассен вычисляет 7 промежуточных произведений: M1=(A11+A22)(B11+B22), M2=(A21+A22)B11, M3=A11(B12−B22), M4=A22(B21−B11), M5=(A11+A12)B22, M6=(A21−A11)(B11+B12), M7=(A12−A22)(B21+B22). Результирующие блоки собираются только сложениями и вычитаниями: C11=M1+M4−M5+M7, C12=M3+M5, C21=M2+M4, C22=M1−M2+M3+M6 — можно прямой подстановкой убедиться, что это даёт те же 4 блока, что и наивная формула, но 7 умножений вместо 8. Рекуррентное соотношение T(n) = 7T(n/2) + O(n²) (сложения/вычитания блоков стоят O(n²)) по Master theorem даёт T(n) = O(n^log₂7) = O(n^2.807...) — асимптотически строго меньше n³.Strassen computes 7 intermediate products: M1=(A11+A22)(B11+B22), M2=(A21+A22)B11, M3=A11(B12−B22), M4=A22(B21−B11), M5=(A11+A12)B22, M6=(A21−A11)(B11+B12), M7=(A12−A22)(B21+B22). The result blocks are assembled using only additions and subtractions: C11=M1+M4−M5+M7, C12=M3+M5, C21=M2+M4, C22=M1−M2+M3+M6 — direct substitution confirms this gives the same 4 blocks as the naive formula, but with 7 multiplications instead of 8. The recurrence T(n) = 7T(n/2) + O(n²) (adding/subtracting blocks costs O(n²)) gives, by the Master theorem, T(n) = O(n^log₂7) = O(n^2.807...) — asymptotically strictly below n³.
та же схема, что у Карацубы: одно "лишнее" умножение с более сложной комбинацией слагаемых заменяет несколько прямыхthe same scheme as Karatsuba: one "extra" multiplication with a trickier combination of terms replaces several direct ones
Matrix strassen(const Matrix& A, const Matrix& B) {
if (A.n == 1) return {{A[0][0] * B[0][0]}};
auto [A11,A12,A21,A22] = split(A);
auto [B11,B12,B21,B22] = split(B);
Matrix M1 = strassen(A11+A22, B11+B22);
Matrix M2 = strassen(A21+A22, B11);
Matrix M3 = strassen(A11, B12-B22);
Matrix M4 = strassen(A22, B21-B11);
Matrix M5 = strassen(A11+A12, B22);
Matrix M6 = strassen(A21-A11, B11+B12);
Matrix M7 = strassen(A12-A22, B21+B22);
Matrix C11 = M1 + M4 - M5 + M7; // только +/- блоков, O(n²)// only block +/-, O(n²)
Matrix C12 = M3 + M5;
Matrix C21 = M2 + M4;
Matrix C22 = M1 - M2 + M3 + M6;
return combine(C11, C12, C21, C22);
}Две фиксированные 2×2 матрицы — демонстрация проигрывает вычисление всех семи произведений M1..M7, а затем сборку четырёх итоговых блоков C11..C22 только через сложения и вычитания.Two fixed 2×2 matrices — the demo auto-plays computing all seven products M1..M7, then assembling the four result blocks C11..C22 using only additions and subtractions.
две матрицы A и B (значения — просто числа, не блоки, для наглядности) — нажмите «запустить»two matrices A and B (values are plain numbers, not blocks, for clarity) — press "run"
O(n^2.807) строго лучше O(n³) асимптотически, но у алгоритма Штрассена три практических недостатка. Во-первых, константа: 7 умножений и около 18 сложений/вычитаний блоков на каждом уровне рекурсии дают заметно больший overhead, чем прямой тройной цикл, — выигрыш проявляется только на достаточно больших матрицах (порядка нескольких сотен–тысяч элементов в стороне, в зависимости от реализации и железа). Во-вторых, локальность кэша: наивное блочное умножение с ручной настройкой блоков под размер кэша (loop tiling) на практике использует память эффективнее, чем рекурсивная структура Штрассена. В-третьих и важнее всего — численная устойчивость: вычитания в M3, M4, M6, M7 могут приводить к катастрофическому сокращению (catastrophic cancellation) при работе с числами с плавающей точкой, чего нет в наивном умножении, где все операции — только сложения произведений. Это тот же паттерн, что и с кучей Фибоначчи (2.3.3.4): доказанно лучшая асимптотика не означает победу без замера на реальных данных и оценки погрешности.O(n^2.807) is strictly better than O(n³) asymptotically, but Strassen's algorithm has three practical drawbacks. First, the constant factor: 7 multiplications and roughly 18 block additions/subtractions at every recursion level add noticeably more overhead than a direct triple loop — the payoff only shows up on sufficiently large matrices (on the order of several hundred to a few thousand elements per side, depending on the implementation and hardware). Second, cache locality: naive block multiplication with manually tuned block sizes matched to the cache (loop tiling) uses memory more efficiently in practice than Strassen's recursive structure. Third, and most important, numerical stability: the subtractions in M3, M4, M6, M7 can lead to catastrophic cancellation when working with floating-point numbers, something absent from naive multiplication, where every operation is just adding products. This is the same pattern as the Fibonacci heap (2.3.3.4): provably better asymptotics doesn't mean a win without measuring on real data and assessing the error.
Некоторые библиотеки линейной алгебры для действительно огромных матриц (и более новые алгоритмы семейства Штрассена — Копперсмита—Винограда и его потомки, с ещё лучшей, но чисто теоретической асимптотикой) применяются в узких нишах, где размер матрицы оправдывает и константу, и меры по контролю численной ошибки.Some linear-algebra libraries for genuinely enormous matrices (and newer Strassen-family algorithms — Coppersmith–Winograd and its descendants, with even better but purely theoretical asymptotics) are used in narrow niches where the matrix size justifies both the constant factor and the extra measures needed to control numerical error.
Штрассен — стандартный пример в курсах алгоритмов для иллюстрации разрыва между "теоретически лучше" и "на практике используется": почти никто не пишет свой matrix multiply через Штрассена в продакшене, но почти каждый курс алгоритмов через него объясняет, что n³ — не окончательный предел для умножения матриц.Strassen is a standard example in algorithms courses illustrating the gap between "theoretically better" and "actually used in practice": almost nobody writes their production matrix multiply via Strassen, but almost every algorithms course uses it to show that n³ isn't the final word on matrix multiplication.