Chapter 03

疎行列はどこから生まれ何に使われるのか (執筆中)

Hishinuma_t
Hishinuma_t
2021.10.17に更新
このチャプターの目次

疎行列は神から与えられます (未執筆).

行列なんで,用途なんていくらでも考えられるわけですが,この本では連立一次方程式や固有値問題を解くために使われることを想定します.

これは感覚の話ですが,工学的な分野で大規模な数値シミュレーションを行うと言ったときに現れる疎行列は,行数は数千万以上で,1行に100個の非零要素があるかないか.というような非常に疎なものが登場します.
数千万行の行列を密行列としてメモリ上に確保することはスーパーコンピュータでも難しいため,疎行列を用いる以外の選択肢がないことが多いです.

また,実際の利用を考えると,通常の行列とは行うことができる処理が異なり,実質不可能とも言える演算もあります.
たとえば,疎行列の逆行列は疎行列と限らないので,疎行列に対して逆行列を求める関数の返り値は密行列として定義する他ありません .
誤解を恐れずに言えば,「逆行列は求まらない」と言っても過言ではありません (まあ,そもそも密行列でも逆行列は簡単に出てこないのですが,疎行列ではメモリ確保すら出来ない).
ある程度規模の大きい疎行列を扱う工学分野の多くの問題で使われるような行列を密行列でメモリ上に確保することは困難なためです.
疎行列の利用はメモリを削減するという目的において優れた効果を発揮するテクニックですが,疎行列の構造(疎性)が崩れるような処理は,あらかじめ工夫して無くす必要があります.

昔書いた文章

以下に,昔書いた文章を貼っておきます...

物理シミュレーションの核は物理現象を記述する偏微分方程式などを差分法や有限要素法などを用いて離散化することによって得られる疎行列を係数行列とする連立一次方程式の求解である.疎行列は解析領域を格子分割するなどによって得られる.解析領域を細かく分割することによって離散化誤差を減らし精度の高いシミュレーションを行えるが,行列のサイズは大きくなり求解にかかる時間が増大する.

一般的に離散化により得られる疎行列は格子点数に依存した次元数および各格子点の節点間の接続に依存した非零要素をもつ.解析領域を細かく分割しても接続関係は大きく変わらないため1行あたりの非零要素数はほとんど変化せず,大規模なシミュレーションでは非常に疎な行列が現れる.そのため一般的に疎行列の表現にはメモリ使用量を節約するために行番号や列番号のインデックス配列を用いて零要素を記憶しない格納形式を用いる.疎行列を係数とする連立一次方程式解法では疎行列の値の書き換えや挿入が頻繁に行われるLU分解などの直接解法でなく反復解法がよく使われる.

連立一次方程式 Ax = b に対するKrylov部分空間法は,初期近似解 x_0 に対応する初期残差ベクトル r_0 = b - Ax_0 を用いてA のべき乗と r_0 の積の像が張る空間から近似解を探索する反復法アルゴリズムの一つのカテゴリで,行列の性質に応じて様々なアルゴリズムがある.行列をベクトルに作用させ,ベクトルの更新を繰り返すことで近似解をえる.ベクトルのみを更新するため疎行列を変更する必要がなく疎行列を扱いやすい.