コンピュータ科学者や数学者にとって、「指数XNUMX」についての意見は、世界がどうあるべきかという感覚に要約されます。

「科学的思考と希望的観測を区別するのは難しい」と述べた。 クリス・ウマンス カリフォルニア工科大学の。 「美しいので、指数をXNUMXにしたいと思います。」

「指数XNUMX」は、数学で最も基本的な演算のXNUMXつである行列の乗算を実行する理想的な速度（必要なステップ数の観点から）を指します。 指数XNUMXが達成可能な場合、物理的に可能な限り高速に行列の乗算を実行することが可能です。 そうでなければ、私たちは自分たちの夢に合わない世界で立ち往生しています。

行列は数値の配列です。 互換性のあるサイズのXNUMXつの行列がある場合、それらを乗算してXNUMX番目の行列を生成することができます。 たとえば、XNUMX行XNUMX列の行列のペアから始める場合、それらの積もXNUMXつのエントリを含むXNUMX行XNUMX列の行列になります。 より一般的には、ペアの製品 nバイn 行列は別です nバイn との行列 n² エントリー。

このため、行列のペアを乗算することを期待できる最速のものは次のとおりです。 n² ステップ—つまり、答えを書き留めるだけのステップ数です。 これが「指数XNUMX」の由来です。

そして、それが達成できるかどうかは誰にもわかりませんが、研究者たちはその方向に進歩を続けています。

紙 XNUMX月に投稿 これまでで最も近いものであり、XNUMXつの行列を乗算するための史上最速の方法を説明しています。 結果は、 ジョシュアルマン、ハーバード大学のポスドク研究員、および バージニアウィリアムズ マサチューセッツ工科大学の、以前の最高点の指数から約XNUMX万分のXNUMXを削ります。 これは、この分野での最近の骨の折れる利益の典型です。

このプロセスとその改善方法を理解するために、XNUMX行XNUMX列の行列AとBのペアから始めましょう。製品の各エントリを計算するときは、Aの対応する行と対応する列を使用します。したがって、右上のエントリを取得するには、Aの最初の行の最初の数値にBのXNUMX番目の列の最初の数値を掛けてから、Aの最初の行のXNUMX番目の数値にBのXNUMX番目の列で、これらXNUMXつの製品を足し合わせます。

この操作は、行と列の「内積」を取ることとして知られています。 製品マトリックスの他のエントリを計算するには、対応する行と列で手順を繰り返します。

全体として、XNUMX行XNUMX列の行列を乗算するための教科書の方法では、XNUMX回の乗算といくつかの加算が必要です。 一般的に、XNUMXを掛けるこの方法 nバイn マトリックスは一緒に必要です n³ 途中で乗算。

行列が大きくなると、積を見つけるために必要な乗算の数は、加算の数よりもはるかに速く増加します。 64行16列の行列の積を見つけるにはXNUMX回の中間乗算が必要ですが、XNUMX行XNUMX列の行列の積を見つけるにはXNUMX回かかります。 ただし、これらの行列のセットを追加するために必要な追加の数は、はるかに近くなります。 一般に、加算の数は行列のエントリの数と等しいため、XNUMX行XNUMX列の行列の場合はXNUMX個、XNUMX行XNUMX列の行列の場合はXNUMX個です。 加算と乗算のこの違いは、研究者が行列の乗算の速度を純粋に必要な乗算の数で測定する理由に気づき始めています。

「掛け算がすべてです」とUmansは言いました。 「最終的な実行時間の指数は、乗算の数にのみ完全に依存します。 追加されたものは消えてしまいます。」

何世紀にもわたって人々は考えました n³ 行列の乗算が実行できる最速でした。 1969年、フォルカーシュトラッセンは、XNUMX回未満の乗算を使用してXNUMX行XNUMX列の行列を乗算する方法がないことを証明しようと試みたと報告されています。 どうやら彼は証拠を見つけることができませんでした、そしてしばらくして彼は理由に気づきました：実際にはXNUMXでそれをする方法があります！

Strassenは、これらの14つの乗算のXNUMXつをXNUMXの追加の加算で置き換えることを可能にする、複雑な一連の関係を考え出しました。 それは大きな違いのようには思えないかもしれませんが、加算よりも乗算の重要性のおかげで報われます。 そして、小さなXNUMX行XNUMX列の行列の単一の乗算を保存する方法を見つけることによって、Strassenは、より大きな行列を乗算するときに利用できる開口部を見つけました。

「この小さな改善は、大きなマトリックスでの大きな改善につながります」とウィリアムズは言いました。

たとえば、XNUMX行XNUMX列の行列のペアを乗算するとします。 これを行うXNUMXつの方法は、各大きな行列をXNUMXつのXNUMX行XNUMX列の行列に分割することです。したがって、それぞれにXNUMXつのエントリがあります。 行列はそれ自体が行列であるエントリを持つこともできるため、元の行列はXNUMX x XNUMXの行列のペアと考えることができ、それぞれのXNUMXつのエントリはそれ自体がXNUMX xXNUMXの行列です。 いくつかの操作により、これらのXNUMX行XNUMX列の行列自体をXNUMXつのXNUMX行XNUMX列の行列に分割できます。

大きな行列を小さな行列に繰り返し分割するというこの削減のポイントは、Strassenのアルゴリズムを小さな行列に何度も適用して、各ステップで彼の方法を節約できることです。 全体として、Strassenのアルゴリズムは行列乗算の速度を n³ 〜へ n^2.81 乗法ステップ。

次の大きな改善は1970年代後半に起こり、問題に取り組むための根本的に新しい方法がありました。 これには、行列の乗算を、テンソルと呼ばれるオブジェクトを含む線形代数の別の計算問題に変換することが含まれます。 この問題で使用される特定のテンソルは、多くの異なる部分で構成される数のXNUMX次元配列であり、それぞれが小さな行列の乗算問題のように見えます。

行列の乗算とテンソルを含むこの問題は、ある意味で互いに同等ですが、研究者はすでに後者を解決するためのより高速な手順を持っていました。 これにより、XNUMXつの間の為替レートを決定するタスクが残りました。テンソル問題を解決するのにかかるのと同じ計算コストで乗算できる行列の大きさはどれくらいですか？

「これは理論計算機科学の非常に一般的なパラダイムであり、問​​題間を減らして、問題が互いに同じくらい簡単または難しいことを示します」とアルマン氏は述べています。

1981年、アーノルドショーンハーゲは​​このアプローチを使用して、行列の乗算を実行できることを証明しました。 n^2.522 ステップ。 Strassenは後に、このアプローチを「レーザー法」と呼びました。

研究者がXNUMXつの問題を変換するためのますます効率的な方法を発見したため、過去数十年にわたって、行列乗算のすべての改善はレーザー法の改善からもたらされました。 新しい証明で、AlmanとWilliamsは、XNUMXつの問題間の摩擦を減らし、特定のサイズのテンソル問題を解くために以前に実現されたよりも多くの行列乗算を「購入」できることを示しています。

「ジョシュとバージニアは基本的に、レーザー法の中に機械を取り入れ、それを微調整してさらに良い結果を得る方法を見つけました」と述べています。 ヘンリーコーン マイクロソフトリサーチの。

この論文は、行列乗算の理論上の速度制限を次のように改善しています。 n^2.3728596.

また、ウィリアムズは、2012年に以前に保持していた行列乗算の王冠を取り戻すことができます（n^2.372873）、その後 2014年に失われました フランソワ・ル・ガルへ（n^2.3728639).

しかし、すべての冗談について、このアプローチが収穫逓減を提供していることも明らかです。 実際、アルマンとウィリアムズの改善は、レーザー法をほぼ限界に達した可能性があります—その究極の理論的目標にははるかに及ばないままです。

「この特定の方法ファミリーを使用して、指数XNUMXに飛躍する可能性は低いです」とUmans氏は述べています。

そこにたどり着くには、新しい方法を発見し、それが可能であるという信念を維持する必要があります。

ウィリアムズは、これについてストラッセンとかつて行った会話を覚えています。「行列の乗算で[指数2]を取得できると彼に尋ねたところ、「いいえ、いいえ、いいえ、いいえ、いいえ」と答えました。」