疎行列

疎行列（そぎょうれつ）とは，成分のほとんどが零である行列のことをいう。スパース行列とも言う。 有限差分法，有限体積法，有限要素法などで離散化された偏微分方程式は一般に疎行列を係数行列とした連立一次方程式となる。

数値解析の分野では，疎行列を前提とした解法が多い。疎行列であれば格納方式を工夫することで次元数を増やすことができる上に、ベクトル-行列積が比較的低計算量で求められるためである。

疎行列の格納方法

最もスタンダードな方法として、圧縮行格納方式(Compressed Row Storage, CRS)がある。 例えば行列 ${\begin{pmatrix}1&2&3&0\\0&0&0&1\\2&0&0&2\\0&0&0&1\\\end{pmatrix}}$ に対して格納する場合を考える。まず、非零の要素を左から右へ、上から下へ書きならべた配列を作り、

[1 2 3 1 2 2 1]

とする。さらに、各要素が何行目・何列目にあるかを別の配列に格納し、

A = [1 2 3 1 2 2 1] 非零要素リスト
IA = [1 1 1 2 3 3 4] i行
JA = [1 2 3 4 1 4 4] j列

とする。 こうすると配列IAというのは同じ数字がずっと続くので、これを圧縮し、何番目の要素からiが始まるかを書きならべる。この場合だと、IAの中で、1が初めに出現するのは1番目、2が初めに出現するのは4番目、3が初めに出現するのは5番目、4が初めに出現するのは7番目なので、

IA' = [1 4 5 7] 

とする。 この、A, IA', JAの組を用いて疎行列を表現する。

関連項目

• 四分木