疎行列
疎行列の例
（11220000003344000000556677000000088000000099）{\displaystyle \left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&0&99\\\end{smallmatrix}}\right)}
上記の疎行列には、非ゼロ要素が9個しかなく、ゼロ要素が26個あります。疎度は74%、密度は26%です。
2次元の有限要素問題を解いた際に得られる疎行列。非ゼロ要素は黒で表示されます。

数値解析や科学計算において、疎行列または疎配列とは、要素のほとんどがゼロである行列のことである。 [ 1 ]行列が疎であるとみなされるゼロ値要素の割合に関する厳密な定義はないが、一般的な基準としては、非ゼロ要素の数が行または列の数とほぼ等しいということである。対照的に、要素のほとんどが非ゼロである場合、その行列は稠密であるとみなされる。[ 1 ]ゼロ値要素の数を要素の総数（たとえば、m × n 行列の場合は m × n）で割った値は、行列の疎性と呼ばれること がある。

概念的には、スパース性は相互作用の少ないシステムに対応します。例えば、バネで一つ一つのボールから次のボールへとつながれた一列のボールを考えてみましょう。これは隣接するボール同士のみが結合されているスパースシステムです。対照的に、同じ一列のボールがバネで他のすべてのボールとつながれている場合、このシステムは稠密行列に対応します。スパース性の概念は、組み合わせ論や、ネットワーク理論や数値解析などの応用分野で有用です。これらの分野では、一般に重要なデータや接続の密度は低いからです。大規模なスパース行列は、偏微分方程式を解く科学技術アプリケーションでよく登場します。

疎行列をコンピュータに保存したり操作したりする場合、行列の疎構造を利用する専用のアルゴリズムとデータ構造を使用すると便利であり、多くの場合必要になります。疎行列専用のコンピュータが作られており、 [ 2 ]機械学習の分野では一般的です。[ 3 ]標準的な密行列構造とアルゴリズムを使用した操作は、処理とメモリがゼロで浪費されるため、大きな疎行列に適用すると遅く非効率的です。疎データは本質的に圧縮しやすいため、必要なストレージが大幅に少なくなります。非常に大きな疎行列の中には、標準的な密行列アルゴリズムを使用して操作できないものもあります。

特殊なケース

バンド付き

帯行列は、非ゼロ要素が主対角線付近に集中する特殊な疎行列です。帯行列は、下側バンド幅と上側バンド幅によって特徴付けられます。これらは、すべての非ゼロ要素が含まれる主対角線の下側と上側の対角線の数を表します。

正式には、行列Aの下側帯域幅とは、 i > j + pのときに要素a i , j が0となる最小の数pです。同様に、上側帯域幅とは、i < j − p のときにa i , j = 0となる最小の数pです（Golub & Van Loan 1996 , §1.2.1）。例えば、三角行列の下側帯域幅は1、上側帯域幅は1です。別の例として、次の疎行列の下側帯域幅と上側帯域幅はどちらも3です。わかりやすいように、ゼロはドットで表されていることに注意してください。 [XXX⋅⋅⋅⋅XX⋅XX⋅⋅X⋅X⋅X⋅⋅⋅X⋅X⋅X⋅⋅XX⋅XXX⋅⋅⋅XXX⋅⋅⋅⋅⋅X⋅X]{\displaystyle {\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &\cdot &\cdot &\\X&\cdot &X&\cdot &\cdot &\cdot &X&\cdot &\cdot &X&\cdot &X&\cdot &X&\cdot &X&X&\cdot &\cdot &X&X&\cdot &\cdot &\cdot &X&\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\\\end{bmatrix}}}

上側と下側の帯域幅が適度に小さい行列はバンド行列と呼ばれ、一般的なスパース行列よりも単純なアルゴリズムに適している場合が多くあります。また、密行列アルゴリズムを適用して、インデックスの数を減らしてループするだけで効率を向上できる場合もあります。

行列Aの行と列を並べ替えることで、より低い帯域幅を持つ行列A ′が得られる可能性があります。帯域幅を最小化するアルゴリズムは数多く存在します。

対角線

対角行列は、上側と下側の帯域幅がゼロである帯行列の極端な例です。対角行列は、主対角成分のみを1次元配列として格納することで効率的に格納できるため、 n × n対角行列はメモリに n個の成分のみを必要とします。

対称的

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

ブロック対角線

ブロック対角行列は、対角ブロックに沿った部分行列から構成される。ブロック対角行列Aは次の形式をとる。 あ＝[あ10⋯00あ2⋯0⋮⋮⋱⋮00⋯あn]、{\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}

ストレージ

行列は通常、2次元配列として保存されます。配列の各エントリは行列の要素a i , jを表し、2つのインデックスiとjによってアクセスされます。慣例的に、iは行インデックス（上から下へ番号付け）、jは列インデックス（左から右へ番号付け）です。m × n行列の場合、この形式で行列を保存するために必要なメモリ量は m × n に比例します（行列の次元も保存する必要があるという事実は考慮しません）。

疎行列の場合、非ゼロ要素のみを格納することで、メモリ使用量を大幅に削減できます。非ゼロ要素の数と分布に応じて異なるデータ構造を使用でき、基本的なアプローチと比較してメモリ使用量を大幅に削減できます。ただし、トレードオフとして、個々の要素へのアクセスがより複雑になり、元の行列を一意に復元するために追加の構造が必要になります。

フォーマットは 2 つのグループに分けられます。

  • DOK（キーの辞書）、LIL（リストのリスト）、COO（座標リスト）など、効率的な変更をサポートするもの。これらは通常、行列の構築に使用されます。
  • CSR (Compressed Sparse Row) や CSC (Compressed Sparse Column) など、効率的なアクセスとマトリックス操作をサポートするもの。

キー辞書（DOK）

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

リストのリスト（LIL）

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

座標リスト（COO）

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

圧縮スパース行（CSR、CRS、または Yale 形式）

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

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

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

例えば、行列 は4つの非ゼロ要素を持つ 4×4行列なので、（5000080000300600）{\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}

V = [ 5 8 3 6 ] COL_INDEX = [ 0 1 2 1 ] ROW_INDEX = [ 0 1 2 3 4 ]

ゼロインデックス言語を想定しています。

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

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

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

この行列の行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の場合にのみメモリを節約します。

別の例として、行列 は4×6行列（24要素）で、8つの非ゼロ要素を持つので、 （10200000030040000050607000000080）{\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}}}

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 (およびCOL_INDEX(10, 20) (30, 40) (50, 60, 70) (80) )のインデックスを示します。
  • COL_INDEX は列内の値を揃えます: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80)。

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

（新旧の）Yale疎行列形式はCSRスキームのインスタンスです。旧Yale形式は上記と全く同じように動作し、3つの配列を使用します。新形式ではROW_INDEXとCOL_INDEXを1つの配列に統合し、行列の対角成分を個別に扱います。[ 9 ]

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

この形式は、1977年にイェール大学コンピュータサイエンス学部の「イェール・スパース・マトリックス・パッケージ」レポートで提案されたため、イェール形式として知られていると考えられます。[ 10 ]

圧縮スパース列（CSC または CCS）

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

ソフトウェア

多くのソフトウェアライブラリが疎行列をサポートし、疎行列方程式のソルバーを提供しています。以下はオープンソースです。

  • PETSc は、さまざまな行列ストレージ形式に対応するさまざまな行列ソルバーを含む大規模な C ライブラリです。
  • Trilinos は大規模な C++ ライブラリで、密行列と疎行列の保存と対応する線形システムのソリューション専用のサブライブラリを備えています。
  • Eigen3は、複数の疎行列ソルバーを含むC++ライブラリです。ただし、いずれも並列化されていません。
  • MUMPS ( MU ltifrontal M assively Parallel sparse direct S solver) は、Fortran90 で記述されたフロント ソルバーです。
  • deal.II は、スパース線形システムとそのソリューションのサブライブラリも備えた有限要素ライブラリです。
  • DUNE は別の有限要素ライブラリであり、スパース線形システムとそのソリューションのサブライブラリも備えています。
  • Armadillo は、BLAS および LAPACK 用のユーザーフレンドリーな C++ ラッパーを提供します。
  • SciPy は、いくつかのスパース行列形式、線形代数、およびソルバーのサポートを提供します。
  • ALGLIBは、スパース線形代数をサポートするC++およびC#ライブラリです。
  • アーノルディアルゴリズムを用いた疎行列の対角化と操作のためのARPACK Fortran 77 ライブラリ
  • 大規模線形システムと疎行列の解法のためのSLEPcライブラリ
  • 機械学習用のPythonライブラリであるscikit-learnは、疎行列とソルバーのサポートを提供します。
  • SparseArraysはJulia の標準ライブラリです。
  • PSBLAS は、GPU でも複数の形式をサポートするスパース線形システムを解くソフトウェア ツールキットです。

歴史

スパース行列という用語は、いくつかの先駆的な研究を開始したものの、その後この分野から去ったハリー・マーコウィッツによって作られたと考えられます。 [ 11 ]

参照

注記

  1. ^ a bヤン、ディ;ウー、タオ。劉英。ガオ、ヤン（2017）。 「マルチコア システムでの効率的な疎密行列乗算」。2017 IEEE 第 17 回通信技術国際会議 (ICCT)。 IEEE。 pp.  1880– 3. doi : 10.1109/icct.2017.8359956。ISBN 978-1-5090-3944-9DNNの計算核は、大規模な疎行列と密行列の乗算です。数値解析の分野では、疎行列とは、主にゼロ要素で構成される行列のことです。一方、行列内の非ゼロ要素の数が比較的多い場合、一般的に密行列とみなされます。行列内のゼロ要素（非ゼロ要素）の割合は、疎性（密度）と呼ばれます。標準的な密行列構造とアルゴリズムを用いた演算は、大規模な疎行列に適用すると比較的遅く、大量のメモリを消費します。
  2. ^ 「Cerebras Systems、業界初の1兆トランジスタチップを発表」 www.businesswire.com 2019年8月19日閲覧日2019年12月2日WSEには、AI向けに最適化された40万個のコンピューティングコアが搭載されています。SLAC™（Sparse Linear Algebra Cores）と呼ばれるこれらのコンピューティングコアは、柔軟性とプログラミング性を備え、すべてのニューラルネットワークコンピューティングの基盤となるスパース線形代数向けに最適化されています。
  3. ^ 「アルゴンヌ国立研究所、世界最速の人工知能コンピュータ「セレブラスCS-1」を導入｜アルゴンヌ国立研究所」www.anl.gov（プレスリリース）。2019年12月2日閲覧。WSEは、面積46,225平方ミリメートルで史上最大のチップであり、最大のグラフィックス処理装置の56.7倍の大きさです。AIに最適化されたコンピューティングコアは78倍、高速オンチップメモリ​​は3,000倍、メモリ帯域幅は10,000倍、通信帯域幅は33,000倍に増加しています。
  4. ^参照scipy.sparse.dok_matrix
  5. ^参照scipy.sparse.lil_matrix
  6. ^参照scipy.sparse.coo_matrix
  7. ^ Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009).圧縮スパースブロックを用いた並列スパース行列ベクトル乗算と行列転置ベクトル乗算(PDF) . ACM Symp. on Parallelism in Algorithms and Architectures. CiteSeerX 10.1.1.211.5256 . 
  8. ^サアド 2003
  9. ^ Bank, Randolph E.; Douglas, Craig C. (1993)、「Sparse Matrix Multiplication Package (SMMP)」（PDF）、Advances in Computational Mathematics、1 : 127– 137、doi : 10.1007/BF02070824、S2CID 6412241 
  10. ^ Eisenstat, SC; Gursky, MC; Schultz, MH; Sherman, AH (1977年4月). 「Yale Sparse Matrix Package」(PDF) . 2019年4月6日時点のオリジナルよりアーカイブ(PDF) . 2019年4月6日閲覧。
  11. ^ハリー・M・マーコウィッツとの口述歴史インタビュー、9、10ページ。

参考文献

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Sparse_matrix&oldid=1327476357#Symmetric」から取得