@article{zhang2015improved,
title={An improved generalized conjugate residual squared (IGCRS2) algorithm suitable for distributed parallel computing},
author={Zhang, Li-Tao and Dong, Xiao-Na and Gu, Tong-Xiang and Zuo, Xian-Yu and Liu, Xing-Ping},
journal={Japan Journal of Industrial and Applied Mathematics},
volume={32},
number={1},
pages={143--155},
year={2015},
publisher={Springer}
}
- 背景
- 線形システム(一次方程式)求解は数値計算の基礎中の基礎。さまざまな分野で使われるが、実用においては問題が大きく、非対称でスパース、また反復法による求解が一般的。
- どんなもの?
- Generalized Conjugate Residual Squared (IGCRS2) algorithmの分散環境向け並列改良。GCRは非対称な線形システム求解手法。ボトルネックは内積計算内のグローバル通信。
- 数値安定性を保ったまま内積計算を独立させて通信と計算をオーバラップさせた。
- 先行研究と比べてどこがすごい?
- GCRS(先行研究、並列手法)よりも並列性と拡張性に優れており、並列性能を約2倍向上させた。
- 技術や手法のキモはどこ?
- 同期タイミングを減らした。一回のpeer-to-peer通信でなるべく多くのデータを送るようにした。
- どうやって有効だと検証した?
- 理論的解析。グリッドのネットワークトポロジを仮定して、データ送信時間、通信セットアップ時間、計算時間などを変数におき、手法ごとに一回の反復における計算時間を数式化して比較。
- 議論はある?
- 収束時間についても比較しているが、プロセッサ増加に対するオーバーヘッドを数式でえいやと定義しているっぽいが良いのだろうか?
- あとは解析的な結果のみで実機での評価は行なっていない。
- 次に読むべき論文は?
- (引用数 35), Gu, Tongxiang, et al. "Multiple search direction conjugate gradient method I: methods and their propositions." International Journal of Computer Mathematics 81.9 (2004): 1133-1143.
- (引用数 13996) Saad, Youcef, and Martin H. Schultz. "GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems." SIAM Journal on scientific and statistical computing 7.3 (1986): 856-869.