5. 大規模疎行列の線形計算
はじめに
行列の要素のうち多くが 0 であるような行列を疎行列という. これに対して, 行列の要素のうちほとんどが 0 でない通常の行列を, 疎行列と区別したい場合には, 密行列とよぶ.
疎行列は偏微分方程式を数値的に解くための連立一次方程式の係数などとしてよく現われる. その際に偏微分方程式の解の精度を上げるためには大規模な連立一次方程式が必要になるため, 一般に大規模な行列 (例えば, 「数万 × 数万」以上) が必要とされることが多い.
通常の密行列は 2 次元配列で表すのが普通である. しかし, 疎行列を同様に 2 次元配列で表すと 0 を格納するために多くのメモリーが消費され, 計算時には 0 との演算に多くの CPU 時間が使われてしまう. それを避けるために疎行列専用の格納形式が使われる.
本章では疎行列の線形計算 (連立一次方程式, 固有値問題など) を扱う. 疎行列の線形計算では, 行列の格納形式が異なるうえに適用される問題の性質上大規模であることが多いため, 使用されるアルゴリズムも従来の密行列用の線形計算プログラムとは異なる.
疎行列係数の連立一次方程式
連立一次方程式 Ax = b を解くことを考える. ここで, A は n x n 疎行列, x および b は n ベクトルである. A は係数行列, x は解ベクトル, b は右辺ベクトルとよばれる.
応用例として代表的なものは数値シミュレーションでよく現れる偏微分方程式を解く問題である. 偏微分方程式の数値解法は最終的に疎行列係数の連立一次方程式を解くことに帰着されるが, 偏微分方程式の解を高精度で求めるためには細かな離散化が必要になり, 係数行列は非常に大きなものとなる.
そのため, 疎行列を格納する際には, 大規模問題に対応できるよう使用メモリーをできるだけ少なくし 0 でない要素だけを格納するような形式が用いられる.
従来の (密行列用の) 連立一次方程式の直接解法 (LU 分解やコレスキー分解) では, 係数行列が疎であっても計算を進めていくうちにもともと 0 だったところが 0 でなくなっていく (これをフィルインという). これは 0 でない要素だけを格納する形式にとっては不都合なため, 疎行列の連立一次方程式を解くにはフィルインが生じない反復法が適している. 反復法では係数行列の非ゼロ要素が記憶されているところだけで計算を進めることができる.
反復法には原理の違いから定常反復法とクリロフ部分空間法の 2 つがある.
なお, 一般の密行列に使われる直接解法 (LU 分解やコレスキー分解) についても, アルゴリズムに工夫を凝らして疎行列にうまく適用する方法も開発されている.
疎行列の固有値問題
固有値問題は Ax = λx を満たす x と λ を求める問題である. ここで, A は n x n 疎行列, x は n ベクトルである. λ は固有値, x は固有ベクトルとよばれる.
大規模疎行列の固有値を求める解法としては, 連立一次方程式と同様に 0 でない要素だけを用いて計算を進めることができる反復法が使われる. 対称行列用のランチョス法, 非対称行列用のアーノルディ法などがある.
目次
5.1 疎行列の格納形式
5.2 連立一次方程式 (定常反復法)
5.3 連立一次方程式 (クリロフ部分空間法)
5.4 連立一次方程式 (直接解法) (未完)
5.5 固有値・固有ベクトル
本章の参考文献
[1] 森口繁一「数値計算工学」(1989) 岩波書店[2] 名取亮「数値解析とその応用」コロナ社 (1990)
[3] 森正武, 他「岩波講座 応用数学12 [方法2] 線形計算」岩波書店 (1994)
[4] 藤野清次, 他「反復法の数理」朝倉書店 (1996)
[5] R. Barrett, 他著, 長谷川里美, 他訳「反復法Templates」朝倉書店 (1996)
[6] 仁木滉、他「楽しい反復法」共立出版 (1998)
[7] 杉原正顕, 他「線形計算の数理」岩波書店 (2009)
[8] F.シャトラン著, 伊理正夫他訳「行列の固有値 新装版」丸善出版 (2012)
[9] 櫻井鉄也, 他「数値線形代数の数理とHPC」共立出版 (2018)
[10] Louis A. Hageman and David M. Young, “Applied Iterative Methods”. Academic Press, New York, 1981.
[11] Y. Saad, “Iterative methods for sparse linear systems” 2nd ed., SIAM (2003)
