Некоммутативный алгоритм умножения матриц 4×4 с использованием 48 скалярных умножений

Основная информация

• ID статьи: 2506.13242
• Название: A non-commutative algorithm for multiplying 4×4 matrices using 48 non-complex multiplications
• Авторы: Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic
• Учреждения: Univ. Grenoble Alpes (Dumas & Pernet), Univ. Lille (Sedoglavic)
• Классификация: cs.SC (Символьные вычисления)
• Дата публикации: 27 ноября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2506.13242

Аннотация

В статье предложен алгоритм вычисления произведения матриц размером 4×4 с использованием 48 скалярных умножений, использующий только рациональные коэффициенты без привлечения комплексных чисел. Это улучшение алгоритма в комплексной области, предложенного AlphaEvolve11, достигнутое путём проектирования на поле рациональных чисел с помощью изотропных преобразований. Статья содержит реализацию в виде прямолинейной программы и предлагает альтернативный вариант базиса, обеспечивающий сложность $7n^{2+\frac{\log_2 3}{2}} + o(n^{2+\frac{\log_2 3}{2}})$ в произвольном кольце, содержащем обратный элемент к 2.

Исследовательский контекст и мотивация

Постановка проблемы

1. Основная задача: Поиск оптимальных некоммутативных алгоритмов умножения матриц малых размеров, в частности снижение требуемого количества скалярных умножений. Умножение матриц является фундаментальной операцией в информатике и численных вычислениях, его эффективность напрямую влияет на производительность многих приложений.
2. Значимость:
   • Временная сложность умножения матриц напрямую влияет на эффективность линейной алгебры, машинного обучения, научных вычислений и других областей
   • Алгоритм Штрассена (1969) впервые снизил сложность с $O(n^3)$ до $O(n^{2.81})$, открыв направление исследований быстрого умножения матриц
   • Алгоритмы умножения матриц малых размеров могут применяться рекурсивно к большим матрицам, имея практическую ценность
3. Ограничения существующих методов:
   • Алгоритм Штрассена требует 49 умножений для матриц 4×4 (две рекурсивные итерации)
   • Fawzi и др.5 достигли 47 умножений в полях характеристики 2
   • AlphaEvolve11 использовал большие языковые модели и эволюционные агенты кодирования для нахождения алгоритма с 48 умножениями, но требует комплексных коэффициентов
   • Комплексные коэффициенты ограничивают применимость алгоритма на некоторых кольцах (целые числа, конечные поля)
4. Исследовательская мотивация:
   • Устранение требования комплексных чисел для расширения применимости алгоритма на более широкий класс алгебраических структур
   • Использование симметрий теории тензорного разложения (действие изотропных групп) для систематического преобразования алгоритмов
   • Предоставление практической реализации в виде прямолинейной программы с оптимизацией константных множителей

Основные вклады

1. Главный теоретический вклад: Доказано существование рациональной точки в изотропной орбите алгоритма AlphaEvolve, предложен алгоритм с 48 умножениями с чисто рациональными коэффициентами
2. Методологический вклад: Систематическое применение теории изотропных групп тензорного разложения, проектирование алгоритма из комплексной области в область рациональных чисел посредством изотропных преобразований (уравнение 24)
3. Практический вклад:
   • Полная реализация в виде прямолинейной программы (Listings 1-4), всего 341 операция
   • Теоретическая граница сложности $11.65625n^{2.792} - 10.65625n^2$
   • Альтернативный вариант базиса, требующий всего 6 операций (1+2+3), с сложностью $7n^{2.792}$
4. Универсальность: Алгоритм применим к любому кольцу, содержащему обратный элемент к 2, расширяя область применения
5. Открытая реализация: Все матрицы и код доступны в библиотеке PLinOpt

Подробное описание метода

Определение задачи

Вход: Две матрицы размером 4×4: $A = (a_{ij})$ и $B = (b_{ij})$, элементы которых принадлежат кольцу $R$, содержащему $\frac{1}{2}$
Выход: Матрица произведения $C = A \cdot B = (c_{ij})$
Ограничения: Минимизация количества скалярных умножений с использованием только рациональных коэффициентов (исключение комплексных чисел)

Теоретическая основа: представление тензорного разложения

1. Тензорное представление билинейного отображения

Умножение матриц может быть представлено как билинейное отображение: $\beta_{mm}: R^{m \times k} \times R^{k \times n} \rightarrow R^{m \times n}, \quad (A, B) \mapsto A \cdot B$

Это отображение кодируется тензорным разложением в пространстве $(R^{m \times k})^* \otimes (R^{k \times n})^* \otimes R^{m \times n}$: $T = \sum_{i=1}^r M_i \otimes N_i \otimes O_i$

где:

• $r$ — ранг тензора (tensor rank), соответствующий требуемому количеству скалярных умножений
• каждый $(M_i, N_i, O_i)$ — тензор ранга один
• трилинейное представление: $\text{Trace}(O_i^T \cdot M_i \cdot N_i)$

2. Тензорное представление алгоритма Штрассена

Алгоритм Штрассена для умножения матриц 2×2 (7 умножений) соответствует разложению тензора ранга 7 типа $X^2Y^2Z^2 + 6XYZ$.

3. Действие изотропной группы

Теорема 2.1: Изотропная группа тензора умножения матриц имеет вид: $\text{psl}_{\pm}(R^m) \times \text{psl}_{\pm}(R^k) \times \text{psl}_{\pm}(R^n) \rtimes S_3$

Определение 2.2: Действие изотропного преобразования $g = (U \times V \times W)$ на тензор ранга один $A \otimes B \otimes C$: $(U^{-T} \cdot A \cdot V^T) \otimes (V^{-T} \cdot B \cdot W^T) \otimes (W^{-T} \cdot C \cdot U^T)$

Это сохраняет ранг тензора неизменным, но изменяет коэффициенты.

Построение основного алгоритма

Ключевое изотропное преобразование

Основная инновация статьи — нахождение специфического изотропного преобразования (уравнение 24): $\begin{bmatrix} I & 0 & 0 & I \\ 0 & 1 & I & 0 \\ 0 & -I & -1 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} I & 0 & 0 & 1 \\ 0 & -I & -I & 0 \\ 0 & -I & I & 0 \\ -I & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

где $I$ — мнимая единица.

Тензорное разложение с рациональными коэффициентами

После применения указанного преобразования получается разложение на 48 тензоров ранга один (уравнения 25-72), каждый имеет вид: $m_i = \left(\sum_{j,k} \alpha_{jk}^{(i)} a_{jk}\right) \otimes \left(\sum_{j,k} \beta_{jk}^{(i)} b_{jk}\right) \otimes \left(\sum_{j,k} \gamma_{jk}^{(i)} c_{jk}\right)$

Ключевые свойства:

• Все коэффициенты $\alpha, \beta, \gamma \in \{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$ (рациональные числа)
• Тип тензора: $16X^2Y^2Z^2 + 32XYZ$ (16 тензоров ранга 2×2×2, 32 тензора ранга 1×1×1)
• Знаменатели содержат только степени 2, 4, 8

Пример: первый член умножения

$m_1 = \frac{1}{4}\left(\sum_{i,j} (-1)^{i+j+1} a_{ij}\right) \otimes (b_{31} + b_{41}) \otimes \left(\sum c_{terms}\right)$

Матричное представление LRP

Алгоритм может быть компактно представлен тремя матрицами $(L, R, P)$:

• $L \in R^{48 \times 16}$: линейное преобразование элементов матрицы $A$ в 48 левых операндов
• $R \in R^{48 \times 16}$: линейное преобразование элементов матрицы $B$ в 48 правых операндов
• $P \in R^{16 \times 48}$: линейное преобразование 48 произведений в элементы матрицы $C$

Поток вычислений: $\text{vec}(C) = P \cdot (L \cdot \text{vec}(A) \odot R \cdot \text{vec}(B))$

где $\odot$ обозначает поэлементное произведение (произведение Адамара).

Технические инновации

1. Систематизированное использование симметрий: Вместо поиска методом проб и ошибок используется теория стабилизаторов $(C_2 \times D_4) \rtimes C_2$ и теоретически обоснованные предположения для нахождения изотропного преобразования
2. Проектирование из комплексных чисел в рациональные: Доказано, что алгоритм, найденный в высокомерном комплексном пространстве, может быть спроектирован в подпространство рациональных чисел — нетривиальный результат
3. Оптимизация прямолинейной программы:
   • Использование инструмента PLinOpt для автоматического генерирования оптимизированной прямолинейной программы
   • Снижение количества операций через разложение ядра (kernel decomposition)
   • Даже при простых коэффициентах матрицы $R$ оптимальная SLP может требовать нетривиальных умножений
4. Альтернативный метод базиса: Дальнейшее упрощение через замену базиса (change of basis) сокращает операции до 336 (в сравнении с исходными 341)

Экспериментальная установка

Инструменты реализации

• Библиотека PLinOpt: Набор процедур на C++ для оптимизации линейных и билинейных программ
• Объём кода: Примерно 8.09 тысяч строк исходного кода (kSLOC)
• Открытый исходный код: Все матрицы и код доступны на GitHub

Файлы данных

Различные представления алгоритма хранятся как:

• 4x4x4_48_rational_L.sms, _R.sms, _P.sms: стандартное представление LRP
• 4x4x4_48_rational-ALT_*.sms: альтернативное представление базиса
• 4x4x4_48_rational-CoB_*.sms: матрицы замены базиса

Метрики оценки

1. Ранг тензора: Требуемое количество скалярных умножений (48)
2. Общее количество операций: Суммарное количество операций сложения и сдвига
3. Асимптотическая сложность: $O(n^{\log_4 3}) \approx O(n^{2.792})$
4. Константные множители: Коэффициент при главном члене и коэффициенты младших членов

Результаты экспериментов

Основные результаты

Стандартная прямолинейная программа (Listings 1-4)

Разложение операций:

• Матрица $L$: 104 операции сложения
• Матрица $R$: 84 операции сложения + 1 операция умножения (двоичный сдвиг)
• Матрица $P$: 119 операций сложения + 33 операции умножения (двоичный сдвиг)
• Итого: 341 операция

Граница сложности: $\left(1 + \frac{341}{48-16}\right)n^{2+\log_4 3} - \frac{341}{32}n^2 \approx 11.65625n^{2.792} - 10.65625n^2$

Альтернативный вариант базиса (Приложение C)

Разложение операций:

• $L_{alt}$: 1 операция сложения
• $R_{alt}$: 2 операции сложения
• $P_{alt}$: 3 операции сложения
• Итого: 6 операций

Затраты на замену базиса:

• CoB_L: 103 операции сложения
• CoB_R: 79 операций сложения + 5 операций умножения
• CoB_P: 116 операций сложения + 33 операции умножения
• Итого: 336 операций

Граница сложности: $7n^{2.792} + \frac{336}{31}(n^{\log_4 47} - n^2) = 7n^{2.792} + o(n^{2.792})$

Сравнение с существующими методами

Ключевые находки

1. Доказательство существования: Доказано, что в изотропной орбите алгоритма AlphaEvolve действительно существует рациональная точка, что не является очевидным
2. Простота коэффициентов: Все коэффициенты принадлежат множеству $\{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$, что облегчает реализацию
3. Парадокс оптимизации: Хотя матрица $R$ содержит только коэффициенты из $\{-1, 0, 1\}$, оптимальная прямолинейная программа всё равно требует нетривиальных умножений (из-за разложения ядра)
4. Преимущество альтернативного базиса: Замена базиса позволяет снизить главную константу с 11.66 до 7.00, при этом затраты на замену базиса составляют $o(n^{2.792})$

Связанные работы

История быстрого умножения матриц

1. Штрассен (1969): Первый алгоритм $O(n^{2.81})$, 7 умножений для матриц 2×2
2. де Гроот (1978): Исследование изотропных групп и алгебраической геометрии оптимальных алгоритмов
3. Теорема 2.2: Доказано, что все алгоритмы с 7 умножениями для матриц 2×2 образуют единую орбиту

Недавние достижения

1. Fawzi и др. (2022) 5: Использование обучения с подкреплением для открытия алгоритма с 47 умножениями в характеристике 2
2. Kaporin (2024) 8: Использование нелинейного метода наименьших квадратов для решения уравнений Брента в комплексной области
3. AlphaEvolve (2025) 11: Использование больших языковых моделей и эволюционных агентов для открытия алгоритма с 48 умножениями (комплексный) и 63 умножениями (3×4×7)

Исследования численной стабильности

• Dumas и др. (2024) 2: Исследование численной точности алгоритма Штрассена, обнаружено, что он не является оптимальным по точности
• Численный анализ предложенного алгоритма остаётся предметом будущих исследований

Преимущества данной работы

1. Теоретическая строгость: Основано на теории изотропных групп, а не на чистом эвристическом поиске
2. Универсальность: Рациональные коэффициенты делают алгоритм применимым к более широкому классу алгебраических структур
3. Воспроизводимость: Полное матричное представление и открытая реализация

Заключение и обсуждение

Основные выводы

1. Успешно преобразован алгоритм AlphaEvolve из комплексной области в область рациональных чисел с сохранением 48 умножений
2. Действие изотропной группы является эффективным инструментом для систематического исследования пространства алгоритмов
3. Предоставлены две реализации: стандартная версия (341 операция) и альтернативный базис (6+336 операций)
4. Алгоритм применим к любому кольцу, содержащему $\frac{1}{2}$, расширяя область применения

Ограничения

1. Ограничения на кольцо: Требуется обратимость 2, не применимо к полям характеристики 2
2. Большие константные множители: Константа 11.66 в стандартной версии велика, преимущество проявляется только для достаточно больших матриц
3. Неизвестная численная стабильность: Анализ численной точности, подобный 2, ещё не проведён
4. Неконструктивность: Открытие изотропного преобразования всё ещё опирается на "обоснованные предположения", полная автоматизация не достигнута

Направления будущих исследований

1. Алгоритм 3×4×7: Сопутствующая статья 3 рассматривает другой комплексный алгоритм AlphaEvolve
2. Численный анализ: Исследование распространения ошибок и числа обусловленности алгоритма
3. Автоматизированное открытие: Разработка систематических методов автоматического поиска изотропных преобразований
4. Другие размерности: Применение аналогичного метода к матрицам 5×5, 3×3×3 и т.д.
5. Практическая производительность: Тестирование производительности на реальном оборудовании с учётом кэша, параллелизма и других факторов

Глубокая оценка

Достоинства

1. Значительный теоретический вклад

• Заполнение важного пробела: Решена проблема ограничения комплексных коэффициентов алгоритма AlphaEvolve, имеющая практическое значение
• Методологическая инновация: Систематическое применение теории изотропных групп, предоставлено теоретическое обоснование пути от комплексных чисел к рациональным
• Математическая строгость: Основано на теории тензорной геометрии Ландсберга с прочной алгебро-геометрической базой

2. Высокая практическая ценность

• Полная реализация: Предоставлены прямолинейная программа и матрицы LRP, готовые к использованию
• Открытая воспроизводимость: Все данные и код доступны в библиотеке PLinOpt
• Широкая применимость: Рациональные коэффициенты позволяют использовать алгоритм на целых числах, рациональных числах, конечных полях нечётной характеристики и т.д.

3. Достаточная детализация технических аспектов

• Полное представление алгоритма: Уравнения 25-72 детально перечисляют все 48 членов умножения
• Множественные представления: Предоставлены трилинейная форма, матрицы LRP, прямолинейная программа и другие представления
• Стратегии оптимизации: Продемонстрированы методы разложения ядра и альтернативного базиса

4. Ясное изложение

• Достаточное введение: От алгоритма Штрассена к теории тензорного разложения — пошаговое введение
• Богатые примеры: Пример 2.1 демонстрирует, как изотропное преобразование вводит комплексные числа
• Систематизированная нотация: Чёткие определения, последовательное использование символов

Недостатки

1. Ограничения метода

• Открытие изотропного преобразования: Признано использование "обоснованных предположений", отсутствует систематический метод поиска
• Зависимость от стабилизатора: Требуется знание стабилизатора $(C_2 \times D_4) \rtimes C_2$, что может быть затруднительно для новых задач
• Ограничение характеристики: Не применимо к полям характеристики 2 (алгоритм Fawzi с 47 умножениями, напротив, применим)

2. Недостаточный экспериментальный анализ

• Отсутствие тестирования на реальном оборудовании: Не проведено тестирование времени выполнения на реальных системах
• Отсутствие анализа численной стабильности: Признано как предмет будущих работ, но важно для практических приложений
• Отсутствие количественного сравнения констант: Не проведено детальное сравнение константных множителей с другими алгоритмами

3. Недостаточная глубина теории

• Неполное доказательство существования: Показана только одна рациональная точка, не доказаны её единственность или оптимальность
• Неисследованная структура орбиты: Вопросы о положении рациональной точки в орбите, количестве рациональных точек остаются открытыми
• Отсутствие обсуждения нижних границ: Не рассмотрены теоретические нижние границы для умножения матриц 4×4 (возможно ли <48?)

4. Детали представления

• Сложная нотация: Обилие индексов и тензорных обозначений может быть затруднительно для неспециалистов
• Недостаток комментариев в коде: Прямолинейные программы (Listings 1-4) лишены пояснительных комментариев
• Сложность восприятия матриц: Большие матрицы в Приложении B трудны для прямого понимания их структуры

Влияние на область

Вклад в развитие науки

1. Мост между теорией и практикой: Преобразование алгоритма, открытого ИИ, в математически обоснованную форму
2. Методологический пример: Демонстрация практического применения теории изотропных групп в оптимизации алгоритмов
3. Вдохновение для будущих исследований: Предоставление шаблона для обработки других комплексных алгоритмов, открытых ИИ

Практическая ценность

1. Средняя: Из-за больших константных множителей (11.66) преимущество проявляется только для крупномасштабных матриц (например, $n > 100$)
2. Специализированные области: Более высокая ценность в системах символьных вычислений, требующих точных рациональных вычислений
3. Образовательное значение: Отличный пример применения теории тензорного разложения и изотропных групп

Воспроизводимость

• Отличная: Полные матрицы, код и инструментарий открыто доступны
• Удобство использования: Библиотека PLinOpt предоставляет инструменты для автоматического генерирования прямолинейных программ
• Полная документация: Приложения содержат подробный список всех файлов данных и их расположения

Сценарии применения

Идеальные сценарии применения

1. Системы символьных вычислений: Точные матричные операции в Maple, Mathematica и подобных системах
2. Вычисления в конечных полях: Линейная алгебра над конечными полями нечётной характеристики
3. Крупномасштабные матрицы: Рекурсивное применение к матрицам размером $n \geq 128$
4. Теоретические исследования: Инструмент для исследования быстрых алгоритмов и тензорного ранга

Неприменимые сценарии

1. Малые матрицы: Для отдельных матриц 4×4 наивный алгоритм (64 умножения) может быть быстрее из-за меньших константных множителей
2. Вычисления с плавающей точкой: Численная стабильность неизвестна, может быть хуже традиционных алгоритмов
3. Поля характеристики 2: Алгоритм Fawzi с 47 умножениями более оптимален
4. Аппаратное ускорение: Оптимизированное умножение матриц на современных GPU может быть быстрее

Список литературы

Ключевые ссылки

1. 13 Штрассен (1969): "Gaussian elimination is not optimal" — основополагающая работа по быстрому умножению матриц
2. 6,7 де Гроот (1978): Оригинальные работы по теории изотропных групп
3. 11 Новиков и др. (2025): AlphaEvolve — исходный комплексный алгоритм, улучшенный в данной работе
4. 10 Ландсберг (2016): "Geometry and complexity theory" — теоретическая основа
5. 2 Dumas и др. (2024): Анализ численной точности алгоритма Штрассена

Связанные работы

• 5 Fawzi и др. (2022): Алгоритм с 47 умножениями, открытый обучением с подкреплением (характеристика 2)
• 9 Karstadt & Schwartz (2017): Другие оптимизации умножения матриц
• 4 Dumas и др. (2025): Методы автоматического генерирования быстрых точных алгоритмов
• 3 Dumas и др. (2025): Алгоритм 3×4×7 с 63 умножениями (сопутствующая работа)

Общая оценка

Это высококачественная работа в области теоретической информатики, успешно преобразовавшая алгоритм, открытый ИИ в комплексной области, в алгоритм с рациональными коэффициентами. Работа имеет значительную теоретическую ценность и определённую практическую значимость. Основные достоинства:

1. Решение практической проблемы: Устранено ограничение комплексных коэффициентов AlphaEvolve
2. Строгая методология: Основано на зрелой теории тензорного разложения и изотропных групп
3. Полная реализация: Предоставлена воспроизводимая открытая реализация

Основные недостатки:

1. Открытие изотропного преобразования всё ещё требует ручного подбора
2. Отсутствует анализ практической производительности и численной стабильности
3. Большие константные множители ограничивают практическую применимость

Рекомендуемая оценка: ⭐⭐⭐⭐ (4/5)
Рекомендуется для ознакомления исследователям, интересующимся символьными вычислениями, тензорным разложением и быстрыми алгоритмами. Для практического применения необходимо оценить преимущества в конкретном сценарии использования.