T (n) = n^{ω + o (1)}, 2 \leq ω < 2.371177

行列の掛け算の指数ω

Exponent of matrix multiplication

AIの96回を95回にした論文の題に、13人の頭文字が並んだ。

n行n列の行列を掛ける手間の指数。定義どおりなら3、1969年に2.81、2026年に2.371177まで下がった。2に届くかは分かっていない。

年代: 1969〜2026年
習う: 大2・情報科学・分割統治法
レベル: 大学(例題 5 問)
人物: フォルカー・シュトラッセン、ヴィクトル・パン、アルノルト・シェーンハーゲ、ドン・コッパースミス、シュムエル・ウィノグラード、フランソワ・ルガル、ヴァージニア・ヴァシレフスカ・ウィリアムズ、ジョシュ・アルマン、段然、マヌエル・カウアーズ

数学情報科学言語学

逸話

13人の頭文字の題

論文の題に、意味の分からない13個の大文字が並んでいた。「 $Z_{2}^{5 \times 5}$ での掛け算のFBHHRBNRSSSHKアルゴリズムは、まだ物語の終わりではない」。2022年10月8日、オーストリアのヨハネス・ケプラー大学リンツで代数学を研究するマヌエル・カウアーズとヤコブ・モースバウアーが、arXivに公開した短い論文である。13の文字は、3日前に『ネイチャー』に載った論文の、著者13人の頭文字を並べたものだ。

その論文で、DeepMindのAI「AlphaTensor」は、2で割った余りで計算する5行5列の行列どうしの積を、96回の掛け算で済ませる手順を見つけていた。それまでの記録は98回である。カウアーズらは、この手順に変形を重ねて掛け算を1つ消せる形に持ち込み、95回にした。

秋の大学の研究室で、2人の研究者が並んで画面に向かう後ろ姿(画像生成 AI で描いたイメージ) — 2022年10月、ヨハネス・ケプラー大学リンツの2人が、AIの96回の手順を組み替えて95回にした画像生成AIで描いたイメージ

たった1回の掛け算を、なぜAIと人が奪い合うのか。行列を小さな塊に分けて同じ手順をくり返すと、1回の差が、大きな行列での手間の増え方そのものを変えるからだ。 $n$ 行 $n$ 列の行列の積にかかる手間は、およそ $n^{ω}$ に比例する。指数 $ω$ は、定義どおりなら3だが、1969年に2.81以下、2026年8月には2.371177より小さいことが示された。2より小さくならないことは分かっているものの、2に届くかどうかは分かっていない。

DeepMindの解説によると、AlphaTensorは囲碁のAlphaZeroを土台に、3次元に並んだ数を1手ずつ0に消していく1人遊びとして手順を探した。消し終えるまでの手数が、掛け算の回数になる。

いちばん注目されたのは、4行4列の積だった。積の順序を入れ替えない手順では、シュトラッセンの手順を2段重ねた49回より少ないものは知られていなかった。AlphaTensorは47回の手順を見つけた。ただし、計算はすべて2で割った余りで行う。 $1 + 1$ を0とみなす世界でだけ正しい手順である。公開された47回の手順を当サイトで確かめると、2を法とすれば4,096個の係数がすべて合い、整数のままでは465個が合わなかった。

2で割った余りを使わない計算でも1回減ったのは、2025年5月である。Google DeepMindはAlphaEvolveを発表した。言語モデルのGeminiにプログラムを書き換えさせ、改良を重ねていく仕組みである。これを使って、複素数を成分にもつ4行4列の行列どうしを48回の掛け算でかける手順が見つかった。複素数の行列に限った話だが、シュトラッセンの手順を56年ぶりに上回ったことになる。

人の返事は、今度も早かった。約1か月後の6月16日、グルノーブル・アルプ大学のジャン＝ギヨーム・デュマとクレマン・ペルネ、リール大学のアレクサンドル・セドグラヴィックが、複素数を使わない48回の手順を公開した。係数は0と±1、±1/2、±1/4、±1/8だけで、2で割ることのできる数の世界なら、どこでも使える。この手順も当サイトで、 $A$ と $B$ の成分を1つずつ1にした256通りについて確かめると、48個の積から、ふつうの積がそのまま組み上がった。AIの見つけた手順が人の手ですぐに磨かれるのは、正しいかどうかを計算機で確かめられる問題だからだろう。

AIは2026年、指数そのものにも手を伸ばした。8月17日、Google DeepMindの研究者7人と、マサチューセッツ工科大学（MIT）のヴァージニア・ヴァシレフスカ・ウィリアムズ、コロンビア大学のジョシュ・アルマンら10人が、短い論文を公開した。指数の上界を、2.371339から2.371177へ下げたのである。

解析の方法そのものは変えていない。上界は、2024年にアルマンらが立てた大きな最適化の問題の解から決まる。研究チームは、誤差逆伝播法と同じ自動微分で勾配を求めてこの問題を解き、解析の段を1つ深くして、変数を約2万5,000個から約700万個に増やした。これだけで上界は約0.000097下がった。さらにAlphaEvolveに最適化のプログラムを書き換えさせ、1台のGPUで1回5時間ほどの計算をくり返して、下げ幅を0.000162に広げた。最後の値は、丸めの誤差が入らない有理数の計算で確かめてある。

研究所のセミナー室で、黒板の前に集まって話し合う人々の後ろ姿(画像生成 AI で描いたイメージ) — 2025年秋、サイモンズ研究所の研究プログラムで交わした会話が、2026年の改良の始まりになった（論文の謝辞による）画像生成AIで描いたイメージ

論文の謝辞によると、きっかけは2025年秋、カリフォルニア大学バークレー校のサイモンズ研究所で開かれた「計算量と線形代数」の研究プログラムでの会話だった。著者たちは、この方法でさらに少し下げる余地はあるものの、大きく下げるにはおそらく新しい数学の考えが要ると見ている。

小さな改良を主張する論文は、すぐに出た。10月6日、マトロイド社のレザ・ザデーが、同じ枠組みのまま最適化をやり直し、2.37115924まで下げたとする論文を公開した。数値の探索とプログラム作りに生成AIのツールを使ったと、謝辞で断っている。まだ査読を経ていない1人の主張なので、この記事の冒頭の式は、アルマンら6人が論文の改訂版に載せた2.371177のままにした。

小さな行列の記録を指数に直すと、道の違いがはっきりする。4行4列を47回なら $lo g_{4} 47 \approx 2.777$ 、48回なら $lo g_{4} 48 \approx 2.792$ で、どちらも1969年の2.807を下回る。でも、2.371には遠い。

では、2.37という値は、どこから来たのだろうか。

起源

3ページの論文と、20年の足踏み

始まりは、1969年8月に学術誌『Numerische Mathematik』に載った3ページの論文である。著者のフォルカー・シュトラッセンは、確率論で名を上げたあと、前の年にチューリッヒ大学の応用数学研究所へ移ったばかりだった。

フォルカー・シュトラッセン1936–2行2列の行列の積を7回の掛け算で済ませ、指数を3から下げた

題は「ガウスの消去法は最適ではない」で、この題には相手がいた。論文が引くソ連のクリュエフとココフキン＝シチェルバクの研究は、1965年に英訳が出ていて、連立1次方程式を解くにはおよそ $n^{3} /3$ 回の掛け算がどうしても要る、としていた。シュトラッセンは2行2列の積を7回の掛け算で済ませ、それをくり返せば、連立方程式も $n^{l o g_{2} 7}$ に比例する回数で解けることを示した。

2つの結果は、どちらも正しい。カリフォルニア大学バークレー校のジェームズ・デメルは2013年の報告で、許した計算の型が違うからだと説明している。シュトラッセンの手順は、1965年の証明が考えた型の外にあった。

7回より減らすことはできない。

1971年、ジョン・ホップクロフトとカーは、掛け算の順序を入れ替えない手順では、2行2列の積に7回が最少だと証明した。つまり、指数を下げる道は、もっと大きな行列の手順を探すか、数え方そのものを変えるかに絞られた。

1978年、ヴィクトル・パンは指数を2.796未満にした。1980年の論文には、70行70列の積を143,640回の掛け算で済ませる手順が載っている。翌年、ダリオ・ビーニらは、ごく小さな数 $ε$ を混ぜて積を近似する手順を考え、2.78にした。近似の手順でも、行列を大きくしていけば指数を抑えられる。1981年にはアルノルト・シェーンハーゲが、大きさの違う行列の積の組をまとめて扱う漸近和不等式で2.522に、続いてコッパースミスとウィノグラードが、初めて2.5を切る2.496にした。

決定打は、1986年にシュトラッセンが考えたレーザー法だった。行列の積そのものではなく、扱いやすい形をした大きな数の配列（テンソル）を何乗もして、その中から互いに重ならない行列の積を数多く取り出し、漸近和不等式で指数に直す。1987年、ドン・コッパースミスとシュムエル・ウィノグラードは、シュトラッセンの配列に手を加えた配列でこれを行い、2.3754770を得た。

数字は、そこで20年以上止まる。

2010年にアンドリュー・ストザーズがエディンバラ大学の博士論文で配列の4乗を解析して2.3736898に、2012年にヴァシレフスカ・ウィリアムズが8乗を計算機で解析して2.3729に下げた。2014年のフランソワ・ルガルは2.3728639、2020年のアルマンとヴァシレフスカ・ウィリアムズは2.3728596である。名古屋大学のルガルは2024年、『Quanta Magazine』の取材に、1987年からの改良は「小さく、……得るのがきわめて難しい」ものだったと語っている。

ヴァージニア・ヴァシレフスカ・ウィリアムズ21世紀に活躍行列の積の指数の上界を、2012年から何度も下げてきた

流れを変えたのは、清華大学の段然とレンフェイ・ジョウ（Renfei Zhou）、カリフォルニア大学バークレー校のホンシュン・ウー（Hongxun Wu）の3人である。2022年10月、3人は、これまでの解析が取り出せるはずの積を捨てすぎていたことを突き止め、指数を2.371866まで下げた。ジョウは同じ取材で、この損失を「意図せずに、塊を消しすぎた結果」と説明している。下げ幅は約0.001で、2010年のストザーズ以来の大きさだった。

段然21世紀に活躍有向グラフの最短経路で、ダイクストラ法の時間の上界を初めて下回った

そこからは、同じ考えを詰めていく競争になった。2023年にヴァシレフスカ・ウィリアムズらが2.371552を、2024年4月にはアルマン、段然、ヴァシレフスカ・ウィリアムズら6人が2.371339を得た。3つある向きのうち2つを同じに扱うという、それまでの解析の前提を外した結果で、2025年1月の国際会議SODAで発表された。2026年8月の改訂版は、Google DeepMindとの論文で解き直した2.371177を載せている。

ただ、この道の先には行き止まりも見えている。2015年、アンドリス・アンバイニス、ユヴァル・フィルムス、ルガルは、コッパースミスとウィノグラードの配列にレーザー法を使う限り、2.3078より下には行けないことを証明した。

証明

7つの積を組み直す

2行2列のブロックに分けた積で、7回の掛け算から正しい答えが組み上がることを確かめ、それをくり返したときの回数を数える。

$n$ 行 $n$ 列の積 $C = A B$ の成分は、定義どおりなら $n$ 個の積の和で、全体で $n^{3}$ 回の掛け算になる。
$c_{ij} = k = 1 \sum n a_{ik} b_{k j}$
$n$ を偶数とし、 $A$ , $B$ , $C$ を $n /2$ 行 $n /2$ 列のブロック4つずつに分ける。どのブロックも2つのブロックの積の和になり、ブロックの掛け算は8回いる。
$C_{11} = A_{11} B_{11} + A_{12} B_{21}, C_{12} = A_{11} B_{12} + A_{12} B_{22}$
4行4列の行列を太線で4つのブロックに分ける。Cの左上のブロックには、Aの上の行のブロック2つと、Bの左の列のブロック2つが使われる。
シュトラッセンの7つの積を作る。どれも、 $A$ のブロックの和か差と、 $B$ のブロックの和か差の積である。
$M_{1} M_{2} M_{3} M_{4} M_{5} M_{6} M_{7} = (A_{11} + A_{22}) (B_{11} + B_{22}) = (A_{21} + A_{22}) B_{11} = A_{11} (B_{12} - B_{22}) = A_{22} (B_{21} - B_{11}) = (A_{11} + A_{12}) B_{22} = (A_{21} - A_{11}) (B_{11} + B_{12}) = (A_{12} - A_{22}) (B_{21} + B_{22})$
4つのブロックを、7つの積の足し引きで組み立てる。
$C_{11} C_{12} C_{21} C_{22} = M_{1} + M_{4} - M_{5} + M_{7} = M_{3} + M_{5} = M_{2} + M_{4} = M_{1} - M_{2} + M_{3} + M_{6}$
$C_{12}$ を展開すると、 $A_{11} B_{22}$ が打ち消し合う。
$M_{3} + M_{5} = A_{11} B_{12} - A_{11} B_{22} + A_{11} B_{22} + A_{12} B_{22} = A_{11} B_{12} + A_{12} B_{22}$
$C_{11}$ を展開すると、 $M_{1}$ の4つの項のうち3つを、 $M_{4}$ , $M_{5}$ , $M_{7}$ が消す。
$M_{1} + M_{4} - M_{5} + M_{7} = (A_{11} B_{11} + A_{11} B_{22} + A_{22} B_{11} + A_{22} B_{22}) + (A_{22} B_{21} - A_{22} B_{11}) - (A_{11} B_{22} + A_{12} B_{22}) + (A_{12} B_{21} + A_{12} B_{22} - A_{22} B_{21} - A_{22} B_{22}) = A_{11} B_{11} + A_{12} B_{21}$
足し算と引き算を数える。7つの積を作る前に10回、組み立てに8回、ブロックの足し引きが合わせて18回いる。
$T (n) = 7 T (\frac{n}{2}) + 18 (\frac{n}{2})^{2}$
$n = 2^{k}$ として、ブロックが1行1列になるまで分けきる。掛け算の回数は1段ごとに7倍になり、 $k = lo g_{2} n$ なので次のようになる。
$7^{k} = 7^{l o g_{2} n} = n^{l o g_{2} 7} \approx n^{2.807}$
一般に、 $n_{0}$ 行 $n_{0}$ 列の積を、掛け算の順序を入れ替えない $R$ 回の掛け算で計算できれば、同じくり返しから次が言える。
$ω \leq lo g_{n_{0}} R$
下からの抑えも数えるだけで出る。積の成分は $n^{2}$ 個あり、どれも少なくとも1回の演算で書き出さなければならない。
$ω \geq 2$

手順9と手順10で、 $ω$ を上と下から挟んだことになる。 $ω$ は、 $n$ 行 $n$ 列の積を $O (n^{τ})$ 回の演算で計算できる指数 $τ$ を、どこまで小さくできるかの境目の値である。境目ちょうどの $O (n^{ω})$ 回で済む方法があるかは分かっていないので、記事の冒頭の式は $n^{ω + o (1)}$ の形にした。

手順5と手順6では、 $A$ のブロックをいつも左に、 $B$ のブロックを右に置いたまま打ち消し合わせ、積の順序を一度も入れ替えていない。だから、ブロックが行列のままでも式が成り立ち、手順8のくり返しができる。整数の掛け算で4回を3回にしたカラツバの方法とよく似た形で、行列ではこの順序の制約が加わる。残りの $C_{21}$ と $C_{22}$ は例題2で確かめる。

3行3列なら、1976年のジュリアン・ラダーマンの23回で $lo g_{3} 23 \approx 2.854$ となり、シュトラッセンに届かない。積の順序を入れ替えない手順の最少の回数は、19回以上23回以下としか分かっていない。手順9の形で2.371177を出すには13回以下が要るので（例題4）、3行3列の手順を1つ見つけるだけでは足りない。

2.37台の上界は、別の道から来ている。手順9の $R$ を、ビーニらの近似の手順で数えた回数に置き換え、シェーンハーゲの漸近和不等式で、大きさの違う積の組をまとめて指数に直す。レーザー法では、コッパースミスとウィノグラードの配列を何乗もした巨大な配列から、重ならない積をどれだけ取り出せるかを、確率分布を選ぶ最適化の問題として解く。2024年の2.371339は配列の4乗、2026年の2.371177は8乗を解析した値で、完全な証明は2022年からの論文（45〜87ページ）にある。

途中の計算

2行2列を7回で掛けてみる

数で一度、手を動かす。 $A = (2413)$ 、 $B = (1256)$ とすると、定義どおりなら $A B = (4101638)$ で、掛け算は8回である。

$A$ の対角の和と $B$ の対角の和を掛ける
$M_{1} = (2 + 3) (1 + 6) = 35$
$A$ の下の行の和に $b_{11}$ を掛ける
$M_{2} = (4 + 3) \times 1 = 7$
$a_{11}$ と $B$ の右の列の差で積を作る
$M_{3} = 2 \times (5 - 6) = - 2$
$a_{22}$ に $B$ の左の列の差を掛ける
$M_{4} = 3 \times (2 - 1) = 3$
$A$ の上の行の和と $b_{22}$ の積を求める
$M_{5} = (2 + 1) \times 6 = 18$
$A$ の左の列の差を $B$ の上の行の和に掛ける
$M_{6} = (4 - 2) (1 + 5) = 12$
最後は $A$ の右の列の差と $B$ の下の行の和の積
$M_{7} = (1 - 3) (2 + 6) = - 16$
7つの積の値と、それぞれをどの成分に足すか引くかを表にした。M1はc11とc22に、M5はc11から引いてc12に足す。列ごとに合計すると4、16、10、38になる。
左上の成分を組み立てる
$c_{11} = 35 + 3 - 18 - 16 = 4$
右上は2つの積の和になる
$c_{12} = - 2 + 18 = 16$
左下も2つの積を足す
$c_{21} = 7 + 3 = 10$
右下は4つの積を足し引きする
$c_{22} = 35 - 7 - 2 + 12 = 38$

掛け算は7回で済んだ。

そのかわり、足し算と引き算は定義どおりの4回から18回に増えている。数どうしの2行2列なら明らかに損で、得をするのは、成分が大きな行列で、1回の掛け算が何万回もの演算にあたるときだ。

応用

1,000行より手前で効く

シュトラッセンの方法は、いまも実際の計算機で使われている。2008年にシュトラッセンがクヌース賞を受けたとき、ACMの計算理論の分科会SIGACTは授賞の理由で、密な行列なら30行30列ほどから先で選ばれる方法だと紹介した。

ただ、長いあいだ多くの研究者は、実用に向かないと考えていた。NASAエイムズ研究センターのデビッド・ベイリーらは1990年の論文で、分かれ目は1,000行1,000列を優に超えるという通説を、計算機科学の世界に残る「困った俗説」と呼んでいる。Sun-4などのワークステーションでは16行16列からシュトラッセンのほうが速く、クレイのスーパーコンピュータでも分かれ目は128ほどで、2,048行2,048列の積はほぼ2倍の速さになった。

クレイ 2(NASA エイムズ研究センターのクレイ 2) — クレイ21985年回路を液体に浸して冷やした、1985年のスーパーコンピュータ出典: Wikimedia Commons・NASA / Wade Sisler・Public domain

回数を数えるだけでも、分かれ目は大きく動く。足し算も1回と数えて最後まで分けきると、シュトラッセンの方法が定義どおりの $2 n^{3} - n^{2}$ 回を下回るのは、 $n$ が654を超えてからである。ところが、8行8列まで分けたところで定義どおりの計算に切り替えると、1,024行1,024列の積の演算は、数えると定義どおりの約51%で済む。

数値の誤差の心配もあったが、ベイリーらはニコラス・ハイアムの1989年の解析を引き、定義どおりの方法ほど安定ではないものの、多くの用途に足りるとまとめている。

一方、指数が2.37台の手順は、実際の計算に使うためのものではない。ジョウは『Quanta Magazine』の取材に「その方法を計算機で動かすことはない。解析するのだ」と答えている。ベイリーらも1990年に、こうした新しい方法が得になるのは、扱える大きさをはるかに超えた行列だけだろうと見ていた。

AIの計算も、行列の積でできている。トランスフォーマーの注意機構では、点数の表 $Q K^{⊤}$ が、 $n \times d$ と $d \times n$ の行列の積になる。トークンが2,048個、1つのヘッドの次元が128なら、1つのヘッドだけで約5億3,700万回の掛け算だ。AlphaTensorは、NVIDIAのV100などで実際に速く動く手順も探し、大きな行列の積を、同じ計算機でよく使われる方法より10〜20%速くした。

例題と解説

回数を数えて指数に直す

例題 1基本定義どおりの回数

3行3列の行列どうしの積を定義どおりに計算するときの、掛け算と足し算の回数を求めよ。また、 $n$ 行 $n$ 列のときの回数を $n$ で表せ。

解説を見る

成分 $c_{ij} = a_{i 1} b_{1 j} + a_{i 2} b_{2 j} + a_{i 3} b_{3 j}$ は、掛け算3回と足し算2回でできる。成分は9個あるので、掛け算は $9 \times 3 = 27$ 回、足し算は $9 \times 2 = 18$ 回である。

$n$ 行 $n$ 列では、成分 $n^{2}$ 個のそれぞれに掛け算 $n$ 回と足し算 $n - 1$ 回がいる。

掛け算 n^{3} 回, 足し算 n^{2} (n - 1) 回

$n = 3$ を入れると27回と18回に戻る。

例題 2基本残り2つのブロック

証明の手順3の7つの積を使って、 $C_{21} = M_{2} + M_{4}$ と $C_{22} = M_{1} - M_{2} + M_{3} + M_{6}$ が、それぞれ $A_{21} B_{11} + A_{22} B_{21}$ と $A_{21} B_{12} + A_{22} B_{22}$ に等しいことを確かめよ。積の順序は入れ替えないこと。

解説を見る

$C_{21}$ は、 $A_{22} B_{11}$ が打ち消し合う。

M_{2} + M_{4} = A_{21} B_{11} + A_{22} B_{11} + A_{22} B_{21} - A_{22} B_{11} = A_{21} B_{11} + A_{22} B_{21}

$C_{22}$ は、4つの積を展開して並べる。

M_{1} - M_{2} M_{3} M_{6} = A_{11} B_{11} + A_{11} B_{22} + A_{22} B_{11} + A_{22} B_{22} = - A_{21} B_{11} - A_{22} B_{11} = A_{11} B_{12} - A_{11} B_{22} = A_{21} B_{11} + A_{21} B_{12} - A_{11} B_{11} - A_{11} B_{12}

足すと、 $A_{11} B_{11}$ , $A_{11} B_{22}$ , $A_{22} B_{11}$ , $A_{21} B_{11}$ , $A_{11} B_{12}$ がそれぞれ $+$ と $-$ で消え、 $A_{21} B_{12} + A_{22} B_{22}$ が残る。どの項も $A$ のブロックが左にあるので、ブロックが行列でもそのまま成り立つ。

例題 3入試分けきったときの足し算

$n = 2^{k}$ の行列を最後まで分けきるとき、掛け算の回数 $P (k)$ と、足し算と引き算の回数 $S (k)$ は次を満たす。

P (k) = 7 P (k - 1), S (k) = 7 S (k - 1) + 18 \cdot 4^{k - 1}, P (0) = 1, S (0) = 0

（1） $S (k) = 6 (7^{k} - 4^{k})$ を示せ。（2） $n = 8$ のとき、演算の合計を定義どおりの場合と比べよ。

解説を見る

（1） $k$ についての数学的帰納法で示す。 $k = 0$ では $6 (1 - 1) = 0$ で成り立つ。 $k - 1$ で成り立つとすると、

S (k) = 7 \cdot 6 (7^{k - 1} - 4^{k - 1}) + 18 \cdot 4^{k - 1}

= 6 \cdot 7^{k} - 42 \cdot 4^{k - 1} + 18 \cdot 4^{k - 1}

= 6 \cdot 7^{k} - 24 \cdot 4^{k - 1} = 6 (7^{k} - 4^{k})

となり、 $k$ でも成り立つ。

（2） $n = 8$ は $k = 3$ である。シュトラッセンの方法は、掛け算が $7^{3} = 343$ 回、足し算と引き算が $6 (343 - 64) = 1, 674$ 回で、合計2,017回。定義どおりは、例題1の式で掛け算 $8^{3} = 512$ 回、足し算 $8^{2} \times 7 = 448$ 回で、合計960回である。最後まで分けきると、8行8列では約2.1倍に増える。

例題 4難関3行3列の手順と指数

3行3列の積を、積の順序を入れ替えない $R$ 回の掛け算で計算する手順があれば、 $ω \leq lo g_{3} R$ が言える。（1）この不等式でシュトラッセンの $lo g_{2} 7$ より小さい上界が出る $R$ の最大値を求めよ。（2）同じ形で $ω < 2.371177$ を出すには、 $R$ はいくつ以下でなければならないか。

解説を見る

（1） $lo g_{3} R < lo g_{2} 7$ は、両辺を3の指数にして $R < 3^{l o g_{2} 7}$ と同じである。

3^{l o g_{2} 7} = 2^{l o g_{2} 3 \cdot l o g_{2} 7} = 7^{l o g_{2} 3} \approx 7^{1.585} \approx 21.85

$R$ は整数なので、最大は21である。22なら $lo g_{3} 22 \approx 2.814$ で、2.807を超える。

（2） $R < 3^{2.371177} \approx 13.53$ なので、13以下が要る。積の順序を入れ替えない手順では、3行3列の積に19回以上の掛け算がいることを、2003年にマルクス・ブレーザーが証明している。3行3列の手順を1つ見つけるだけでは、2.371177に届かない。

例題 5大学5行5列の95回は指数を下げるか

（1）4行4列の積を49回で計算する手順から出る上界 $lo g_{4} 49$ が、 $lo g_{2} 7$ に等しいことを示せ。（2）カウアーズとモースバウアーは、2を法として5行5列の積を95回で計算する手順を見つけた。この手順から出る上界 $lo g_{5} 95$ を小数第3位まで求め、シュトラッセンの $lo g_{2} 7$ と比べよ。また、5行5列で $lo g_{2} 7$ を下回るには何回以下が要るか。

解説を見る

（1）底を2にそろえる。

lo g_{4} 49 = \frac{lo g _{2} 49}{lo g _{2} 4} = \frac{2 lo g _{2} 7}{2} = lo g_{2} 7

シュトラッセンの手順を2段重ねただけなので、上界は変わらない。

（2） $lo g_{5} 95 = ln 95/ ln 5 \approx 4.5539/1.6094 \approx 2.829$ で、 $lo g_{2} 7 \approx 2.807$ より大きい。2を法とする世界でも、この手順をくり返すだけでは、シュトラッセンの手順を2段重ねた4行4列の49回に負ける。下回るには $R < 5^{l o g_{2} 7}$ が要る。

5^{l o g_{2} 7} = 7^{l o g_{2} 5} \approx 7^{2.3219} \approx 91.7

91回以下でなければならない。5行5列の記録は、それだけでは指数を下げない。

図示

3から2.371177への階段

1969年から2026年までの指数の上界を階段で描いた。1969年のシュトラッセンが2.807、1981年のシェーンハーゲが2.522、1987年のコッパースミスとウィノグラードが2.376まで下げた。その後の改良は、この縮尺では見分けられない。破線は、いまの方法で届く限界の2.3078。

1987年から2026年までを、縦に約170倍に拡大した。20年以上止まったあと、2010年から少しずつ下がり、2022年の段然らの改良で大きな段ができた。

目立つのは、1980年代の数年間の落ち方である。拡大すると、2022年の一段は約0.00099で、2014年から2020年までに下がった約0.000004の200倍を超える。

シミュレーション

段を重ねて開く差

上の段では、2行2列のブロックの積が1つずつできていき、線はその積がどの成分に入るかを表す。定義どおりの積はどれも1つの成分にしか入らないが、シュトラッセンの積の多くは2つの成分に使い回され、破線は引く積である。下の段は、つまみの段の数 $k$ だけ分けたときの掛け算の回数で、比は $k$ を1増やすごとに7/8倍になる。「足し算も数える」を押すと、最後まで分けきったときの足し算を含めた回数に変わり、 $k$ が9までは定義どおりのほうが少ない。

広がる学問

グラフ、文法、テンソルの階数

数学掛け算の最少の回数をテンソルの階数として調べる代数的計算量の理論で、行列の積は中心の問題になる。2行2列の積の階数は7だが、3行3列は19以上23以下としか分かっていない。 $n$ 行 $n$ 列の積の階数が $n$ とともにどれだけ速く増えるかが、そのまま指数 $ω$ になる。
情報科学 グラフの問題を速く解くとき、隣接行列の積に直して計算する。推移閉包はその代表で、辺に重みのない有向グラフの全点対最短経路は、長方形の行列の積の指数を使って $O (n^{2.5275})$ で解ける（2024年のアルマンらの論文）。
言語学 文脈自由文法で文を構文解析するとき、その計算を論理値の行列の積に置き換えると、文の長さの3乗より速く判定できる。1975年にレスリー・ヴァリアントが見つけた方法である。2002年にはリリアン・リーが逆向きの結果を証明した。3乗より大幅に速い構文解析があれば、論理値の行列の積も速くなる。実用的な構文解析がなかなか3乗を切れない理由の説明にもなっている。

いまの研究と事業

使える48回と、2への壁

2026年グルノーブル・アルプ大学とリール大学ほか: デュマ、ペルネ、セドグラヴィックは、ジョシュア・ステープルトン、ペトル・ティハフスキーと、48回の手順を大きな行列にくり返し使うための形を9月に公開した。足し算などの演算を204回にまとめ、全体の手間の主な項を $(7 + 3/8) n^{l o g_{4} 48}$ に抑えている。3月には、誤差の増え方を抑えた版も出している。指数の $lo g_{4} 48 \approx 2.792$ は、証明の手順9で $n_{0} = 4$ , $R = 48$ とした値である。出典はarXiv:2609.12027とarXiv:2603.18699。
2025年芝浦工業大学と理化学研究所: 尾崎克久ら3人は、AI向けの計算機が得意な8ビット整数の行列の積を組み合わせて、倍精度の浮動小数点数の行列の積を作り出す方法を発表した。NVIDIAのGH200では、倍精度の演算器をそのまま使うより速い。互いに素な $s$ 個の数で割った余りごとに積を1回ずつ求め、中国剰余定理で答えを戻すので、積は $s$ 回で済む。倍精度と同じ程度の精度に、入力を切り分ける従来の方法では28〜35回の積がいたところを、16回で届くと見込んでいる。出典はarXiv:2504.08009。
2023年名古屋大学: ルガルは、段然らが見つけた損失の考えを長方形の行列の積に広げ、 $n \times n^{k}$ と $n^{k} \times n$ の積の指数 $ω (1, k, 1)$ の上界を下げた。この指数が下がると、全点対最短経路のようなグラフの問題の手間も下がる。論文は2024年1月のSODAで発表された。出典はarXiv:2307.06535。
2021年ジョシュ・アルマン: アルマンは、レーザー法や群論を使う方法を含む「普遍的な方法」の限界を調べた。コッパースミスとウィノグラードの配列に使う限り、上界は2.16805より下がらないことを、学術誌『Theory of Computing』で示している。2024年のアルマンらの論文によれば、ほかの研究と合わせて、いま知られている方法を大きく一般化しても $ω = 2$ は証明できない。下限の2と上界の2.371177のあいだを詰めるには、配列から積を取り出すのとは別の考えが要るのかもしれない。出典はarXiv:1812.08731とarXiv:2404.16349の序文。

参考文献

V. Strassen, "Gaussian elimination is not optimal", Numerische Mathematik 13(4) (1969), 354-356（引用文献にV. V. Klyuev, N. I. Kokovkin-Shcherbak, Stanford University CS 24（1965））; J. E. Hopcroft, L. R. Kerr, "On Minimizing the Number of Multiplications Necessary for Matrix Multiplication", SIAM J. Appl. Math. 20(1) (1971), 30-36; J. Demmel, UCB/EECS-2013-126 (2013); MacTutor History of Mathematics, "Volker Strassen".
M. Bläser, "Fast Matrix Multiplication", Theory of Computing Library, Graduate Surveys 5 (2013), 1-60; J. D. Laderman, Bull. Amer. Math. Soc. 82(1) (1976), 126-128; M. Bläser, J. Complexity 19(1) (2003), 43-60; D. Bini, M. Capovani, F. Romani, G. Lotti, Inform. Process. Lett. 8(5) (1979), 234-235.
D. Coppersmith, S. Winograd, "Matrix multiplication via arithmetic progressions", J. Symbolic Comput. 9(3) (1990), 251-280; V. Vassilevska Williams, "Multiplying matrices in O(n^2.373) time"（2014年7月1日版）; F. Le Gall, "Powers of Tensors and Fast Matrix Multiplication", ISSAC 2014, 296-303; J. Alman, V. Vassilevska Williams, "A Refined Laser Method and Faster Matrix Multiplication", TheoretiCS 3 (2024); A. Ambainis, Y. Filmus, F. Le Gall, "Fast Matrix Multiplication: Limitations of the Laser Method", STOC 2015（arXiv:1411.5414）.
R. Duan, H. Wu, R. Zhou, "Faster Matrix Multiplication via Asymmetric Hashing", FOCS 2023（arXiv:2210.10173）; V. Vassilevska Williams, Y. Xu, Z. Xu, R. Zhou, "New Bounds for Matrix Multiplication: from Alpha to Omega", SODA 2024（arXiv:2307.07970）; J. Alman, R. Duan, V. Vassilevska Williams, Y. Xu, Z. Xu, R. Zhou, "More Asymmetry Yields Faster Matrix Multiplication", SODA 2025, 2005-2039（arXiv:2404.16349v3, 2026年8月19日）; S. Nadis, "New Breakthrough Brings Matrix Multiplication Closer to Ideal", Quanta Magazine（2024年3月7日）.
A. Fawzi et al., "Discovering faster matrix multiplication algorithms with reinforcement learning", Nature 610 (2022), 47-53; DeepMind, "Discovering novel algorithms with AlphaTensor"（2022年10月5日）とgoogle-deepmind/alphatensor; M. Kauers, J. Moosbauer, "The FBHHRBNRSSSHK-Algorithm for Multiplication in Z_2^{5×5} is still not the end of the story", arXiv:2210.04045 (2022).
A. Novikov et al., "AlphaEvolve: A coding agent for scientific and algorithmic discovery", arXiv:2506.13131 (2025); Google DeepMind, "AlphaEvolve: A Gemini-powered coding agent for designing advanced algorithms"（2025年5月14日）; J.-G. Dumas, C. Pernet, A. Sedoglavic, arXiv:2506.13242（2025）とfmm.univ-lille.frの ⟨4×4×4:48⟩; E. Dupont et al., "Improving the matrix multiplication exponent with modern optimization and AlphaEvolve", arXiv:2608.16884 (2026); R. Zadeh, "A faster matrix multiplication algorithm through structured optimization", arXiv:2610.10593 (2026).
D. H. Bailey, K. Lee, H. D. Simon, "Using Strassen's algorithm to accelerate the solution of linear systems", J. Supercomputing 4 (1990), 357-371; D. H. Bailey, SIAM J. Sci. Stat. Comput. 9(3) (1988), 603-607; ACM SIGACT, "2008 Knuth Prize"; L. G. Valiant, J. Comput. Syst. Sci. 10(2) (1975), 308-315; L. Lee, J. ACM 49(1) (2002), 1-15.

行列の掛け算の指数ω

13人の頭文字の題

3ページの論文と、20年の足踏み

7つの積を組み直す

2行2列を7回で掛けてみる

1,000行より手前で効く

回数を数えて指数に直す

例題 1基本定義どおりの回数

例題 2基本残り2つのブロック

例題 3入試分けきったときの足し算

例題 4難関3行3列の手順と指数

例題 5大学5行5列の95回は指数を下げるか

3から2.371177への階段

段を重ねて開く差

グラフ、文法、テンソルの階数

使える48回と、2への壁

参考文献

タグ

同じタグを持つ公式

姉妹サイト