行列乗算アルゴリズム

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

行列乗算の数学的定義を直接適用すると、その体上の2つのn×n行列を乗算するのにn⁺の体演算のオーダーの時間がかかるアルゴリズムが得られます（^ビッグO記法ではΘ ( n⁻³ ) ^）。行列の乗算に必要な時間に関するより良い漸近的境界は、1960年代のシュトラッセンのアルゴリズム以来知られていますが、最適な時間（つまり、行列乗算の計算量）は不明のままです。2025年9月現在、行列乗算アルゴリズムの漸近的複雑性に関する最良の境界は^、 Alman、Duan、 Williams、Xu、Xu、およびZhouによって示されたO( n⁻²⁻²⁻² )時間です。 ^{[ 2 ]}ただし、このアルゴリズムは定数が大きいため 銀河アルゴリズムであり、実際には実現できません。

反復アルゴリズム

行列の乗算の定義は、 n × m行列Aとm × p行列Bに対してC = ABであるとき、Cはn × p行列で あり、その要素は

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

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

• 入力: 行列AとB
• Cを適切なサイズの新しい行列とする
• 1からnまでのiについて:
  • jが 1 からpまでの場合:
    • 合計を0とする
    • kが 1 からmの場合:
      • 合計 ← 合計 + A _ik × B _kjを設定します。
    • C _ij ← 合計をセットする
• リターンC

このアルゴリズムはΘ( nmp )（漸近表記）の時間 がかかります。^{[ 1 ]}アルゴリズム解析のための一般的な単純化は、入力がすべてn × nの正方行列であると仮定することです。この場合^、実行時間はΘ( n3 )、つまり次元のサイズの3乗になります。^{[ 3 ]}

キャッシュの動作

行優先順序と列優先順序の図

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

特に、Mバイトとキャッシュラインあたりbバイトで構成されるフルアソシアティブキャッシュの理想的なケース（つまり、 ⁠M/b⁠キャッシュラインの場合、上記のアルゴリズムは、 AとBが行優先順で格納されているときには最適ではありません。n > ⁠のとき、M/b⁠、内側のループ（ Aの行とBの列を同時に走査する）の各反復処理では、 Bの要素にアクセスする際にキャッシュミスが発生します。つまり、このアルゴリズムは最悪の場合、 Θ( n ³ )回のキャッシュミスが発生することになります。2010年現在、メモリの速度はプロセッサの速度に比べて非常に速く、大規模な行列では、実際の計算よりもキャッシュミスが実行時間の大部分を占めています。 ^{[ 4 ]}

行優先レイアウトにおけるAとBの反復アルゴリズムの最適な変種はタイル化されたバージョンであり、行列は暗黙的に√M × √Mのサイズの正方形タイルに分割される：^{[ 4 ] [ 5 ]}

• 入力: 行列AとB
• Cを適切なサイズの新しい行列とする
• タイルのサイズを選択するT = Θ( √ 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からmin( I + T , n )までのiについて:
        • Jからmin( J + T , p )までのjについて:
          • 合計を0とする
          • Kからmin( K + T、m )までのkについて:
            • 合計 ← 合計 + A _ik × B _kjを設定します。
          • C _ij ← C _ij + 合計をセットする
• リターンC

理想的なキャッシュモデルでは、このアルゴリズムはΘ( ⁠n ³/b √ M⁠ )キャッシュミス; 現代のマシンでは除数b √ Mは数桁の大きさになるため、キャッシュミスではなく実際の計算が実行時間の大部分を占める。 ^{[ 4 ]}

分割統治アルゴリズム

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

${\displaystyle 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 × ^{2nとなるような}行列すべてに当てはまる。行列積は

${\displaystyle {\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 ₁₁ = a ₁₁ b ₁₁を基本ケースとして、より小さな乗算を再帰的に計算します。

このアルゴリズムの複雑さはnの関数として再帰式^{[ 3 ]}で与えられる。

${\displaystyle T(1)=\Theta (1);}$

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

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

非正方行列

このアルゴリズムの変形は、任意の形状の行列に機能し、実際にはより高速です。^{[ 4 ]}次のように、行列を4つの部分行列ではなく2つに分割します。^{[ 6 ]} 行列を分割するということは、行列を等しいサイズ、または奇数次元の場合は可能な限り等しいサイズに近い2つの部分に分割することを意味します。

• 入力:サイズn × mの行列A、サイズm × pの行列B。
• 基本ケース: max( n , m , p )が特定のしきい値を下回る場合、反復アルゴリズムの展開バージョンを使用します。
• 再帰的なケース:

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

${\displaystyle 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を垂直に分割します。

${\displaystyle 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を水平に分割する。

${\displaystyle 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行の理想的なキャッシュを持つマシンでは、 ^{[ 6 ]}で制限されます^。13

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

サブキュービックアルゴリズム

行列乗算の計算複雑性に対する指数ωの推定値の時間の経過に伴う改善。${\displaystyle O(n^{\omega })}$

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

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

ストラッセン型再帰2x2ブロック行列乗算の進歩

年	参照	ステップあたりの行列乗算回数	ステップあたりの行列加算回数	合計算術演算	総I/O複雑度
1969	シュトラッセン[ 9 ]	7	18	${\displaystyle 7n^{\log _{2}7}-6n^{2}}$	${\displaystyle 6\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-18n^{2}+3M}$
1971	ウィノグラッド[ 10 ]	7	15	${\displaystyle 6n^{\log _{2}7}-5n^{2}}$	${\displaystyle 5\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-15n^{2}+3M}$
2017	カルシュタット、シュワルツ[ 11 ]	7	12	${\displaystyle 5n^{\log _{2}7}-4n^{2}+3n^{2}\log _{2}n}$	${\displaystyle 4\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-12n^{2}+3n^{2}\cdot \log _{2}\left({\frac {{\sqrt {2}}n}{\sqrt {M}}}\right)+5M}$
2023	シュワルツ、ヴァクニン[ 12 ]	7	12	${\displaystyle 5n^{\log _{2}7}-4n^{2}+1.5n^{2}\log _{2}n}$	${\displaystyle 4\left({\frac {{\sqrt {3}}n}{\sqrt {M}}}\right)^{\log _{2}7}\cdot M-12n^{2}+1.5n^{2}\cdot \log _{2}\left({\frac {{\sqrt {2}}n}{\sqrt {M}}}\right)+5M}$

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

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

Freivaldsのアルゴリズムは、行列A、B、Cが与えられたときに、 AB = CかどうかをΘ( n ² )時間で検証する単純なモンテカルロアルゴリズムです。

アルファテンソル

2022年、DeepMindはAlphaTensorを発表しました。これは、シングルプレイヤーゲームのアナロジーを用いて数千もの行列乗算アルゴリズムを発明したニューラルネットワークで、その中には以前に人間が発見したものもあれば、そうでないものもありました。 ^{[ 19 ]}演算は非可換基底体（通常の演算）と有限体${\displaystyle \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つの方法で並列化できます。これは、

${\displaystyle {\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 ₁₁ ← a ₁₁ × b ₁₁を設定します(または小さなブロック行列を乗算します)。
• それ以外の場合は、形状n × nの新しい行列Tにスペースを割り当て、次の操作を実行します。
  • A をA ₁₁、A ₁₂、A ₂₁、A ₂₂に分割します。
  • BをB ₁₁、B ₁₂、B ₂₁、B ₂₂に分割します。
  • CをC ₁₁、C ₁₂、C ₂₁、C ₂₂に分割します。
  • T をT ₁₁、T ₁₂、T ₂₁、T ₂₂に分割します。
  • 並列実行:
    • フォーク乗算( C ₁₁、A ₁₁、B ₁₁ )。
    • フォーク乗算( C ₁₂、A ₁₁、B ₁₂ )。
    • フォーク乗算( C ₂₁、A ₂₁、B ₁₁ )。
    • フォーク乗算( C ₂₂、A ₂₁、B ₁₂ )。
    • フォーク乗算( T ₁₁、A ₁₂、B ₂₁ )。
    • フォーク乗算( T ₁₂、A ₁₂、B ₂₂ )。
    • フォーク乗算( T ₂₁、A ₂₂、B ₂₁ )。
    • フォーク乗算( T ₂₂、A ₂₂、B ₂₂ )。
  • 参加します(並列フォークが完了するまで待機します)。
  • ( C , T )を追加します。
  • Tの割り当てを解除します。

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

• 基本ケース: n = 1 の場合、c ₁₁ ← c ₁₁ + t ₁₁を設定します(または、展開された可能性のある短いループを実行します)。
• さもないと：
  • CをC ₁₁、C ₁₂、C ₂₁、C ₂₂に分割します。
  • T をT ₁₁、T ₁₂、T ₂₁、T ₂₂に分割します。
  • 並行して：
    • フォークadd( C ₁₁ , T ₁₁ )。
    • フォークadd( C ₁₂ , T ₁₂ )。
    • フォークadd( C ₂₁ , T ₂₁ )。
    • フォークadd( C ₂₂ , T ₂₂ )。
  • 参加する。

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

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

ブロック行列の乗算。2Dアルゴリズムでは、各プロセッサはCの1つのサブ行列を担当します。3Dアルゴリズムでは、乗算されるAとBのサブ行列のペアごとに、 1つのプロセッサが割り当てられます。

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

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

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

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

メッシュのアルゴリズム

クロスワイヤーメッシュ上の 2 つの n×n 行列の行列乗算は、2n-1 ステップで完了します。

メッシュ上の乗算には様々なアルゴリズムがあります。2Dキャノンアルゴリズムを用いた標準的な2次元メッシュ上での2つのn × nの乗算は、 3n -2ステップで完了しますが、繰り返し計算の場合はこの半分のステップ数に短縮されます。^{[ 30 ]}標準的な配列は、2つの行列のデータが同時に到着せず、ゼロで埋めなければならないため、非効率的です。

結果は2層のクロスワイヤーメッシュではさらに高速になり、必要なステップは2n-1ステップだけになります。[ ^{31 ]繰り返し}計算ではパフォーマンスがさらに向上し、100%の効率が得られます。^{[ 32 ]}クロスワイヤーメッシュアレイは、非平面（つまり多層）処理構造の特殊なケースと見なすことができます。^{[ 33 ]}

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

参照

• 数学演算の計算複雑さ
• 行列乗算の計算複雑さ
• CYKアルゴリズム § Valiantのアルゴリズム
• 行列連鎖乗算
• 4人のロシア人の方法
• 乗算アルゴリズム
• 疎行列とベクトルの乗算

参考文献

1. スティーヴン・スキエナ(2012). 「ソートと検索」.アルゴリズム設計マニュアル. シュプリンガー. pp.  45–46 , 401–3 . doi : 10.1007/978-1-84800-070-4_4 . ISBN 978-1-84800-069-8。
2. Alman, Josh; Duan, Ran; Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (2025). 「非対称性の増加による行列乗算の高速化」 . 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) の議事録. SIAM. pp.  2005– 2039. doi : 10.1137/1.9781611978322.63 .
3. コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2009) [1990].アルゴリズム入門（第3版）. MITプレスおよびマグロウヒル. pp.  75– 79. ISBN 0-262-03384-4。
4. 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).ブロック化アルゴリズムのキャッシュ性能と最適化. ASPLOS91: 第4回プログラミング言語とオペレーティングシステムのアーキテクチャサポートに関する国際会議. doi : 10.1145/106972.106981 . ISBN 978-0-89791-380-5。
6. Prokop, Harald (1999). Cache-Oblivious Algorithms (PDF) (Master's). MIT. hdl : 1721.1/80568 . 2023年11月22日時点のオリジナル(PDF)からのアーカイブ。 2015年1月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 (第3版). 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). 「ペブリングゲームと高性能行列乗算のための代替基底」 . 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 ].
15. コッパースミス、ドン；ウィノグラード、シュムエル（1990）「算術進行による行列乗算」（PDF）、Journal of Symbolic Computation、9（3）：251、doi：10.1016/S0747-7171（08）80013-2
16. Iliopoulos, Costas S. (1989) 「有限アーベル群の標準構造と整数行列のエルミートおよびスミス正規形を計算するアルゴリズムの最悪ケースの複雑さの境界」(PDF)、SIAM Journal on Computing、18 (4): 658– 669、CiteSeerX 10.1.1.531.9309、doi : 10.1137/0218045、MR 1004789 、 2014-03-05 にオリジナル(PDF)からアーカイブ、 2015-01-16に取得、Coppersmith–Winograd アルゴリズムは、必要な乗算回数の上限に非常に大きな隠れた定数があるため、実用的ではありません。  
17. Robinson, Sara (2005年11月)、「行列乗算の最適アルゴリズムに向けて」(PDF)、SIAM News、38 (9)、たとえ誰かが仮説の1つを証明し、 ω = 2であることを実証できたとしても、花輪積アプローチは、実際に生じる大規模な行列問題には適用できない可能性が高い。[...] 時間の違いが明らかになるためには、入力行列が天文学的な大きさでなければならない。
18. ラダーマン、ジュリアン; パン、ビクター; シャ、シュアン・ヘ (1992)、「高速行列乗算のための実用的なアルゴリズムについて」、線形代数とその応用、162– 164: 557– 588、doi : 10.1016/0024-3795(92)90393-O
19. 「AlphaTensorによる新たなアルゴリズムの発見」 www.deepmind.com 2022年10月5日 2022年11月1日閲覧。
20. ファウジ、アルフセイン;バログ、マテイ;ファン、アジャ。ヒューバート、トーマス。ロメラ・パレデス、ベルナルディーノ。バレカティン、モハマダミン。アレクサンダー・ノヴィコフ。 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). 「行列乗算のためのフリップグラフ」. arXiv : 2212.01175 [ cs.SC ].
22. Brubaker, Ben (2022年11月23日). 「AIが明らかにする行列乗算の新たな可能性」 . Quanta Magazine . 2022年11月26日閲覧。
23. Randall, Keith H. (1998). Cilk: Efficient Multithreaded Computing (PDF) (Ph.D.). マサチューセッツ工科大学. pp.  54– 57. hdl : 1721.1/47519 . 2020年11月6日時点のオリジナル(PDF)からのアーカイブ。 2015年1月16日閲覧。
24. キャノン、リン・エリオット（1969年7月14日）「カルマンフィルタアルゴリズムを実装するセルラーコンピュータ」（Ph.D.）モンタナ州立大学。
25. Hong, JW; Kung, HT (1981). 「I/Oの複雑さ：赤青小石ゲーム」（PDF） . Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81 . pp.  326– 333. doi : 10.1145/800076.802486 . S2CID 8410593. 2019年12月15日時点のオリジナルよりアーカイブ（PDF） . 
26. アイロニー、ドロール；トレド、シヴァン；ティスキン、アレクサンダー（2004年9月）「分散メモリ行列乗算における通信下限値」J. Parallel Distrib. Comput . 64 (9): 1017–26 . CiteSeerX 10.1.1.20.7034 . doi : 10.1016/j.jpdc.2004.03.021 . 
27. 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.5D行列乗算およびLU分解アルゴリズム」(PDF) .第17回国際並列処理会議論文集. 第2巻. 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). 「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層メッシュアレイ」.並列コンピューティング. 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). 「多層アレイコンピューティング」.情報科学. 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 .

さらに読む

• 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. (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を最適化する方法