スパース行列

バンド行列は、非ゼロ要素が主対角線付近に集中している特殊な疎行列の一種です。バンド行列は、下側帯域幅と上側帯域幅によって特徴づけられます。下側帯域幅とは、主対角線の下側と上側（それぞれ）にある、すべての非ゼロ要素が含まれる対角線の数を指します。

形式的には、行列Aの下限帯域幅は、 i > j + pのときに要素a _{i , j}がゼロになる最小の数pです。同様に、上限帯域幅は、 i < j − pのときにa _{i , j} = 0になる最小の数pです( Golub & Van Loan 1996 、§1.2.1)。たとえば、三重対角行列の下限帯域幅は1 で、上限帯域幅も1 です。別の例として、次の疎行列の下限帯域幅と上限帯域幅は両方とも 3 です。分かりやすくするために、ゼロはドットで表されていることに注意してください。 $${\displaystyle {\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}}$$

上下の帯域幅が比較的小さい行列はバンド行列と呼ばれ、一般的な疎行列よりも単純なアルゴリズムが適用できる場合が多い。あるいは、密行列アルゴリズムを適用して、インデックスの数を減らしてループ処理を行うだけで効率を上げることができる場合もある。

行列Aの行と列を並べ替えることで、帯域幅の低い行列A 'を得ることができる場合がある。帯域幅を最小化するためのアルゴリズムは数多く存在する。

対称疎行列は無向グラフの隣接行列として現れ、隣接リストとして効率的に格納できます。

ブロック対角行列は、対角ブロックに沿った部分行列から構成されます。ブロック対角行列Aは次の形式をとります。 $${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},}$$

ここで、A _kは、すべてのk = 1, ..., nに対して正方行列である。

行列のフィルインとは、アルゴリズムの実行中に初期値がゼロから非ゼロ値に変化する要素のことです。アルゴリズムの実行中に使用されるメモリ要件と演算回数を削減するには、行列の行と列を入れ替えることでフィルインを最小限に抑えることが有効です。記号的コレスキー分解を用いることで、実際のコレスキー分解を実行する前に、最悪のフィルインを計算できます。

コレスキー分解以外にも、様々な方法が用いられています。例えば、最小二乗法で問題を解く場合、直交化法（QR分解など）がよく用いられます。理論上のフィルインは同じですが、実際には「偽の非ゼロ」は方法によって異なる場合があります。また、これらのアルゴリズムの記号版は、記号コレスキー分解と同様に、最悪の場合のフィルインを計算するために使用できます。

疎行列を解くには、反復法と直接法の両方が存在する。

共役勾配法やGMRESなどの反復法は、行列とベクトルの積の高速計算を利用する。${\displaystyle Ax_{i}}$行列${\displaystyle A}$疎行列の場合、前処理行列を用いることで、このような反復法の収束を大幅に加速できる。

DOKは、(行、列)のペアを要素の値にマッピングする辞書で構成されています。辞書に存在しない要素はゼロとみなされます。この形式は、ランダムな順序で疎行列を段階的に構築するのに適していますが、辞書順で非ゼロ値を反復処理するには不向きです。通常、この形式で行列を構築してから、処理のために別のより効率的な形式に変換します。^{[ 4 ]}

LILは行ごとに1つのリストを格納し、各エントリには列インデックスと値が含まれます。通常、これらのエントリは高速な検索のために列インデックスでソートされます。これは、増分行列の構築に適したもう1つの形式です。^{[ 5 ]}

COOは（行、列、値）タプルのリストを格納します。理想的には、ランダムアクセス時間を改善するために、エントリはまず行インデックスでソートされ、次に列インデックスでソートされます。これは、増分行列の構築に適したもう1つの形式です。^{[ 6 ]}

圧縮疎行(CSR) または圧縮行ストレージ(CRS) または Yale フォーマットは、行列Mを 3 つの (1 次元) 配列で表します。これらの配列には、それぞれ非ゼロ値、行の範囲、および列インデックスが含まれます。これは COO に似ていますが、行インデックスを圧縮するため、この名前が付けられています。このフォーマットでは、高速な行アクセスと行列とベクトルの乗算 ( M x ) が可能です。CSR フォーマットは少なくとも 1960 年代半ばから使用されており、最初の完全な説明は 1967 年に登場しました。^{[ 7 ]}

CSRフォーマットでは、疎行列m × n行列Mを3つの（1次元）配列（V、COL_INDEX、ROW_INDEX）を用いて行形式で格納します。NNZはMの非ゼロ要素の数を表します。（ここでは0から始まるインデックスを使用することに注意してください。）

• 配列VとCOL_INDEXは長さNNZで、それぞれ非ゼロ値とその値の列インデックスを格納します。
• COL_INDEXには、対応するエントリVが存在する列が格納されます。
• 配列ROW_INDEXは長さm + 1で、指定された行の開始位置を示すVおよびCOL_INDEX のインデックスをエンコードします。これは、行jより上の非ゼロの総数をエンコードするROW_INDEX[j]と同等です。最後の要素はNNZであり、これは最後の有効なインデックスNNZ − 1 の直後のV内の仮想インデックスです。^{[ 8 ]}

例えば、行列 $${\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}$$ は4 × 4行列で、非ゼロ要素は 4 つあるため、

V = [ 5 8 3 6 ] COL_INDEX = [ 0 1 2 1 ] 行インデックス = [ 0 1 2 3 4 ]

ゼロインデックス言語を前提とする。

行を抽出するには、まず以下を定義します。

row_start = ROW_INDEX[row] row_end = ROW_INDEX[row + 1]

次に、VとCOL_INDEXから、row_startからrow_endまでの範囲のスライスを取得します。

この行列の 1 行目 (2 行目) を抽出するには、row_start=1と を設定しますrow_end=2。次に、スライスV[1:2] = [8]と を作成しますCOL_INDEX[1:2] = [1]。これで、1 行目には、1 列目に値が 8 の要素が 1 つあることがわかります。

この場合、CSR表現には13個のエントリが含まれていますが、元の行列には16個のエントリがあります。CSR形式は、NNZ < ( m ( n − 1) − 1) / 2の場合にのみメモリを節約します。

別の例として、行列 $${\displaystyle {\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}}$$ は4 × 6行列 (24 エントリ) で、8 つの非ゼロ要素を持つため、

V = [ 10 20 30 40 50 60 70 80 ] COL_INDEX = [ 0 1 1 3 2 3 4 5 ] ROW_INDEX = [ 0 2 4 7 8 ]

全体は21個のエントリとして格納されます。Vに8個、 COL_INDEXに8個、 ROW_INDEXに5個です。

• ROW_INDEX は配列Vを行に分割します。各行の開始位置と終了位置を示すV(10, 20) (30, 40) (50, 60, 70) (80)のインデックス(およびCOL_INDEX ) を示します。
• COL_INDEX は列内の値を整列します(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80)。

この形式では、 ROW_INDEXの最初の値は常にゼロで、最後の値は常にNNZとなるため、ある意味で冗長です (ただし、配列の長さを明示的に格納する必要があるプログラミング言語では、NNZ は冗長ではありません)。とはいえ、この形式により、各行の長さを計算する際に例外的なケースを処理する必要がなくなり、ROW_INDEX[ i + 1] − ROW_INDEX[ i ]という式が任意の行iに対して機能することが保証されます。さらに、この冗長な格納によるメモリコストは、十分に大きな行列であればおそらく無視できる程度です。

（旧および新）イェール疎行列形式は、CSRスキームのインスタンスです。旧イェール形式は、上記の説明どおりに3つの配列で動作します。新形式では、ROW_INDEXとCOL_INDEXを1つの配列に結合し、行列の対角要素を別々に処理します。^{[ 9 ]}

論理隣接行列の場合、行配列にエントリが存在するだけで二項隣接関係をモデル化できるため、データ配列は省略できます。

イェール形式として知られているのは、イェール大学コンピュータサイエンス学科の1977年のイェール疎行列パッケージレポートで提案されたためであると考えられる。^{[ 10 ]}

CSC は CSR と似ていますが、値が最初に列ごとに読み込まれ、各値に対して行インデックスが格納され、列ポインタが格納されます。たとえば、CSC は(val, row_ind, col_ptr)で、valは行列の (上から下、次に左から右の) 非ゼロ値の配列です。row_ind は値に対応する行インデックスです。col_ptr は、各列の開始位置となるvalインデックスのリストです。この名前は、列インデックス情報が COO 形式に比べて圧縮されているという事実に基づいています。通常、構築には別の形式 (LIL、DOK、COO) を使用します。この形式は、算術演算、列スライス、および行列とベクトルの積に効率的です。これは、MATLAB で疎行列を指定するための従来の形式です (sparse関数を介して)。