強制疎化、LU分解の並列計算の研究

点击翻译按钮获取中文摘要

強制疎化LU分解はオリジナルのアルゴリズムである。本研究ではLU分解や連立一次方程式の解法など関連するアルゴリズムの最新の並列処理技術について調査し、強制疎化LU分解法の並列処理の方針については知見が得られた。これらの知見およびそれに基づく強制疎化LU分解法の並列処理については、本年度中に発表することができなかったが、近いうちに研究発表をしたいと考えている。本研究では、研究テーマの周辺に位置する、線形計算の高速・並列アルゴリズムについても成果が得られた。まず、固有値解法についてはダブルシフトQR法の並列処理についてさらに研究を進めた。並列化オーバーヘッドの解析を行い、マルチシフトアルゴリズムと漸近的な並列化効率について比較を行なった。その結果についての論文を現在投稿中である。また、最近注目を集めている高速計算法に、高速多重極子展開法(FMM)がある。これは特殊な行列とベクトルの積の高速計算アルゴリズムであるが、本研究では多項式の内挿を経由させることによりこれまでよりも広い範囲の行列にこの解法が利用できることを示した。これにより球面調和関数変換などの応用上重要な変換計算がFFT並みのオーダーで計算できるようになることが分かった。今後この手法をさまざまな計算に応用し、アプリケーションに適用して評価をして行く予定である。FFTもある種の行列とベクトルの積の高速計算アルゴリズムであるが、これについてもルジャンドル変換への応用やブロックサイクリック分割を用いた並列処理などについて研究を進めている。また、連立一次方程式については非等間隔格子や球面格子上でのポアソン方程式に対する高速アルゴリズムについても研究を行ない、一部発表も行なった。