マトリックスフリー法

計算数学において、行列フリー法は、係数行列を明示的に保存せず、行列ベクトル積を評価することによって行列にアクセスする、線形方程式系または固有値問題を解くアルゴリズムです。 ^{[1]このような方法は、行列が非常に大きく、}疎行列の方法を使用しても、行列の保存と操作に多くのメモリと計算時間がかかる場合に適しています。多くの反復法では、行列を使用しない実装が可能で、以下が含まれます。

べき乗法、
ランチョスアルゴリズム、^[2]
局所最適ブロック前処理共役勾配法（LOBPCG）^[3]
ヴィーデマンの座標回帰アルゴリズム^[4]および
共役勾配法[ ⁵ ]
クリロフ部分空間法

線形システムの均質な解を実現するために、粗粒度並列ソフトウェアシステムを使用した分散ソリューションも研究されてきた。^[6]

これは通常、数値流体力学におけるオイラー方程式などの非線形方程式を解くために使用されます。マトリックスフリー共役勾配法は、非線形弾塑性有限要素ソルバーに適用されています。^{[7]これらの方程式を解くには、CPU時間とストレージの点でコストのかかる}ヤコビアンを計算する必要があります。このコストを回避するために、マトリックスフリー法が採用されています。ヤコビアンを計算する必要性をなくすために、代わりにヤコビアンベクトル積が形成されますが、これは実際にはベクトルそのものです。このベクトルの操作と計算は、大きなマトリックスや線形システムで作業するよりも簡単です。

参考文献

^ Langville, Amy N. ; Meyer, Carl D. (2006)、Google の PageRank とその先: 検索エンジンランキングの科学、プリンストン大学出版、p. 40、ISBN 978-0-691-12202-1
^ コッパースミス、ドン（1993）、「GF（2）上の線形方程式の解法：ブロックランチョスアルゴリズム」、線形代数とその応用、192：33–60、doi：10.1016 / 0024-3795（93）90235-G
^ Knyazev, Andrew V. (2001). 「最適な前処理付き固有値ソルバーに向けて: 局所的に最適なブロック前処理付き共役勾配法」SIAM Journal on Scientific Computing . 23 (2): 517–541. CiteSeerX 10.1.1.34.2862 . doi :10.1137/S1064827500366124.
^ Wiedemann, D. (1986)、「有限体上のスパース線形方程式の解法」(PDF)、IEEE Transactions on Information Theory、32 : 54–62、doi :10.1109/TIT.1986.1057137
^ Lamacchia, BA; Odlyzko, AM (1991)、「有限体上の大規模スパース線形システムの解法」、Advances in Cryptology – CRYPT0' 90、Lecture Notes in Computer Science、vol. 537、p. 109、doi : 10.1007/3-540-38424-3_8、ISBN 978-3-540-54508-8
^ Kaltofen, E.; Lobo, A. (1996)、「有限体上の大規模スパース線形システムの分散行列フリー解法」、Algorithmica、vol. 24、no. 3–4、pp. 311–348、CiteSeerX 10.1.1.17.7470、doi :10.1007/PL00008266、S2CID 13305650
^ Prabhune, Bhagyashree C.; Krishnan, Suresh (2020年3月4日). 「積層造形における残留応力を予測するための高速マトリックスフリー弾塑性ソルバー」. Computer Aided Design . 123 :102829. doi : 10.1016/j.cad.2020.102829 .

[1] Langville, Amy N. ; Meyer, Carl D. (2006)、Google の PageRank とその先: 検索エンジンランキングの科学、プリンストン大学出版、p. 40、ISBN 978-0-691-12202-1

[2] コッパースミス、ドン（1993）、「GF（2）上の線形方程式の解法：ブロックランチョスアルゴリズム」、線形代数とその応用、192：33–60、doi：10.1016 / 0024-3795（93）90235-G

[3] Knyazev, Andrew V. (2001). 「最適な前処理付き固有値ソルバーに向けて: 局所的に最適なブロック前処理付き共役勾配法」SIAM Journal on Scientific Computing . 23 (2): 517–541. CiteSeerX 10.1.1.34.2862 . doi :10.1137/S1064827500366124.

[4] Wiedemann, D. (1986)、「有限体上のスパース線形方程式の解法」(PDF)、IEEE Transactions on Information Theory、32 : 54–62、doi :10.1109/TIT.1986.1057137

[5] Lamacchia, BA; Odlyzko, AM (1991)、「有限体上の大規模スパース線形システムの解法」、Advances in Cryptology – CRYPT0' 90、Lecture Notes in Computer Science、vol. 537、p. 109、doi : 10.1007/3-540-38424-3_8、ISBN 978-3-540-54508-8

[6] Kaltofen, E.; Lobo, A. (1996)、「有限体上の大規模スパース線形システムの分散行列フリー解法」、Algorithmica、vol. 24、no. 3–4、pp. 311–348、CiteSeerX 10.1.1.17.7470、doi :10.1007/PL00008266、S2CID 13305650

[7] Prabhune, Bhagyashree C.; Krishnan, Suresh (2020年3月4日). 「積層造形における残留応力を予測するための高速マトリックスフリー弾塑性ソルバー」. Computer Aided Design . 123 :102829. doi : 10.1016/j.cad.2020.102829 .