疎行列

数値解析と計算科学の分野において、疎行列（そぎょうれつ、英語: sparse matrix）または疎配列（英語: sparse array）とは、成分のほとんどが零である行列のことをいう。スパース行列とも言う。行列が疎であると判定するためのゼロの値を持つ要素の割合について厳密な定義はないが、一般的な条件としては、非ゼロ要素の数が行数または列数におおよそ近いものである。逆に、ほとんどの要素が非ゼロ要素である行列は、密な（dense）行列であると見なされる。行列のゼロ要素の数を要素数の合計で割った値を、行列のスパース性（sparsity）と呼ぶことがある。 概念的には、スパース性はペアワイズ相互作用をほとんど持たないシステムに対応する。たとえば、隣同士がバネで接続されたボールの線について考えると、各ボールは隣接するボールのみと組になっているため、これはスパースなシステムである。対称的に、同じボールの線でも、1つのボールが他のすべてのボールとバネでつながっている場合、このシステムは密行列と対応する。スパース性の概念は、組み合せ論や、通常、重要なデータや接続の密度が低くなるネットワーク理論・数値解析などの応用領域で役に立つ。巨大な疎行列は、偏微分方程式を解くときに科学や工学のアプリケーションによく現れる。 コンピューター上で疎行列の保存や操作を行うときには、行列のスパースな構造を利用した特別なアルゴリズムとデータ構造を使用することが有益であり、多くの場合には必要になる。機械学習の分野では疎行列がよく用いられるため、疎行列に特化したコンピューターも作られている。標準的な密行列の構造とアルゴリズムを対象とする操作は、巨大な疎行列に適用する場合には処理とメモリがゼロ値で無駄になり、遅くて非効率である。スパースなデータは本質的により簡単に圧縮されるため、必要なストレージが非常に小さくなる。非常に巨大な疎行列に対しては、標準的な密行列で使用する操作を適用することができる場合もある。 有限差分法、ある有限体積法、有限要素法などで離散化された偏微分方程式は、一般に疎行列を係数行列とした連立一次方程式となる。 数値解析の分野では、疎行列を前提とした解法が多い。疎行列の非零要素だけを工夫してうまく格納することにより、大次元の問題を扱うことが容易になる。また、たとえば比較的少ない手間でベクトルと行列の積を計算できるなどの利点がある。