Greedy法に基づく代数マルチカラーオーダリングを導入した前処理付きMRTR法の並列化に関する検討

摘要

前処理付きクリロフ部分空間法の前進·後退代入を並列化する一手法として代数マルチカラーオーダリング（AMC）がある．本法では1回の前進·後退代入を行うのに，（色数-1）回の通信·同期が発生するため，可能な限り少ない色数の設定が望まれる．文献［1］では各色に属する未知変数の数が均等になるように色をつけているため，問題によっては色数が増加する可能性がある．一方，各色に属する未知変数の数が均等にならないGreedy法と呼ばれる色付け法があり，文献［1］の方法よりも少ない色数を使って未知変数に色付けできる．本稿では，Greedy法を導入した代数マルチカラーオーダリングと文献［1］による並列化性能を比較したので報告する．