コンピューター科学者は要求が厳しい集団です。彼らにとって、問題に対する正しい答えを得るだけでは十分ではありません。ほとんどの場合、目標は、できるだけ効率的に答えを見つけることです。

行列、つまり数値の配列を乗算する行為を考えてみましょう。 1812 年、フランスの数学者ジャック フィリップ マリー ビネは、現在でも生徒に教えている基本的な規則を考案しました。これは完全にうまく機能しますが、他の数学者はプロセスを簡素化して高速化する方法を見つけました。今の課題は、 プロセスを早める 行列乗算の進歩は数学とコンピュータ サイエンスの交差点にあり、研究者は今日に至るまでそのプロセスを改良し続けていますが、ここ数十年の進歩はかなり控えめです。 1987 年以来、行列乗算の数値的改善は「わずかであり、実現するのは非常に困難です」と述べています。 フランソワ・ル・ガル、名古屋大学のコンピュータ科学者。

現在、清華大学のラン・ドゥアン氏とレンフェイ・チョウ氏、カリフォルニア大学バークレー校のホンシュン・ウー氏という3人の研究者が、この長年の問題に取り組む上で大きな一歩を踏み出した。彼らの 新しい結果昨年11月にFoundations of Computer Scienceカンファレンスで発表されたこの技術は、予想外の新しい技術から生まれたものだとル・ガル氏は述べた。改善自体は比較的小さかったが、ル・ガール氏は「これまでの改善よりも概念的に大きい」と述べた。

この技術は、これまで知られていなかったため未開発の潜在的な改善の源を明らかにし、すでに実を結んでいます。 2枚目の論文は 1 月に出版され、最初の内容に基づいて、行列の乗算をさらに強化する方法を示しています。

「これは大きな技術的進歩です」と彼は言った ウィリアム・クスマウル、ハーバード大学の理論コンピューター科学者。 「これは、私たちがここ 10 年以上で見た行列乗算の最大の改善です。」

マトリックスに入る

わかりにくい問題のように思えるかもしれませんが、行列の乗算は基本的な計算操作です。これは、より鮮明なコンピュータ グラフィックスの表示からネットワーク理論におけるロジスティック問題の解決に至るまで、さまざまなタスクで人々が毎日使用するアルゴリズムの大部分に組み込まれています。他の計算分野と同様に、速度が最も重要です。わずかな改善でも、最終的には時間、計算能力、コストの大幅な節約につながる可能性があります。しかし今のところ、理論家は主に、プロセスがどれだけ速くなり得るかを解明することに関心を持っている。

2 を掛ける伝統的な方法 nバイn 行列 — 最初の行列の各行の数値と 2 番目の列の数値を乗算することにより、次のことが必要になります n³ 別々の乗算。 2 行 2 列の行列の場合、2 を意味します³ または 8 回の乗算。

1969 年、数学者の Volker Strassen は、わずか 2 回の乗算ステップと 2 回の加算で 18 行 2 列の行列を乗算できる、より複雑な手順を明らかにしました。 2 年後、コンピューター科学者のシュムエル ウィノグラードは、実際に XNUMX 行 XNUMX 列の行列の絶対最小値が XNUMX であることを証明しました。

ストラッセンは同じアイデアを利用して、すべてがより大きなものであることを示しました。 nバイn 行列は以下の数で乗算することもできます。 n³ ステップ。この戦略の重要な要素には、分解と呼ばれる手順が含まれます。これは、大きな行列を連続する小さな部分行列に分解することで、最終的には 2 行 2 列、さらには 1 行 1 列の小さな行列になる可能性があります (これらは単なる単一の数値です)。

によると、巨大な配列を小さな部分に分割する理論的根拠は非常に簡単です。 バージニアヴァシレフスカウィリアムズ、マサチューセッツ工科大学のコンピューター科学者であり、新しい論文の 100 つの共著者です。 「人間にとって、大きな行列 (たとえば、100 行 3 列のオーダー) を見て、可能な限り最良のアルゴリズムを考えるのは困難です」とヴァシレフスカ ウィリアムズ氏は言います。 3 行 XNUMX 列の行列でさえ、まだ完全には解決されていません。 「それにもかかわらず、小さな行列用にすでに開発した高速アルゴリズムを使用して、より大きな行列用の高速アルゴリズムを取得することもできます。」

研究者らは、速度の鍵は乗算ステップの数を減らし、その指数を n³ （標準的な方法の場合）できる限り。可能な限り低い値、 n², 基本的には答えを書くだけで十分です。コンピュータ科学者はその指数をオメガ、ω、と呼びます。 n^ω 2 を正常に乗算するために必要なステップが最小限であること nバイn 行列として n とても大きく成長します。 2024年2月の論文の共著者でもある周氏は、「この研究のポイントは、XNUMXにどれだけ近づくことができるか、理論的に達成できるかどうかを確認することだ」と述べた。

レーザーフォーカス

1986 年、ストラッセンはさらに大きな進歩を遂げました。 導入 いわゆる行列乗算のレーザー法です。ストラッセンはこれを使用して、オメガの上​​限値である 2.48 を確立しました。この方法は大規模な行列乗算の XNUMX ステップにすぎませんが、研究者が改良を続けているため、最も重要なステップの XNUMX つです。

1 年後、Winograd と Don Coppersmith は、レーザー法を美しく補完する新しいアルゴリズムを導入しました。このツールの組み合わせは、行列乗算を高速化するためのその後の事実上すべての取り組みで機能しました。

これらのさまざまな要素がどのように組み合わされるかについての単純化された考え方を次に示します。まず、乗算する 2 つの大きな行列 A と B から始めましょう。まず、それらを多数の小さな部分行列 (ブロックとも呼ばれます) に分解します。次に、Coppersmith と Winograd のアルゴリズムを使用して、ブロックを処理し、最終的に組み立てるための一種の取扱説明書として機能させることができます。ヴァシレフスカ・ウィリアムズ氏は、積行列 C の「何を乗算し、何を加算し、どのエントリがどこに入るのかを教えてくれる」と語った。 「これは、A と B から C を構築するための単なるレシピです。」

ただし、落とし穴があります。共通のエントリを持つブロックが作成される場合があります。これらを製品内に残すことは、これらのエントリを 2 回カウントすることに似ているため、ある時点で、重複と呼ばれる重複した用語を削除する必要があります。研究者は、ブロックが含まれているブロックを「消去」することでこれを行います。つまり、そのコンポーネントをゼロに設定して計算から除外します。

そこでついにストラッセン氏のレーザー法が登場します。 「通常、レーザー法は非常にうまく機能し、一般にブロックのサブセットを破壊して重なりを除去する良い方法を見つけます」とル・ガール氏は述べた。レーザーがすべての重なりを除去、つまり「焼き尽くし」た後、最終的な製品マトリックス C を構築できます。

これらのさまざまな手法を組み合わせると、少なくとも理論的には、全体として意図的に少ない乗算回数で 2 つの行列を乗算するアルゴリズムが作成されます。レーザー方式は実用化を目的としたものではありません。それは行列を乗算する理想的な方法を考えるための単なる方法です。 「私たちはこのメソッドを（コンピューター上で）実行することは決してありません」と周氏は語った。 「私たちはそれを分析します。」

そしてその分析が、ここ 10 年以上で最大のオメガの改善につながりました。

紛失物が見つかった

Duan氏、Zhou氏、Wu氏による昨年夏の論文は、ストラッセン氏のプロセスがまだ大幅にスピードアップできる可能性があることを示した。それはすべて、以前の分析の奥深くに埋もれていた、隠れた損失と呼ばれる概念によるもので、「意図せずにあまりにも多くのブロックを殺してしまった結果だ」と周氏は述べた。

レーザー方式は、重複のあるブロックを廃棄予定のゴミとしてラベル付けすることで機能します。他のブロックは価値があると見なされ、保存されます。ただし、選択プロセスはある程度ランダム化されます。ゴミと評価されたブロックでも、実際には役に立つ可能性があります。これはまったくの驚きではありませんでしたが、これらのランダムな選択の多くを調査することで、Duan のチームは、レーザー法が組織的にブロックを過小評価していると判断しました。つまり、より多くのブロックを保存し、より少ないブロックを捨てるべきであるということです。そして、通常のことですが、無駄が減れば効率が高まります。

「重複することなくより多くのブロックを保持できるため、行列乗算アルゴリズムの高速化につながります」と Le Gall 氏は述べています。

この損失の存在を証明した後、Duan のチームはレーザー法でブロックにラベルを付ける方法を変更し、無駄を大幅に削減しました。その結果、彼らはオメガの新しい上限を約 2.371866​​2.3728596 に設定しました。これは、以前の上限である XNUMX よりも改善されました。 2020年に設定 ジョシュ・アルマンとヴァシレフスカ・ウィリアムズ著。これは境界をわずか約 0.001 下げるという控えめな変更のように思えるかもしれません。しかし、これは科学者たちが2010年以降に確認した単一の最大の改善だ。比較すると、ヴァシレフスカ・ウィリアムズとアルマンの2020年の結果は、前任者に比べて0.00001改善しただけだ。

しかし、研究者にとって最も興味深いのは、新記録そのものだけではありません。それは長くは続かなかったのです。また、この論文は、それまでまったく注目されなかった改善の新たな道を明らかにしたという事実でもあります。約40年にわたり、誰もが同じレーザー手法に依存してきたとル・ガール氏は語った。 「その後、彼らは、私たちはもっと良くできることに気づきました。」

2024 年 2.371552 月の論文ではこの新しいアプローチが洗練され、Vassilevska Williams 氏、Zhou 氏、およびその共著者らは隠れた損失をさらに削減できるようになりました。これにより、オメガの上​​限がさらに改善され、XNUMX に減少しました。著者らはまた、同じ手法を一般化して、長方形の乗算プロセスを改善しました (nバイm) 行列 — グラフ理論、機械学習、その他の分野に応用できる手順。

これらの方針に沿ってさらに進展することはほぼ確実ですが、限界もあります。 2015年、ル・ガルとXNUMX人の協力者 証明 現在のアプローチ (レーザー法と Coppersmith-Winograd レシピを組み合わせたもの) では、2.3078 未満のオメガを生成することはできません。ル・ガル氏は、さらなる改善を行うには、「1987年以来ほとんど変わっていない、カッパースミスとウィノグラードのオリジナルの[アプローチ]を改善する必要がある」と述べた。に設立された地域オフィスに加えて、さらにローカルカスタマーサポートを提供できるようになります。」 しかし今のところ、これより良い方法を思いついた人は誰もいません。一つもないかもしれません。

「オメガを改善することは、実際にはこの問題を理解することの一部です」と周氏は言う。 「問題をよく理解できれば、それに対するより良いアルゴリズムを設計できます。 [そして]人々はまだ、この古くからある問題を理解する非常に初期の段階にいます。」