疎行列
疎行列（そぎょうれつ、英: sparse matrix）とは、成分のほとんどが零である行列のことをいう。スパース行列とも言う。 有限差分法、有限体積法、有限要素法などで離散化された偏微分方程式は一般に疎行列を係数行列とした連立一次方程式となる。
数値解析の分野では、疎行列を前提とした解法が多い。疎行列であれば格納方式を工夫することで次元数を増やすことができる上に、ベクトル-行列積が比較的低計算量で求められるためである。
Contents
疎行列の格納方法
名称は、Netlib で使われている物[1]や Intel Math Kernel Library[2]・SciPy で使われている物に基づく。
Dictionary of Key (DOK)
(行, 列) をキーにして連想配列に入れる方式。
リストのリスト (LIL)
行ごとにリストを作り、そのリストの中に (列, 値) のタプルを入れる方式。
座標リスト (COO)
(行, 列, 値) のタプルでリストを作る方法。
圧縮行格納方式 (CRS)・Compressed Sparse Row (CSR)
最もスタンダードな方法として、圧縮行格納方式（Compressed Row Storage, CRS）や Compressed Sparse Row (CSR) がある。
例えば行列 [math] \begin{pmatrix} 1 & 2 & 3 & 0\\ 0 & 0 & 0 & 1\\ 2 & 0 & 0 & 2\\ 0 & 0 & 0 & 1\\ \end{pmatrix} [/math] に対して格納する場合を考える。まず、非零の要素を左から右へ、上から下へ書きならべた配列を作り、
[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の組を用いて疎行列を表現する。
圧縮列格納方式 (CCS)・Compressed Sparse Column (CSC)
圧縮列格納方式（Compressed Column Storage, CCS）や Compressed Sparse Column (CSC) は、CRS・CSR を列単位にした物。
圧縮対角格納方式 (CDS) ・Diagonal (DIA)
圧縮対角格納方式 (Compressed Diagonal Storage, CDS) や Diagonal (DIA) は、CRS・CSR を対角行列単位にした物。
スカイライン格納方式 (SKS, SKY)
三角行列用。
ブロック圧縮行格納方式 (BCRS) ・Block sparse row (BSR)
ブロック圧縮行格納方式 (Block Compressed Row Storage, BCRS) や Block sparse row (BSR) は、CRS・CSR をブロック単位にした物。