Штрассен: гауссово исключение не оптимально

Название статьи

В 1969 году в журнале «Numerische Mathematik» выходит работа Фолькера Штрассена с заголовком, который сам по себе есть содержание:

«Gaussian elimination is not optimal» — «Гауссово исключение не оптимально».

Штрассен искал доказательство обратного. Умножение двух матриц $n\times n$ по определению требует $n^{3}$ умножений — по одному на каждую тройку индексов, — и всем казалось очевидным, что меньше нельзя: результат содержит $n^{2}$ чисел, каждое есть сумма $n$ произведений, откуда взяться экономии? Он пытался это доказать и нашёл опровержение.

Семь вместо восьми

Возьмём матрицы $2\times2$. Обычное умножение — восемь умножений и четыре сложения. Штрассен выписал комбинацию из семи произведений специально подобранных сумм элементов, из которых все четыре элемента результата собираются одними сложениями и вычитаниями.

Одно сэкономленное умножение ценой лишних сложений — само по себе пустяк. Но приём применяется рекурсивно: разбиваем матрицу $n\times n$ на четыре блока вдвое меньшего размера и умножаем блоки тем же способом. Тогда

$$T(n)=7\,T(n/2)+O(n^{2}) \quad\Longrightarrow\quad T(n)=O\!\left(n^{\log_{2}7}\right)=O\!\left(n^{2{,}807}\right).$$

Показатель три сдвинулся — и, как выяснилось, сдвинуть его можно ещё.

Та же схема девятью годами раньше

Читатель, дошедший до этого места по линии, узнаёт приём. Ровно так же устроено решение Карацубы 1960 года: разбить объекты пополам, купить сокращение числа умножений ценой лишних сложений, применить рекурсивно, получить показатель меньше прежнего.

Совпадение не случайное, и оба случая устроены одинаково ещё в одном отношении: и Карацуба, и Штрассен искали доказательство того, что лучше нельзя. КолмогоровАндрей Николаевич Колмогороврусский и советский математик · 1903–1987Дал вероятности аксиомы, турбулентности — закон, сложности — определение, а школьной математике в СССР — программу, по которой учились миллионы. высказал гипотезу, что умножение $n$-значных чисел требует порядка $n^{2}$ операций, и семинар занимался её обоснованием; Штрассен подступался к оптимальности $n^{3}$. Оба получили опровержение вместо доказательства — и в обоих случаях выяснилось, что «очевидно необходимое» число операций таковым не является.

Гонка, которая не кончилась

После 1969 года показатель $\omega$ — точная граница сложности умножения матриц — стал предметом отдельного вида спорта. Пан, Бини, Шёнхаге, затем Копперсмит и Виноград (1990) довели его до $2{,}376$; Вильямс (2014) и Алман с Вильямс (2021) — до $2{,}372$.

Снизу известно только тривиальное $\omega\geqslant2$: результат надо хотя бы выписать. Чему равно $\omega$ на самом деле, неизвестно. Многие верят, что двум, — и тогда матрицы можно перемножать почти так же дёшево, как складывать.

У этой гонки есть ироническая сторона. Алгоритмы после Штрассена почти все «галактические»: их преимущество проявляется на матрицах такого размера, какой не поместится ни в одну существующую машину, а константы столь велики, что практического смысла нет. Реально используется сам алгоритм Штрассена — в библиотеках линейной алгебры, при достаточно больших блоках, — и на этом список практичных достижений заканчивается.

Линия про цену вычисления получает здесь новую разновидность сюжета: цена, вычисленная теоретически, и цена, уплаченная на практике, разошлись. Оптимальность стала предметом чистой математики, отдельным от вопроса, что быстрее работает на этой неделе.

Следующая точка: Нью-Хейвен — где выяснилось, что размерностью можно пренебречь.