НОВЫЙ РЕКОРД В УМНОЖЕНИИ ТАБЛИЦ ЧИСЕЛ
Умножение двух матриц — таблиц чисел — одна из самых базовых операций в вычислениях. Если делать это по-школьному, стоимость умножения двух таблиц n на n растёт как n³. Алгоритм Фолькера Штрассена 1969 года первым справился лучше — «субкубически», по выражению статьи, — и с тех пор математики измеряют прогресс одним числом: показателем ω (омега), наименьшей степенью n, которой достаточно по мере роста таблиц.
Штрассен опустил его ниже 2,81. Десятилетия работы, перечисленные в статье, довели его примерно до 2,37, причём шаги становились всё меньше. В 2026 году Эмильен Дюпон и его коллеги достигли 2,371177. Реза Заде из компании Matroid, Inc. теперь доказывает, что ω < 2,37115924.
Избранные улучшения верхней оценки ω — от Штрассена в 1969 году до этой статьи. — Таблица 1, Zadeh (2026), arXiv:2610.10593, CC BY 4.0.
Рецепт с 212 820 настройками
Эти рекорды рождаются не из более хитрого приёма для маленьких таблиц. Они происходят от алгебраического объекта под названием тензор Копперсмита — Винограда, который можно рекурсивно разрезать и перекомбинировать во множество независимых матричных произведений. Как именно его разрезать, определяет огромный набор выборов: распределения вероятностей, штрафы за энтропию и размеры матриц, задаваемые уровень за уровнем. Любой допустимый набор выборов даёт допустимую оценку; искусство в том, чтобы найти хороший.
Опираясь на подход Джоша Алмана и коллег и на формулировку Дюпона и коллег, Заде настроил 212 820 чисел сразу, с тремя усовершенствованиями:
- Перемасштабирование по значимости. Некоторые части конструкции встречаются лишь изредка, поэтому их влияние на результат крошечное и оптимизатор почти их не сдвигает. Каждое число было перемасштабировано в соответствии с весом, который несёт его часть.
- Шесть регуляторов для узких мест. Итоговый показатель определяется самой слабой из трёх конкурирующих величин на трёх этапах. Отдельная поправка использовала всего шесть управляющих параметров, чтобы держать их в равновесии.
- Точный экспорт. Итоговый рецепт был переведён в точные дроби со знаменателями 2⁹⁶.
Доказательство проверкой
Оценка — это компьютерное доказательство. Короткая программа, использующая только стандартную библиотеку Python — без сети, без модели, без дополнительных пакетов, — восстанавливает каждое распределение из точных дробей и вычисляет результат с гарантированным округлением. Она устанавливает, что ключевая величина положительна — примерно на 8,5 миллиардных, — что и доказывает оценку. Автор подчёркивает, чего это не охватывает: программа — это проверяемый код, а не формализация всей теории в системе доказательств, и поиск был локальным, без утверждения, что рецепт наилучший из возможных.
Автор также пишет, что инструменты генеративного ИИ, которые не названы, помогали с численным исследованием, программным обеспечением и рукописью, а ранний код опирался на вычислительные заметки, которыми публично поделился Эрик Наслунд. Отдельный публичный компьютерный сертификат, опубликованный 5 октября 2026 года, достиг 2,371169353; новое значение ещё ниже.
Быстрее — в теории
Выигрыш по сравнению с Дюпоном и коллегами составляет 0,00001776 в показателе. Как и все оценки, полученные таким образом, гарантия асимптотическая: один лишь показатель не говорит, начиная с какого размера матриц новый алгоритм действительно обгонит существующие. Меняется другое — лучший известный ответ на вопрос, который задают с 1969 года: насколько быстро в принципе можно перемножать таблицы чисел?