シュトラッセンのアルゴリズム

シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、${\displaystyle N\times N}$行列同士の積を計算するには${\displaystyle O(N^{3})}$の時間が必要だが、このアルゴリズムを用いると、${\displaystyle O(N^{\log _{2}7})\approx O(N^{2.807})}$の時間で計算できる^[1]。1969年、フォルカー・シュトラッセンが開発した^[1][2]。

便宜上、${\displaystyle N}$を偶数と考えて、以下のように${\displaystyle {\frac {N}{2}}\times {\frac {N}{2}}}$部分行列に分解する。

${\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}}}$

そして、以下の七つの行列をつくる。

${\displaystyle P_{1}=(A_{11}+A_{22})(B_{11}+B_{22})}$

${\displaystyle P_{2}=(A_{21}+A_{22})B_{11}}$

${\displaystyle P_{3}=A_{11}(B_{12}-B_{22})}$

${\displaystyle P_{4}=A_{22}(B_{21}-B_{11})}$

${\displaystyle P_{5}=(A_{11}+A_{12})B_{22}}$

${\displaystyle P_{6}=(A_{21}-A_{11})(B_{11}+B_{12})}$

${\displaystyle P_{7}=(A_{12}-A_{22})(B_{21}+B_{22})}$

このとき、

${\displaystyle C_{11}=P_{1}+P_{4}-P_{5}+P_{7}}$

${\displaystyle C_{12}=P_{3}+P_{5}}$

${\displaystyle C_{21}=P_{2}+P_{4}}$

${\displaystyle C_{22}=P_{1}+P_{3}-P_{2}+P_{6}}$

の関係が成り立つ。

この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では8回必要なのに、この方法では7回ですむようになり、計算時間が削減される。部分行列への分割を再帰的に行うことにより、さらに計算時間を削減することができる。

脚注

関連文献

• Ushiro, Y. (1998). An extension of Strassen's algorithm on matrix multiplication, Hitachi, Ltd. General Purpose Computer Division.

解説記事

• Huang, J., Smith, T. M., Henry, G. M., & van de Geijn, R. A. (2016, November). Strassen's algorithm reloaded. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (p. 59). IEEE Press.
• Gates, A. Q., & Kreinovich, V. (2001). Strassen's Algorithm Made (Somewhat) More Natural: A Pedagogical Remark. Bulletin of the EATCS, 73, 142-145.
• Grochow, J. A., & Moore, C. (2017). Designing Strassen's algorithm. arXiv preprint arXiv:1708.09398.
• Ikenmeyer, C., & Lysikov, V. (2017). Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective. arXiv preprint arXiv:1708.08083.

精度保証付き数値計算

• 荻田武史, 大石進一, 後保範「Strassen のアルゴリズムによる行列乗算の高速精度保証 (微分方程式の数値解法と線形計算)」『数理解析研究所講究録』第1320巻、京都大学数理解析研究所、2003年5月、151-161頁、CRID 1050282677273376512、hdl:2433/43088、ISSN 1880-2818。 
• 森山敦史, 荻田武史, 後保範, 大石進一「拡張Strassen法による連立一次方程式の精度保証 (数値解析と新しい情報技術)」『数理解析研究所講究録』第1362巻、京都大学数理解析研究所、2004年4月、47-55頁、CRID 1050001202108508672、hdl:2433/25277、ISSN 1880-2818。 

表 話 編 歴 線型代数学・行列解析
連立一次方程式	ガウスの消去法 クラメルの公式 ガウス＝ザイデル法 ヤコビ法
ベクトル	線型独立 線型結合 基底 双対基底
ベクトル空間	双対空間 核空間 固有空間 広義固有空間 線型包 行空間 列空間 次元
計量ベクトル空間	ドット積 コーシー＝シュワルツの不等式 直交 正規直交系 正規直交基底 グラム・シュミットの正規直交化法 直交補空間
行列・線型写像	演算・操作 乗法 転置 逆行列 サラスの方法 基本変形 対角化 分解 LU QR コレスキー シューア 特異値 固有値 不変量 行列式 跡 階数 固有値と固有ベクトル 固有多項式 最小多項式 単因子 階数標準形 スミス標準形 ジョルダン標準形 有理標準形 小行列式 クラス 正則 基本 対称 エルミート 正規 直交 回転 ユニタリ 冪零 射影 正定値 ユニモジュラー 置換 区分
行列式	余因子展開 余因子行列 ヴァンデルモンドの行列式 終結式 コーシー・ビネの公式
多重線型代数	外積 外積代数 対称代数 テンソル代数
数値線形代数	基本的な概念 浮動小数点 数値的安定性 疎行列 Z-行列 M行列 条件数 ゲルシュゴリンの定理 クリロフ部分空間 ソフトウェア MATLAB 数値解析ソフトの比較/一覧 ライブラリ Armadillo Basic Linear Algebra Subprograms (BLAS) INTLAB Intel oneAPI Math Kernel Library LAPACK NumPy OpenBLAS 線型代数学ライブラリの比較 反復法・技法 SOR法 共役勾配法 GMRES法 固有値問題の数値解法 ランチョス法 QR法 べき乗法 逆べき乗法 ヤコビ法 (固有値問題) シュトラッセンのアルゴリズム ハウスホルダー変換 ギブンス回転 人物 ジェームズ・H・ウィルキンソン クリーブ・モラー ニコラス・ハイアム ジーン・ゴラブ リチャード・バルガ
行列値関数	行列指数関数 行列の対数 行列の平方根
その他	スカラー ケイリー・ハミルトンの定理 ペロン＝フロベニウスの定理 シューア補行列 シルヴェスターの慣性法則
カテゴリ