疎行列
 数値解析と計算科学の分野において、疎行列（そぎょうれつ、英語: sparse matrix）または疎配列（英語: sparse array）とは、成分のほとんどが零である行列のことをいう[1]。スパース行列とも言う。行列が疎であると判定するためのゼロの値を持つ要素の割合について厳密な定義はないが、一般的な条件としては、非ゼロ要素の数が行数または列数におおよそ近いものである。逆に、ほとんどの要素が非ゼロ要素である行列は、密な（dense）行列であると見なされる[1]。行列のゼロ要素の数を要素数の合計で割った値を、行列のスパース性（sparsity）と呼ぶことがある。 概念的には、スパース性はペアワイズ相互作用をほとんど持たないシステムに対応する。たとえば、隣同士がバネで接続されたボールの線について考えると、各ボールは隣接するボールのみと組になっているため、これはスパースなシステムである。対称的に、同じボールの線でも、1つのボールが他のすべてのボールとバネでつながっている場合、このシステムは密行列と対応する。スパース性の概念は、組み合せ論や、通常、重要なデータや接続の密度が低くなるネットワーク理論・数値解析などの応用領域で役に立つ。巨大な疎行列は、偏微分方程式を解くときに科学や工学のアプリケーションによく現れる。 コンピューター上で疎行列の保存や操作を行うときには、行列のスパースな構造を利用した特別なアルゴリズムとデータ構造を使用することが有益であり、多くの場合には必要になる。機械学習の分野では疎行列がよく用いられるため[2]、疎行列に特化したコンピューターも作られている[3]。標準的な密行列の構造とアルゴリズムを対象とする操作は、巨大な疎行列に適用する場合には処理とメモリがゼロ値で無駄になり、遅くて非効率である。スパースなデータは本質的により簡単に圧縮されるため、必要なストレージが非常に小さくなる。非常に巨大な疎行列に対しては、標準的な密行列で使用する操作を適用することができる場合もある。 有限差分法、ある有限体積法、有限要素法などで離散化された偏微分方程式は、一般に疎行列を係数行列とした連立一次方程式となる。 数値解析の分野では、疎行列を前提とした解法が多い。疎行列の非零要素だけを工夫してうまく格納することにより、大次元の問題を扱うことが容易になる。また、たとえば比較的少ない手間でベクトルと行列の積を計算できるなどの利点がある。ランダムメモリアクセスを多用する疎行列を用いた計算処理はベクトルプロセッサが得意としており、一般的なスカラ型CPUやGPGPUでは未だに苦手とする処理である[4][注釈 1]。 格納形式行列は、典型的には2次元の配列に格納される。配列の各要素は、行列の要素ai,jを表し、2つのインデックスiとjを用いてアクセスされる。慣習として、iは上から下に数えた行のインデックスを指し、jは左から右に数えた列のインデックスを指す。m × n行列の場合、このフォーマットで行列を格納するのに必要なメモリ量は、m × nに比例する（忘れられることが多いが、行列の次元も格納する必要がある）。 疎行列の場合、非ゼロ要素のみを保存することで、必要メモリ容量の大幅な削減が実現できる。非ゼロ要素の数と分散によって、異なるデータ構造を利用することで、基本的なアプローチに比べてメモリ量の大幅な節約が可能になる。トレードオフは、各要素へのアクセスがより複雑になり、オリジナルの行列を曖昧さなく復元できるようにするために追加の構造が必要になることである。 このため疎行列を格納するための様々な形式（フォーマット）が存在する。 フォーマットは2つのグループに分けられる。
以下の名称は、Netlibで使われているもの[5]やIntel Math Kernel Library[6]、SciPyで使われているものに基づく。例として次の疎行列Aを考える。 |
疎行列と同じ種類の言葉
- 疎行列のページへのリンク
