行列乗算アルゴリズム

行列乗算は多くの数値アルゴリズムにおいて中心的な演算であるため、行列乗算アルゴリズムの効率化に多大な努力が注がれてきました。計算問題における行列乗算の応用は、科学計算やパターン認識などの多くの分野、そしてグラフを通る経路の数え上げといった一見無関係な問題にも見られます。^{[ 1 ]}並列システムや分散システムなど、さまざまなハードウェア上で行列を乗算するためのさまざまなアルゴリズムが設計されており、これらのシステムでは計算処理が複数のプロセッサ（場合によってはネットワーク経由）に分散されます。

行列乗算の数学的定義を直接適用すると、 $n$ $\times$ $n$ 行列をその体上で乗算するのに、 $n$ $3 回$ の体演算のオーダーの時間を要するアルゴリズムが得られます (ビッグ O 表記では $Θ($ $n$ $3$ $)$ )。行列乗算に必要な時間のより良い漸近的上限は、1960 年代の Strassen のアルゴリズム以来知られていますが、最適な時間 (つまり、行列乗算の計算複雑度) は未だ不明です。2025年9 月現在行列乗算アルゴリズムの漸近的複雑性の最良の上限は、Alman、Duan、Williams、Xu、Xu、Zhouによって与えられた $O(n 2.371339)時間である。$ ^[²^]しかし、このアルゴリズムは定数が大きいため銀河アルゴリズムであり、実際には実現できない。

反復アルゴリズム

行列乗算の定義は、 $n$ $\times$ $m$ 行列 $A$ と $m$ $\times$ $p$ 行列 $B$ に対して $C = AB$ が成り立つ場合、 $Cは$ $n$ $\times$ $p$ 行列であり、その要素は AB である。

c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}.

このことから、インデックス $i を$ 1 から $n$ まで、 $j$ を1 から $p$ までループさせ、ネストされたループを使用して上記を計算する単純なアルゴリズムを構築できます。

入力：行列 $A$ と $B$
$Cを$ 適切なサイズの新しい行列とする
i を1 からnまで繰り返す:
- jが1からpまでの場合：
  - 合計 $を0とする$
  - kが1からmまでの場合：
    - セット $合計 \leftarrow 合計 + A ik \times B kj$
  - セット $C ij \leftarrow 合計$
$C$ を返す

このアルゴリズムの実行時間は $Θ(nmp)$ (漸近表記) です。^{[ 1 ]}アルゴリズム解析の目的でよく用いられる簡略化として、入力はすべて $n \times n$ サイズの正方行列であると仮定すると、実行時間は $Θ(n 3)$ 、つまり次元の 3 乗になります。^{[ 3 ]}

キャッシュの動作

反復行列乗算の 3 つのループは、正しさや漸近実行時間に影響なく、互いに任意に交換できます。ただし、アルゴリズムのメモリアクセスパターンとキャッシュの使用により、順序は実際のパフォーマンスにかなりの影響を与える可能性があります。 ^{[ 1 ]}どの順序が最適かは、行列が行優先順序、列優先順序、またはその両方の混合で格納されているかどうかにも依存します。

特に、 $M$ バイトの容量とキャッシュラインあたり $bバイト（つまり$ 、M / b個のキャッシュライン）からなる完全連想キャッシュの理想的な場合、上記のアルゴリズムは行優先順序で格納された $A$ と $Bに対して最適ではありません。n$ $>$ $M$ $/$ $b$ $の$ $場合、内側のループの各イテレーション（ Aの行と$ $B$ の列を同時に走査する）で $、$ $Bの要素$ $に$ アクセスする際にキャッシュミスが発生します。これは、最悪の場合、アルゴリズムが $Θ($ $n³$ $)$ $回$ のキャッシュミスを引き起こすことを意味します。 2010年現在メモリの速度はプロセッサの速度に比べて非常に遅いため、大きな行列の場合、実際の計算よりもキャッシュミスが実行時間を支配する。^{[ 4 ]}

行優先レイアウトの $A$ と $B$ に対する反復アルゴリズムの最適なバリアントはタイルバージョンであり、行列は暗黙的にサイズ $\sqrt M$ × $\sqrt M$ の正方形タイルに分割されます。^{[ 4 ]}^{[ 5 ]}

入力：行列 $A$ と $B$
$Cを$ 適切なサイズの新しい行列とする
タイルサイズ $T = Θ(\sqrt M)を選択します。$
I を1 からnまでTずつ増分して変化させる場合：
- Jを1からpまでTずつ増減する場合：
  - Kを1からmまでTずつ変化させる場合：
    - $A I : I + T 、 K : K + T$ と $B K : K + T 、 J : J + T$ $をC I : I + T 、 J : J + T$ に掛けます。つまり、次のようになります。
    - i をIからmin( I + T , n )まで繰り返す:
      - $jを$ $J$ から $min(J + T, p)$ まで取得する場合：
        合計 $を0とする$
        $k$ を $Kから$ $min(K + T, m)$ まで変化させる場合：
        セット $合計 \leftarrow 合計 + A ik \times B kj$
        $C$ $ij$ $\leftarrow$ $C$ $ij$ $+ 合計$ を設定します
$C$ を返す

理想化されたキャッシュモデルでは、このアルゴリズムは $Θ(⁠ n 3 / b \sqrt M ⁠) の$ キャッシュミスしか発生しません。除数 $b \sqrt M$ は現代のマシンでは数桁の大きさになるため、実際の計算が実行時間の大部分を占め、キャッシュミスはそれほど重要ではありません。^{[ 4 ]}

分割統治アルゴリズム

反復アルゴリズムの代替として、行列乗算のための分割統治アルゴリズムがあります。これはブロック分割に依存しています。

C={\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}},\,A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}},\,B={\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\\\end{pmatrix}},

これは、次元が2のべき乗であるすべての正方行列、つまり、ある $nに対して$ $2n \times2n の$ 形状を持つ行列に有効です。行列の積は次のようになります $。$

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\\\end{pmatrix}}{\begin{pmatrix}B_{11}&B_{12}\\B_{21}& B_{22}\\\end{pmatrix}}={\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

これは、部分行列のペアの 8 つの乗算とそれに続く加算ステップから構成されます。分割統治アルゴリズムは、スカラー乗算 $c$ $11$ $=$ $a$ $11$ $b$ $11$ を基本ケースとして使用して、より小さな乗算を再帰的に計算します。

$このアルゴリズムの複雑さは、 n$ の関数として漸化式^{[ 3 ]で与えられます。}

T(1)=\Theta (1);

T(n)=8T(n/2)+\Theta (n^{2}),

$サイズn /2$ の行列に対する 8 つの再帰呼び出しと、結果として得られる 4 つの行列のペアを要素ごとに合計する Θ( n 2 ) を考慮すると、分割統治再帰のマスター定理を適用すると、 $この再帰の解$ は反復アルゴリズムと同じ $Θ(n 3)であることが示されます。$ ^{[ 3 ]}

非正方行列

任意の形状の行列に対して機能し、実際にはより高速なこのアルゴリズムの変種^{[ 4 ]は}、次のように行列を4つのサブ行列ではなく2つのサブ行列に分割します。^{[ 6 ]} 行列を分割するということは、それを同じサイズの2つの部分に分割するか、奇数次元の場合はできるだけ同じサイズに近づけることを意味します。

入力: $n$ $\times$ $m$ サイズの行列 $A$ 、 $m$ $\times$ $p$ サイズの行列 $B。$
基本ケース: $max(n, m, p)$ がある閾値より小さい場合、反復アルゴリズムの展開バージョンを使用します。
再帰的なケース:

$max(n, m, p) = n$ の場合、 $A を$ 水平方向に分割します。

C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}

それ以外の場合、 $max(n, m, p) = p$ であれば、 $B を$ 垂直に分割します。

C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}

それ以外の場合は、 $max(n, m, p) = m$ とする。A $を$ 垂直に、 $Bを$ 水平に分割する。

C={\begin{pmatrix}A_{1}&A_{2}\end{pmatrix}}{\begin{pmatrix}B_{1}\\B_{2}\end{pmatrix}}=A_{1}B_{1}+A_{2}B_{2}

キャッシュの動作

再帰行列乗算のキャッシュミス率はタイル化された反復バージョンと同じですが、そのアルゴリズムとは異なり、再帰アルゴリズムはキャッシュ非依存です。^{[ 6 ]}最適なキャッシュパフォーマンスを得るために必要なチューニングパラメータはなく、他のプロセスがキャッシュスペースを占有するためキャッシュサイズが実質的に動的になるマルチプログラミング環境でも良好に動作します。 ^{[ 4 ]} (単純な反復アルゴリズムもキャッシュ非依存ですが、行列レイアウトがアルゴリズムに適応していない場合は、実際にははるかに遅くなります。)

このアルゴリズムによって発生するキャッシュミスの数は、それぞれ $bバイトのサイズを持つ$ $M$ ラインの理想的なキャッシュを備えたマシンでは、 ^[⁶^]^:¹³で制限されます。

\Theta \left(m+n+p+{\frac {mn+np+mp}{b}}+{\frac {mnp}{b{\sqrt {M}}}}\right)

サブキューブアルゴリズム

{\displaystyle O(n^{\omega })} — $行列乗算の計算複雑性に関する指数ω$ の推定値の経時的な改善 $O(n^{\omega })$ 。

単純なアルゴリズムよりも優れた実行時間を提供するアルゴリズムが存在する。最初に発見されたのは、1969年にフォルカー・シュトラッセンによって考案され、「高速行列乗算」と呼ばれることが多いシュトラッセンのアルゴリズムである。これは、2×2行列を乗算する方法に基づいており、通常の8回の乗算ではなく、わずか7回の乗算で済むが、いくつかの追加の加算と減算演算が必要となる。これを再帰的に適用すると、乗算コストが次のアルゴリズムが得られる。 $O(n^{\log _{2}7})\approx O(n^{2.807})$ Strassen のアルゴリズムは、単純なアルゴリズムに比べて複雑で数値安定性が低下しますが^{[ 7 ]} $、 n > 100$ 程度の場合^{[ 1 ]}は高速で、 BLASなどのいくつかのライブラリに登場します^{[ 8 ]}。数値安定性が問題にならない有限体などの正確な領域上の大きな行列には非常に役立ちます。

Strassen のアルゴリズムは実際に実用的な数値計算ソフトウェアやコンピュータ代数システムで使用されているため、ビッグ O 表記に隠された定数を改善することにはメリットがあります。2×2 ブロック行列の再帰的乗算に基づく改良版の主要な側面を比較した表を以下に示します。これは 7 つのブロック行列乗算によるものです。いつものように、 $n$ 行列の次元を示し、 $M$ メモリサイズを指定します。

2×2ブロック行列ステップを持つStrassenのようなアルゴリズムでは、少なくとも7回のブロック行列乗算が必要であることが知られています。1976年にProbert ^{[ 13 ]}は、そのようなアルゴリズムでは少なくとも15回の加算（減算を含む）が必要であることを示しましたが、ブロックと2×2ブロック行列が同じ基底で表現されているという隠れた仮定がありました。KarstadtとSchwartzは異なる基底で計算し、3回の加算をより安価な基底変換と交換しました。また、異なる基底を使用しても、ステップあたり12回未満の加算はできないことも証明しました。その後の研究でBeniaminiら^{[ 14 ]}は、この基底変更トリックを2×2ブロック行列よりも一般的な分解に適用し、実行時間の先頭定数を改善しました。

理論計算機科学において、ストラッセンのアルゴリズムを漸近的複雑性の観点からどの程度改善できるかは未解決の問題である。行列乗算指数は、通常、 $\omega$ は、任意のに対してとなる最小の実数である。 $n\times n$ 体上の行列は、以下の方法で乗算できます。 $n^{\omega +o(1)}$ 現場作業。現在の最良の制約は $\omega$ は $\omega <2.371339$ Alman、Duan、Williams、Xu、Xu、Zhou による。^{[ 2 ]}このアルゴリズムは、この研究分野の他の最近のアルゴリズムと同様に、1990 年にDon CoppersmithとShmuel Winogradによって与えられた Coppersmith–Winograd アルゴリズムの一般化である。 ^{[ 15 ]} $これらのアルゴリズムの概念的なアイデアは Strassen のアルゴリズムに似ている。2 つのk \times k行列を$ $k 3$ 未満の乗算で乗算する方法が考案され、この手法が再帰的に適用される。しかし、ビッグ O 表記で隠された定数係数が非常に大きいため、これらのアルゴリズムは、現在のコンピュータで処理するには大きすぎる行列に対してのみ価値がある。^{[ 16 ]}^{[ 17 ]} Victor Pan は、指数が 2.77 をわずかに上回るが、その代わりに隠れた定数係数がはるかに小さい、いわゆる実行可能なサブ 3 次行列乗算アルゴリズムを提案した。^{[ 18 ]}

フレイヴァルドのアルゴリズムは、行列 $A$ 、 $B$ 、 $Cが与えられたときに$ $Θ($ $n$ $2$ $)$ 時間で $AB$ $=$ $C$ を検証する単純なモンテカルロアルゴリズムです。

アルファテンソル

2022年、DeepMindはAlphaTensorというニューラルネットワークを発表しました。これは、シングルプレイヤーゲームのアナロジーを用いて、人間が以前に発見したものとそうでないものを含め、数千もの行列乗算アルゴリズムを発明しました。^{[ 19 ]}演算は非可換な基礎体（通常の算術）と有限体に限定されていました。 $\mathbb {Z} /2\mathbb {Z}$ (mod 2 演算)。最も優れた「実用的な」(行列乗算テンソルの明示的な低ランク分解) アルゴリズムは O(n ^2.778 ) で実行されました。^{[ 20 ]}このようなテンソル (およびそれ以上) の低ランク分解を見つけることは NP 困難です。3×3 行列の最適な乗算でさえ、可換体であっても未だ不明です。 ^{[ 20 ]} 4×4 行列では、AlphaTensor は予想外に 47 回の乗算ステップで解を発見しました。これは、mod 2 演算に限定されているものの、1969 年の Strassen のアルゴリズムで必要だった 49 回の乗算よりも改善されています。同様に、AlphaTensor は 5×5 行列を Strassen の 98 ステップではなく 96 ステップで解きました。このような改善が存在するという驚くべき発見に基づき、他の研究者たちはすぐに同様の独立した 4×4 アルゴリズムを見つけ、Deepmind の 96 ステップの 5×5 アルゴリズムを mod 2 演算では 95 ステップに、通常の演算では 97 ステップに個別に調整しました^{[ 21 ]}。^{[ 22 ]}いくつかのアルゴリズムは完全に新しいものでした。たとえば、(4, 5, 5) は通常の演算と mod 2 演算の両方で、ベースラインの 80 ステップから 76 ステップに改善されました。

並列分散アルゴリズム

共有メモリ並列処理

先に概説した分割統治アルゴリズムは、共有メモリマルチプロセッサ向けに 2 つの方法で並列化できます。これらは、8 つの再帰的な行列乗算が

{\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\\\end{pmatrix}}

4 つの加算と同様に、それぞれ独立して実行できます (ただし、アルゴリズムは加算を行う前に乗算を「結合」する必要があります)。問題の完全な並列性を活用すると、フォーク-ジョインスタイルの擬似コードで表現できるアルゴリズムが得られます。^{[ 23 ]}

手続き $multiply(C, A, B)$ :

基本ケース: $n = 1 の$ 場合、 $c 11 \leftarrow a 11 \times b 11$ と設定します(または、小さなブロック行列を乗算します)。
そうでない場合は、 n × nの形状の新しい行列Tのための領域を割り当て、次に次の操作を行う。
- $A$ $を$ $A11$ 、 $A12$ 、 $A21$ 、 $A22$ に分割 $し$ ます $。$ $$
- $B$ $を$ $B11$ 、 $B12$ 、 $B21$ 、 $B22$ に分割 $し$ ます $。$ $$
- $C を$ $C 11$ 、 $C 12$ 、 $C 21$ 、 $C 22$ に分割します。
- $T を$ $T 11$ 、 $T 12$ 、 $T 21$ 、 $T 22$ に分割します。
- 並列実行：
  - Fork $multiply(C 11, A 11, B 11)$ 。
  - Fork $multiply(C 12, A 11, B 12)$ 。
  - Fork $multiply(C 21, A 21, B 11)$ 。
  - Fork $multiply(C 22, A 21, B 12)$ 。
  - Fork $multiply(T 11, A 12, B 21)$ 。
  - Fork $multiply(T 12, A 12, B 22)$ 。
  - Fork $multiply(T 21, A 22, B 21)$ 。
  - Fork $multiply(T 22, A 22, B 22)$ 。
- （並列フォークが完了するまで待機する）
- $add(C, T)$ 。
- $T$ を解放します。

手続き $add(C, T)$ は、要素ごとに $T を$ $C$ に追加します。

基本ケース: $n = 1 の$ 場合、 $c 11 \leftarrow c 11 + t 11$ を設定します(または、おそらく展開された短いループを実行します)。
さもないと：
- $C を$ $C 11$ 、 $C 12$ 、 $C 21$ 、 $C 22$ に分割します。
- $T を$ $T 11$ 、 $T 12$ 、 $T 21$ 、 $T 22$ に分割します。
- 並行して：
  - Fork $add(C 11, T 11)$ 。
  - Fork $add(C 12, T 12)$ 。
  - Fork $add(C 21, T 21)$ 。
  - Fork $add(C 22, T 22)$ 。
- 参加する。

ここで、fork は、計算を関数呼び出しの残りの部分と並行して実行できることを示すキーワードであり、join は、以前に「fork」されたすべての計算が完了するまで待機します。partition $は$ 、ポインタ操作のみによって目的を達成します。

このアルゴリズムのクリティカルパス長は $Θ(log 2 n)$ ステップであり、これはプロセッサ数が無限の理想的なマシンでその時間を要することを意味します。したがって、実際のコンピュータでは最大で $Θ($ $n$ $3$ $/log$ $2$ $n$ $)$ の高速化が可能です。このアルゴリズムは、一時行列 $T$ との間でデータを移動する際に発生する通信コストのため実用的ではありませんが、より実用的なバリアントでは、一時行列を使用せずに $Θ($ $n$ $2$ $)の$ 高速化を実現できます。^[²³^]

通信回避型分散アルゴリズム

階層型メモリを備えた最新のアーキテクチャでは、入力行列要素のロードと格納のコストが、演算のコストよりも大きくなる傾向があります。単一マシンでは、これはRAMとキャッシュ間で転送されるデータ量であり、分散メモリのマルチノードマシンでは、ノード間で転送されるデータ量です。どちらの場合も、これは通信帯域幅と呼ばれます。3つのネストされたループを使用する単純なアルゴリズムは、 $Ω(n 3)$ の通信帯域幅を使用します。

キャノンのアルゴリズム（2D アルゴリズムとも呼ばれる）は、各入力行列をブロック行列に分割する通信回避アルゴリズムであり、ブロック行列の要素はサイズ $\sqrt M /3$ × $\sqrt M /3$ のサブ行列である。ここで、 $M$ は高速メモリのサイズである。^{[ 24 ]} $次に、単純なアルゴリズムがブロック行列に対して使用され、サブ行列の積はすべて高速メモリ内で計算される。これにより、通信帯域幅はO (n 3 / \sqrt M)$ に削減され、これは漸近的に最適である ( $Ω(n 3)$ 計算を実行するアルゴリズムの場合)。^{[ 25 ]}^{[ 26 ]}

$\sqrt$ $p$ $\times \sqrt$ $p$ の2D メッシュに配置された $p 個$ のプロセッサを持つ分散環境では、結果の 1 つのサブマトリックスを各プロセッサに割り当てることができ、各プロセッサが $O$ $($ $n$ $2$ $/$ $\sqrt$ $p$ $)$ ワードを送信して積を計算できます。これは、各ノードが最小の $O$ $($ $n$ $2$ $/$ $p$ $)$ 個の要素を格納すると仮定すると漸近的に最適です。^[²⁶^]これは、プロセッサを 3D キューブメッシュに配置し、2 つの入力サブマトリックスのすべての積を単一のプロセッサに割り当てる 3D アルゴリズムによって改善できます。結果サブマトリックスは、各行に対して縮小を実行することによって生成されます。^[²⁷^]このアルゴリズムは、プロセッサごとに $O$ $($ $n$ $2$ $/$ $p$ $2/3$ $)$ ワードを送信し、これは漸近的に最適です。^[²⁶^]ただし、これには各入力行列要素を $p$ $1/3$ 回複製する必要があるため、入力を格納するために必要なメモリよりも $p$ $1/3$ 倍多くのメモリが必要になります。このアルゴリズムは、Strassen と組み合わせることで、実行時間をさらに短縮できます。^[²⁷^]「2.5D」アルゴリズムは、メモリ使用量と通信帯域幅の間で連続的なトレードオフを提供します。^[²⁸^] MapReduceなどの最新の分散コンピューティング環境では、特殊な乗算アルゴリズムが開発されています。^[²⁹^]

メッシュ生成アルゴリズム

メッシュ上での乗算にはさまざまなアルゴリズムがあります。2D Cannon アルゴリズムを使用して標準的な 2 次元メッシュ上で2 つのn × nを乗算する場合、乗算は 3 n -2 ステップで完了できますが、繰り返し計算の場合はこの数の半分に削減されます。^[³⁰^]標準配列は、2 つの行列からのデータが同時に到着しないため、ゼロでパディングする必要があるため、非効率的です。

2 層のクロスワイヤメッシュでは、わずか 2 n -1 ステップで済むため、結果はさらに高速になります。^{[ 31 ]}繰り返し計算を行うと、パフォーマンスはさらに向上し、100% の効率になります。^{[ 32 ]}クロスワイヤメッシュアレイは、非平面 (つまり多層) 処理構造の特殊なケースと見なすことができます。^{[ 33 ]}

n ^{3 個の}処理要素を持つ 3D メッシュでは、2 つの行列を乗算すると、 ${\mathcal {O}}(\log n)$ DNSアルゴリズムを使用する。^{[ 34 ]}

参考文献

1 2 3 4 Skiena, Steven (2012). "Sorting and Searching". The Algorithm Design Manual . Springer. pp. 45–46 , 401–3 . doi : 10.1007/978-1-84800-070-4_4 . ISBN 978-1-84800-069-8。
1 2 Alman, Josh; Duan, Ran; Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (2025). "More Asymmetry Yields Faster Matrix Multiplication" . Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM. pp. 2005–2039 . doi : 10.1137/1.9781611978322.63 .
1 2 3コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。75 ～ 79ページ。ISBN 0-262-03384-4。
1 2 3 4 5 Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 ソフトウェアシステムのパフォーマンスエンジニアリング、講義 8" . MIT OpenCourseWare . マサチューセッツ工科大学。2019年 10 月 7 日のオリジナルからアーカイブ済み。2015年1 月 27 日取得。
↑ Lam, Monica S. ; Rothberg, Edward E.; Wolf, Michael E. (1991). The Cache Performance and Optimizations of Blocked Algorithms . ASPLOS91: 4th Int'l Conference on Architecture Support for Programming Languages & Operating Systems. doi : 10.1145/106972.106981 . ISBN 978-0-89791-380-5。
1 2 3 Prokop, Harald (1999). Cache-Oblivious Algorithms (PDF) (修士論文). MIT. hdl : 1721.1/80568 . 2023-11-22 のオリジナル(PDF)からアーカイブ済み。2015-01-28に取得。
↑ミラー、ウェッブ(1975)、「計算複雑性と数値安定性」、SIAM News、4 (2): 97–107、CiteSeerX 10.1.1.148.9947、doi : 10.1137/0204009
↑ Press, William H.; Flannery, Brian P.; Teukolsky, Saul A. ; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press . p . 108. ISBN 978-0-521-88068-8。
↑ Strassen, Volker (1969). "ガウス消去法は最適ではない". Numer. Math . 13 (4): 354–356 . doi : 10.1007/BF02165411 . S2CID 121656251 .
↑ Probert, Robert L (1976)との私信。「行列乗算の加法的な複雑さについて」。SIAM Journal on Computing。5 ( 2 ): 187–203。doi : 10.1137 /0205016。
↑ Karstadt, Elaye; Schwartz, Oded (2017年7月) 「行列乗算、少し速く」。第29回ACM並列アルゴリズムおよびアーキテクチャシンポジウム議事録。SPAA '17。pp. 101–110。doi : 10.1145 / 3087556.3087579。
↑ Schwartz, Oded; Vaknin, Noa (2023). "Pebbling Game and Alternative Basis for High Performance Matrix Multiplication" . SIAM Journal on Scientific Computing . pp. C277– C303. doi : 10.1137/22M1502719 .
↑ Probert, Robert L. (1976). "行列乗算の加法的な複雑さについて". SIAM J. Comput . 5 (2): 187–203 . doi : 10.1137/0205016 .
↑ Beniamini, Gal; Cheng, Nathan; Holtz, Olga ; Karstadt, Elaye; Schwartz, Oded (2020). "高速行列乗算アルゴリズムの演算子のスパース化". arXiv : 2008.03759 [ cs.DS ].
↑ Coppersmith, Don ; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions" (PDF) , Journal of Symbolic Computation , 9 (3): 251, doi : 10.1016/S0747-7171(08)80013-2
↑ Iliopoulos, Costas S. (1989), "Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix" (PDF) , SIAM Journal on Computing , 18 (4): 658– 669, CiteSeerX 10.1.1.531.9309 , doi : 10.1137/0218045 , MR 1004789 , archived from the original (PDF) on 2014-03-05 , retrieved 2015-01-16 , Coppersmith–Winograd アルゴリズムは、必要な乗算回数の上限に隠れた定数が非常に大きいため、実用的ではありません。
↑ Robinson, Sara (2005 年 11 月)、「行列乗算のための最適アルゴリズムに向けて」(PDF)、SIAM News、38 (9)、たとえ誰かが予想の 1 つを証明して $ω$ $= 2 を$ 実証できたとしても、リース積アプローチは、実際に発生する大規模な行列の問題には適用できない可能性が高い。[...] 時間の差が明らかになるには、入力行列が天文学的に大きくなければならない。
↑ Laderman, Julian; Pan, Victor; Sha, Xuan-He (1992), "On practical algorithms for accelerated matrix multiplication", Linear Algebra and Its Applications , 162–164 : 557–588 , doi : 10.1016/0024-3795(92)90393-O
↑ 「AlphaTensorで新しいアルゴリズムを発見する」。www.deepmind.com。2022年10月5日。 2022年11月1日取得。
1 2ファウジ、アルフセイン。バログ、マテイ;ファン、アジャ。ヒューバート、トーマス。ロメラ・パレデス、ベルナルディーノ。バレカティン、モハマダミン。アレクサンダー・ノヴィコフ。 R. ルイス、フランシスコ J.シュリットヴィーザー、ジュリアン。スヴィルシュチュ、グジェゴシュ;シルバー、デイビッド。ハサビス、デミス。コーリ、プッシュミート（2022 年 10 月）。「強化学習によるより高速な行列乗算アルゴリズムの発見」。自然。610 (7930): 47–53。ビブコード: 2022Natur.610...47F。土井: 10.1038/s41586-022-05172-4。ISSN 1476-4687。PMC 9534758。PMID 36198780。
↑ Kauers, Manuel; Moosbauer, Jakob (2022-12-02). "Flip Graphs for Matrix Multiplication". arXiv : 2212.01175 [ cs.SC ].
↑ Brubaker, Ben (2022年11月23日). 「AIが行列乗算の新たな可能性を明らかにする」 . Quanta Magazine . 2022年11月26日取得。
1 2 Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57 . hdl : 1721.1/47519 . 2020-11-06 にオリジナル (PDF) からアーカイブ済み。2015-01-16に取得。
↑キャノン、リン・エリオット（1969年7月14日）。カルマンフィルタアルゴリズムを実装するためのセルラーコンピュータ（博士論文）。モンタナ州立大学。
↑ Hong, JW; Kung, HT (1981). "I/O 複雑性: 赤青の小石ゲーム" (PDF) .第 13 回 ACM 理論計算機科学シンポジウム (STOC '81) 論文集. pp. 326–333 . doi : 10.1145/800076.802486 . S2CID 8410593 . 2019 年 12 月 15 日にオリジナルからアーカイブ(PDF) 。
1 2 3 Irony, Dror; Toledo, Sivan; Tiskin, Alexander (2004 年 9 月)。「分散メモリ行列乗算の通信下限」。J . Parallel Distrib. Comput . 64 (9): 1017–26。CiteSeerX 10.1.1.20.7034。doi : 10.1016 / j.jpdc.2004.03.021。
1 2 Agarwal, RC; Balle, SM; Gustavson, FG; Joshi, M.; Palkar, P. (1995 年 9 月). "並列行列乗算への 3 次元アプローチ". IBM J. Res. Dev . 39 (5): 575– 582. CiteSeerX 10.1.1.44.3404 . doi : 10.1147/rd.395.0575 .
↑ Solomonik, Edgar; Demmel, James (2011). "通信最適化並列2.5次元行列乗算およびLU分解アルゴリズム" (PDF) .第17回国際並列処理会議議事録.第II部. pp. 90–109 . doi : 10.1007/978-3-642-23397-5_10 . ISBN 978-3-642-23397-5。
↑ Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF) . arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . 2014年7月12日取得.
↑ Bae, SE; Shinn, T.-W.; Takaoka, T. (2014). "メッシュ配列上の行列乗算のためのより高速な並列アルゴリズム" . Procedia Computer Science . 29 : 2230–40 . doi : 10.1016/j.procs.2014.05.208 .
↑ Kak, S (1988). "行列乗算のための2層メッシュアレイ". Parallel Computing . 6 (3): 383–5 . CiteSeerX 10.1.1.88.8527 . doi : 10.1016/0167-8191(88)90078-6 .
↑ Kak, S. (2014). "クロスワイヤメッシュアレイにおける行列乗算の効率". arXiv : 1411.3273 [ cs.DC ].
↑ Kak, S (1988). "多層アレイコンピューティング". Information Sciences . 45 (3): 347–365 . CiteSeerX 10.1.1.90.4753 . doi : 10.1016/0020-0255(88)90010-2 .
↑ Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981). "並列行列およびグラフアルゴリズム". SIAM Journal on Computing . 10 (4): 657–675 . doi : 10.1137/0210049 .

さらに読む

Buttari, Alfredo; Langou, Julien; Kurzak, Jakub; Dongarra, Jack (2009). "マルチコアアーキテクチャ向け並列タイル線形代数アルゴリズムのクラス". Parallel Computing . 35 : 38–53 . arXiv : 0709.1272 . doi : 10.1016/j.parco.2008.10.002 . S2CID 955 .
後藤和重、ロバート A. van de Geijn ( 2008)「高性能行列乗算の構造」ACM Transactions on Mathematical Software 34 (3): 1–25 . CiteSeerX 10.1.1.140.3583 . doi : 10.1145/1356052.1356053 . S2CID 9359223 .
Van Zee, Field G.; van de Geijn, Robert A. (2015). "BLIS: BLAS機能を迅速にインスタンス化するためのフレームワーク". ACM Transactions on Mathematical Software . 41 (3): 1–33 . doi : 10.1145/2764454 . S2CID 1242360 .
GEMMを最適化する方法

[skiena-1] 1 2 3 4 Skiena, Steven (2012). "Sorting and Searching". The Algorithm Design Manual . Springer. pp. 45–46 , 401–3 . doi : 10.1007/978-1-84800-070-4_4 . ISBN 978-1-84800-069-8。

[alman2025-2] 1 2 Alman, Josh; Duan, Ran; Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (2025). "More Asymmetry Yields Faster Matrix Multiplication" . Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM. pp. 2005–2039 . doi : 10.1137/1.9781611978322.63 .

[clrs-3] 1 2 3コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。75 ～ 79ページ。ISBN 0-262-03384-4。

[ocw-4] 1 2 3 4 5 Amarasinghe, Saman; Leiserson, Charles (2010). "6.172 ソフトウェアシステムのパフォーマンスエンジニアリング、講義 8" . MIT OpenCourseWare . マサチューセッツ工科大学。2019年 10 月 7 日のオリジナルからアーカイブ済み。2015年1 月 27 日取得。

[5] Lam, Monica S. ; Rothberg, Edward E.; Wolf, Michael E. (1991). The Cache Performance and Optimizations of Blocked Algorithms . ASPLOS91: 4th Int'l Conference on Architecture Support for Programming Languages & Operating Systems. doi : 10.1145/106972.106981 . ISBN 978-0-89791-380-5。

[prokop-6] 1 2 3 Prokop, Harald (1999). Cache-Oblivious Algorithms (PDF) (修士論文). MIT. hdl : 1721.1/80568 . 2023-11-22 のオリジナル(PDF)からアーカイブ済み。2015-01-28に取得。

[7] ミラー、ウェッブ(1975)、「計算複雑性と数値安定性」、SIAM News、4 (2): 97–107、CiteSeerX 10.1.1.148.9947、doi : 10.1137/0204009

[8] Press, William H.; Flannery, Brian P.; Teukolsky, Saul A. ; Vetterling, William T. (2007). Numerical Recipes: The Art of Scientific Computing (3rd ed.). Cambridge University Press . p . 108. ISBN 978-0-521-88068-8。

[9] Strassen, Volker (1969). "ガウス消去法は最適ではない". Numer. Math . 13 (4): 354–356 . doi : 10.1007/BF02165411 . S2CID 121656251 .

[10] Probert, Robert L (1976)との私信。「行列乗算の加法的な複雑さについて」。SIAM Journal on Computing。5 ( 2 ): 187–203。doi : 10.1137 /0205016。

[11] Karstadt, Elaye; Schwartz, Oded (2017年7月) 「行列乗算、少し速く」。第29回ACM並列アルゴリズムおよびアーキテクチャシンポジウム議事録。SPAA '17。pp. 101–110。doi : 10.1145 / 3087556.3087579。

[12] Schwartz, Oded; Vaknin, Noa (2023). "Pebbling Game and Alternative Basis for High Performance Matrix Multiplication" . SIAM Journal on Scientific Computing . pp. C277– C303. doi : 10.1137/22M1502719 .

[13] Probert, Robert L. (1976). "行列乗算の加法的な複雑さについて". SIAM J. Comput . 5 (2): 187–203 . doi : 10.1137/0205016 .

[14] Beniamini, Gal; Cheng, Nathan; Holtz, Olga ; Karstadt, Elaye; Schwartz, Oded (2020). "高速行列乗算アルゴリズムの演算子のスパース化". arXiv : 2008.03759 [ cs.DS ].

[coppersmith-15] Coppersmith, Don ; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions" (PDF) , Journal of Symbolic Computation , 9 (3): 251, doi : 10.1016/S0747-7171(08)80013-2

[16] Iliopoulos, Costas S. (1989), "Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix" (PDF) , SIAM Journal on Computing , 18 (4): 658– 669, CiteSeerX 10.1.1.531.9309 , doi : 10.1137/0218045 , MR 1004789 , archived from the original (PDF) on 2014-03-05 , retrieved 2015-01-16 , Coppersmith–Winograd アルゴリズムは、必要な乗算回数の上限に隠れた定数が非常に大きいため、実用的ではありません。

[robinson-17] Robinson, Sara (2005 年 11 月)、「行列乗算のための最適アルゴリズムに向けて」(PDF)、SIAM News、38 (9)、たとえ誰かが予想の 1 つを証明して $ω$ $= 2 を$ 実証できたとしても、リース積アプローチは、実際に発生する大規模な行列の問題には適用できない可能性が高い。[...] 時間の差が明らかになるには、入力行列が天文学的に大きくなければならない。

[18] Laderman, Julian; Pan, Victor; Sha, Xuan-He (1992), "On practical algorithms for accelerated matrix multiplication", Linear Algebra and Its Applications , 162–164 : 557–588 , doi : 10.1016/0024-3795(92)90393-O

[19] 「AlphaTensorで新しいアルゴリズムを発見する」。www.deepmind.com。2022年10月5日。 2022年11月1日取得。

[alphatensor-20] 1 2ファウジ、アルフセイン。バログ、マテイ;ファン、アジャ。ヒューバート、トーマス。ロメラ・パレデス、ベルナルディーノ。バレカティン、モハマダミン。アレクサンダー・ノヴィコフ。 R. ルイス、フランシスコ J.シュリットヴィーザー、ジュリアン。スヴィルシュチュ、グジェゴシュ;シルバー、デイビッド。ハサビス、デミス。コーリ、プッシュミート（2022 年 10 月）。「強化学習によるより高速な行列乗算アルゴリズムの発見」。自然。610 (7930): 47–53。ビブコード: 2022Natur.610...47F。土井: 10.1038/s41586-022-05172-4。ISSN 1476-4687。PMC 9534758。PMID 36198780。

[21] Kauers, Manuel; Moosbauer, Jakob (2022-12-02). "Flip Graphs for Matrix Multiplication". arXiv : 2212.01175 [ cs.SC ].

[22] Brubaker, Ben (2022年11月23日). 「AIが行列乗算の新たな可能性を明らかにする」 . Quanta Magazine . 2022年11月26日取得。

[cilk-23] 1 2 Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). Massachusetts Institute of Technology. pp. 54–57 . hdl : 1721.1/47519 . 2020-11-06 にオリジナル (PDF) からアーカイブ済み。2015-01-16に取得。

[24] キャノン、リン・エリオット（1969年7月14日）。カルマンフィルタアルゴリズムを実装するためのセルラーコンピュータ（博士論文）。モンタナ州立大学。

[25] Hong, JW; Kung, HT (1981). "I/O 複雑性: 赤青の小石ゲーム" (PDF) .第 13 回 ACM 理論計算機科学シンポジウム (STOC '81) 論文集. pp. 326–333 . doi : 10.1145/800076.802486 . S2CID 8410593 . 2019 年 12 月 15 日にオリジナルからアーカイブ(PDF) 。

[irony-26] 1 2 3 Irony, Dror; Toledo, Sivan; Tiskin, Alexander (2004 年 9 月)。「分散メモリ行列乗算の通信下限」。J . Parallel Distrib. Comput . 64 (9): 1017–26。CiteSeerX 10.1.1.20.7034。doi : 10.1016 / j.jpdc.2004.03.021。

[Agarwal-27] 1 2 Agarwal, RC; Balle, SM; Gustavson, FG; Joshi, M.; Palkar, P. (1995 年 9 月). "並列行列乗算への 3 次元アプローチ". IBM J. Res. Dev . 39 (5): 575– 582. CiteSeerX 10.1.1.44.3404 . doi : 10.1147/rd.395.0575 .

[28] Solomonik, Edgar; Demmel, James (2011). "通信最適化並列2.5次元行列乗算およびLU分解アルゴリズム" (PDF) .第17回国際並列処理会議議事録.第II部. pp. 90–109 . doi : 10.1007/978-3-642-23397-5_10 . ISBN 978-3-642-23397-5。

[29] Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). "Dimension Independent Matrix Square Using MapReduce" (PDF) . arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . 2014年7月12日取得.

[30] Bae, SE; Shinn, T.-W.; Takaoka, T. (2014). "メッシュ配列上の行列乗算のためのより高速な並列アルゴリズム" . Procedia Computer Science . 29 : 2230–40 . doi : 10.1016/j.procs.2014.05.208 .

[31] Kak, S (1988). "行列乗算のための2層メッシュアレイ". Parallel Computing . 6 (3): 383–5 . CiteSeerX 10.1.1.88.8527 . doi : 10.1016/0167-8191(88)90078-6 .

[32] Kak, S. (2014). "クロスワイヤメッシュアレイにおける行列乗算の効率". arXiv : 1411.3273 [ cs.DC ].

[33] Kak, S (1988). "多層アレイコンピューティング". Information Sciences . 45 (3): 347–365 . CiteSeerX 10.1.1.90.4753 . doi : 10.1016/0020-0255(88)90010-2 .

[34] Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981). "並列行列およびグラフアルゴリズム". SIAM Journal on Computing . 10 (4): 657–675 . doi : 10.1137/0210049 .

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[

[

[

[

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

行列乗算アルゴリズム

反復アルゴリズム

キャッシュの動作

分割統治アルゴリズム

非正方行列

キャッシュの動作

サブキューブアルゴリズム

アルファテンソル

並列分散アルゴリズム

共有メモリ並列処理

通信回避型分散アルゴリズム

メッシュ生成アルゴリズム

関連項目

参考文献

さらに読む

関連するトピック

行列乗算は多くの

数値アルゴリズム

科学計算

パターン認識などの多くの分野、そして