疎行列
数値解析と計算科学の分野において、疎行列(そぎょうれつ、英語: sparse matrix)または疎配列(英語: sparse array)とは、成分のほとんどが零である行列のことをいう。スパース行列とも言う。行列が疎であると判定するためのゼロの値を持つ要素の割合について厳密な定義はないが、一般的な条件としては、非ゼロ要素の数が行数または列数におおよそ近いものである。逆に、ほとんどの要素が非ゼロ要素である行列は、密な(dense)行列であると見なされる。行列のゼロ要素の数を要素数の合計で割った値を、行列のスパース性(sparsity)と呼ぶことがある。
概念的には、スパース性はペアワイズ相互作用をほとんど持たないシステムに対応する。たとえば、隣同士がバネで接続されたボールの線について考えると、各ボールは隣接するボールのみと組になっているため、これはスパースなシステムである。対称的に、同じボールの線でも、1つのボールが他のすべてのボールとバネでつながっている場合、このシステムは密行列と対応する。スパース性の概念は、組み合せ論や、通常、重要なデータや接続の密度が低くなるネットワーク理論・数値解析などの応用領域で役に立つ。巨大な疎行列は、偏微分方程式を解くときに科学や工学のアプリケーションによく現れる。
このため疎行列を格納するための様々な形式(フォーマット)が存在する。
フォーマットは2つのグループに分けられる。
効率的な編集をサポートするフォーマット DOK(Dictionary of keys) LIL(List of lists) COO
効率的なアクセスと行列操作をサポートするフォーマット CSR CSC BSR: ブロック疎行列(Block Sparse matrix)向け
以下の名称は、Netlibで使われているものやIntel Math Kernel Library、SciPyで使われているものに基づく。例として次の疎行列Aを考える。
[ 1 2 3 0 0 0 0 1 2 0 0 2 0 0 0 1 ] {\displaystyle {\begin{bmatrix}1&2&3&0\\0&0&0&1\\2&0&0&2\\0&0&0&1\\\end{bmatrix}}}
Dictionary of Key(DOK)は、(行, 列) をキーにして連想配列に入れる方式である。