数学を使おう！フォーラムで楽しくお話してみませんか？

鈴木 厚 氏 (大阪大学サイバーメディアセンター)

講演題目

大規模疎行列の並列直接法解法と FreeFem++ ソフトウェアでの活用

概略

偏微分方程式を有限要素法で離散化すると、大規模な疎行列からなる連立方程式系が得られる。その解法にはLU分解に代表される直接法と共役勾配法に代表される反復法がある。反復法は計算複雑さが小さく、主たる演算である行列とベクトルの積演算が並列計算に適するが、非対称性が強い場合や不定値の場合には適切な前処理と組み合わせる必要がある。一方直接法は堅牢な解法であるが逐次演算であること、計算複雑さが大きいため、大規模行列を扱うことは難しかった。しかし、変数の順序の並べ替えと非零成分のグラフ分割により、複数の箇所から分解を開始することと部分的な密行列演算操作の抽出により、現代のスーパースカラー型のマルチコアCPUシステムで高い演算性能を得ることが可能になってきている。数学的な問題は、有限要素法剛性行列は対称な非零要素パターンを持つため、行列の左右から同一の置換をほどこす対称軸選択が効率的であるが、不定値行列の場合はLU分解が途中で破綻する可能性があることである。分解途中の部分行列の対角成分が極端に小さくなった場合、LU分解操作を先送りすること、対角を2x2のブロックとして扱うことでこの問題を回避することができる。開発した Dissection コードは更に行列が特異な場合、核の次元を数値的に決定するアルゴリズムを含む。FreeFem++ は有限要素法の弱形式を直接記述するスクリプト言語を持つ汎用プログラムであり、三角形あるいは四面体要素分割の上での種々の有限要素空間を設定し、剛性行列を生成できる。不定値行列を導く混合型有限要素法の代表例である、非圧縮流れ問題、静磁場問題、半導体問題での Dissection コードの有効性を示す。二次元問題では、スーパースカラーCPUに最適化した直接法は反復法より高速であり、100万自由度を超える大規模な3次元問題では、領域分割と組み合わせ効率的な前処理を構成することができる。