2025-11-27T11:04:19.442540

A non-commutative algorithm for multiplying 4x4 matrices using 48 non-complex multiplications

Dumas, Pernet, Sedoglavic

The quest for non-commutative matrix multiplication algorithms in small dimensions has seen a lot of recent improvements recently. In particular, the number of scalar multiplications required to multiply two $4\times4$ matrices was first reduced in \cite{Fawzi:2022aa} from 49 (two recursion levels of Strassen's algorithm) to 47 but only in characteristic 2 or more recently to 48 in \cite{alphaevolve} but over complex numbers. We propose an algorithm in 48 multiplications with only rational coefficients, hence removing the complex number requirement. It was derived from the latter one, under the action of an isotropy which happen to project the algorithm on the field of rational numbers. We also produce a straight line program of this algorithm, reducing the leading constant in the complexity, as well as an alternative basis variant of it, leading to an algorithm running in $7 n^{2+\frac{\log_2 3}{2}} +o\left(n^{2+\frac{log_2 3}{2}}\right)$ operations over any ring containing an inverse of 2.

academic

非可換アルゴリズムによる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
所属機関: グルノーブル・アルプス大学(Dumas & Pernet)、リール大学(Sedoglavic)
分類: cs.SC(記号計算)
発表日: 2025年11月27日(arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2506.13242

要約

本論文は、4×4行列乗算を48回のスカラー乗算で計算する非可換アルゴリズムを提案している。本アルゴリズムは有理数係数のみを使用し、複素数を必要としない。これはAlphaEvolve11が提案した複素数域アルゴリズムの改善であり、等方性変換(isotropy)を通じて有理数域に投影されたものである。論文はまた直線プログラム(straight-line program)実装を提供し、2の逆元を含む任意の環上で $7n^{2+\frac{\log_2 3}{2}} + o(n^{2+\frac{\log_2 3}{2}})$ の演算複雑度を実現する代替基変体を示している。

研究背景と動機

問題背景

中心的課題: 小次元行列乗算の最適な非可換アルゴリズムを探索すること、特に必要なスカラー乗算の回数を削減すること。行列乗算はコンピュータ科学と数値計算の基本演算であり、その効率は多くのアプリケーションのパフォーマンスに直接影響する。
重要性:
- 行列乗算の時間複雑度は線形代数計算、機械学習、科学計算などの分野の効率に直接影響する
- Strassen アルゴリズム(1969)は複雑度を初めて $O(n^3)$ から $O(n^{2.81})$ に低下させ、高速行列乗算研究の時代を開いた
- 小次元行列乗算アルゴリズムは大規模行列への再帰的適用を通じて実用的価値を持つ
既存手法の限界:
- Strassen アルゴリズムは4×4行列上で49回の乗算が必要(2層の再帰)
- Fawzi等5は標数2の体上で47回の乗算を実現した
- AlphaEvolve11は大規模言語モデルと進化的コーディングエージェントを使用して48回の乗算アルゴリズムを発見したが、複素数係数が必要である
- 複素数係数は整数環や有限体などの特定の環上でのアルゴリズム適用を制限する
研究動機:
- 複素数要件を排除し、より広範な代数構造上でアルゴリズムを適用可能にする
- テンソル分解理論における対称性(等方性群作用)を利用して系統的にアルゴリズムを変換する
- 実用的な直線プログラム実装を提供し、定数項を最適化する

核心的貢献

主要な理論的貢献: AlphaEvolve アルゴリズムの等方性軌道(isotropy orbit)に有理数点が存在することを証明し、48回の乗算を持つ純粋な有理数係数アルゴリズムを提案した
方法論的貢献: テンソル分解の等方性群理論を系統的に適用し、等方性変換(式24)を通じて複素数域アルゴリズムを有理数域に投影する
実用的貢献:
- 完全な直線プログラム実装(リスト1-4)を提供し、合計341個の演算を実現
- 理論的複雑度界は $11.65625n^{2.792} - 10.65625n^2$
- 代替基変体を提供し、わずか6個の演算(1+2+3)で $7n^{2.792}$ の複雑度を実現
汎用性: アルゴリズムは2の逆元を含む任意の環に適用可能であり、適用範囲を拡張する
オープンソース実装: すべての行列とコードはPLinOptライブラリで公開されている

方法の詳細

タスク定義

入力: 2つの4×4行列 $A = (a_{ij})$ と $B = (b_{ij})$ 、要素は $\frac{1}{2}$ を含む環 $R$ から取得
出力: 積行列 $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)$ はランク1テンソルである
三線形表現は $\text{Trace}(O_i^T \cdot M_i \cdot N_i)$ である

2. Strassen アルゴリズムのテンソル表現

Strassen の2×2行列乗算アルゴリズム(7回の乗算)はテンソルランク7の分解に対応し、型は $X^2Y^2Z^2 + 6XYZ$ である。

3. 等方性群作用(Isotropy Group Action)

定理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)$ がランク1テンソル $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個のランク1テンソルの分解(式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 行列表現

アルゴリズムは3つの行列 $(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$ は要素ごとの乗算(Hadamard積)を表す。

技術的革新点

対称性の系統的利用: 試行錯誤的な探索ではなく、安定化部分群 $(C_2 \times D_4) \rtimes C_2$ と理論的指導による推測を利用して等方性変換を発見する
複素数から有理数への投影: 高次元複素数空間で発見されたアルゴリズムを有理数部分空間に投影できることを証明し、これは非自明な結果である
直線プログラムの最適化:
- PLinOptツールを使用して最適化された直線プログラムを自動生成
- 核分解(kernel decomposition)を通じて演算回数を削減
- $R$ 行列の係数が単純であっても、最適なSLPは非自明な乗算が必要な場合がある
代替基法: 基変換(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: 基変換行列

評価指標

テンソルランク: 必要なスカラー乗算の回数(48)
演算総数: 加算とシフト演算の総数
漸近複雑度: $O(n^{\log_4 3}) \approx O(n^{2.792})$
定数項: 主導定数と低次項の係数

実験結果

主要な結果

標準直線プログラム(リスト1-4)

演算の分解：

$L$ 行列：104回の加算
$R$ 行列：84回の加算 + 1回の乗算(2進シフト)
$P$ 行列：119回の加算 + 33回の乗算(2進シフト)
合計：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})$

既存手法との比較

手法	乗算回数	係数体	適用可能な環	複雑度定数
Strassen (2層)	49	有理数	任意	-
Fawzi et al. 5	47	有理数	標数2	-
AlphaEvolve 11	48	複素数	複素数体	-
本論文(標準)	48	有理数	$\frac{1}{2}$ を含む環	11.66
本論文(代替基)	48	有理数	$\frac{1}{2}$ を含む環	7.00

主要な発見

存在性の証明: AlphaEvolve アルゴリズムの等方性軌道に有理数点が実際に存在することを証明し、これは自明ではない
係数の簡潔性: すべての係数が $\{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$ であり、実装が容易である
最適化のパラドックス: $R$ 行列の係数が $\{-1, 0, 1\}$ のみであっても、最適な直線プログラムは依然として非自明な乗算が必要である(核分解による)
代替基の利点: 基変換を通じて主導定数を11.66から7.00に削減でき、代償は $o(n^{2.792})$ の基変換コストである

AlphaEvolve の複素数アルゴリズムを有理数アルゴリズムに成功裏に変換し、48回の乗算を保持した
等方性群作用はアルゴリズム空間を系統的に探索するための効果的なツールである
2つの実装を提供：標準版(341演算)と代替基版(6+336演算)
アルゴリズムは $\frac{1}{2}$ を含む任意の環に適用可能であり、適用範囲を拡張する

限界

環の制限: 2が可逆である必要があり、標数2の体には適用不可
定数項が大きい: 標準版の定数11.66は大きく、十分に大きな行列上でのみ利点がある
数値安定性が未知: 2と同様の数値精度分析がまだ実施されていない
非構成的: 等方性変換の発見は依然として「教育的推測」に依存し、完全に自動化されていない

今後の方向性

3×4×7アルゴリズム: 姉妹論文3がAlphaEvolveの別の複素数アルゴリズムを処理
数値分析: このアルゴリズムの誤差伝播と条件数を研究
自動化発見: 等方性変換を自動的に探索するための系統的方法を開発
他の次元: 同じ方法を5×5、3×3×3などの場合に適用
実際のパフォーマンス: キャッシュ、並列化などを考慮して実際のハードウェア上でパフォーマンスをテスト

深い評価

利点

1. 理論的貢献が顕著

重要な空白を埋める: AlphaEvolve アルゴリズムの複素数係数制限という実際的な問題を解決
方法論的革新: 等方性群理論を系統的に適用し、複素数から有理数への理論的経路を提供
数学的厳密性: Landsbergのテンソル幾何学理論に基づき、堅実な代数幾何学的基礎を持つ

2. 実用的価値が高い

完全な実装: 直線プログラムとLRP行列を提供し、直接使用可能
オープンソースで再現可能: すべてのデータとコードはPLinOptライブラリで公開
適用性が広い: 有理数係数により、整数、有理数、有限体(奇標数)などで使用可能

3. 技術的詳細が充分

完全なアルゴリズム表示: 式25-72で48個の乗算項すべてを詳細に列挙
複数の表現: 三線形形式、LRP行列、直線プログラムなど複数の表現を提供
最適化戦略: 核分解と代替基などの最適化技術を展示

4. 記述が明確

背景説明が充分: Strassen アルゴリズムからテンソル分解理論まで段階的に導入
例が豊富: 例2.1は等方性がどのように複素数を導入するかを示す
記号が系統化: 定義が明確で、記号が一貫している

不足

1. 方法の限界

等方性変換の発見: 「教育的推測」の使用を認め、系統的な探索方法が欠ける
安定化部分群への依存: 安定化部分群 $(C_2 \times D_4) \rtimes C_2$ が既知である必要があり、新しい問題では取得が困難な可能性
標数制限: 標数2の体には適用不可(Fawziの47回アルゴリズムは反対に使用可能)