スパース行列は、通常、列のメジャー順または行メジャー順に格納されますか？

Question

少し背景：私は、疎な行列*ベクトルの乗算についていくつかの研究をすることに興味があります。

私はスパース行列のこのデータベースを介して見てきた：

The University of Florida Sparse Matrix Collection

私は行列がで利用可能な3つの形式があることに気づいた：

1. MATLAB（.MAT）
2. マトリックスマーケット（.mtx）
3. ハーウェルボーイング（.rb）

マトリクスは列の主要な順序（すなわち、列はお互いの直後の行ではなく、互いの直後に格納されます）。しかし、文献では、圧縮されたスパース行（CSR）形式が最も一般的な形式であるように見えます（「セルプロセッサSamuelの科学的コンピューティングカーネル」を参照）。私は何らかの形でインデックス（i、j）とそれらの座標の値が格納されていることを知っていますが、行列*ベクトル乗算を効率的に実行するためにデータを最初に再フォーマットしなければならないと思います。

私の実装では、行の主要な順序でデータを格納する方が理にかなっているため、行内の要素は連続したメモリアドレスに格納されるため、順番にアクセスできます。

CSRフォーマットでは、データが行のメジャー順に格納されていると見なされるようです。だから私はこれが疑問です： データは、通常、疎なマトリックスのためにメモリにどのように格納されますか？スパース行列*ベクトル計算の一部は、列メジャーから行メジャー順にデータを再グループ化することを含むか？ この変換が一般的に疎な行列ベンチマーク結果で考慮されているのだろうかと疑問に思っています。

Answer 1

私は恐れているのでしょうか？最適なストレージスキームは、解決しようとしている問題によって異なります。考慮すべき事項は、ストレージのサイズだけでなく、計算とハードウェアの観点から、このストレージ形式でのアクセスと操作がいかに効率的であるかです。

スパース行列ベクトル乗算では、CSRは、メモリとキャッシュのパフォーマンスに優れた行列行の要素への線形アクセスを可能にするため、優れた形式です。しかし、CSRは被乗数にさらに不規則なアクセスパターンを誘導します。つまり、行から取り出したインデックスに応じて異なる位置に要素を取り出します。これはキャッシュのパフォーマンスに悪いです。 CSC行列ベクトル乗算は、解ベクトル内のより不規則なアクセスを犠牲にして、被乗数上の不規則なアクセスを除去することができる。マトリクス構造に応じて、どちらかを選択することができます。たとえば、2,3の長い行があり、同様の非ゼロ分布を持つ行列は、CSC形式で処理する方が効率的です。

良く知られているソフトウェアパッケージ/ツールでいくつかの例：

1. MATLABは、デフォルトでは、列のストレージを使用しています私の知る限り。

2. Fortranに基づいた科学的コード（およびBLAS）も、デフォルトで列記憶域を使用します。これはFortran配列がAFAIK列で始まっており、元々Fortranで作成されたDense/Sparse BLASコードが多数存在したため、主に歴史的な理由によるものです。

3. Eigenも既定で列記憶域を使用しますが、これはカスタマイズできます。

4. Intel MKLは、IIRCを選択する必要があります。

5. Boost ublasは、デフォルトで行ベースの記憶形式を使用します。大規模科学技術計算で広く使われているツールである

6. PetSCは、（SequentialAIJは、CSRの略）a row based formatを使用しますが、また、あなたが保存形式の様々なから選択することができます（上のMatCreate *機能を参照してください彼らのdocumentation）

そして、リストは続けられます。あなたが見ることができるように、さまざまなツールの間にいくつかの広がりがあり、私は基準がSpMV操作のパフォーマンスであるとは思っていません:)ターゲットの問題ドメインの共通の記憶形式、ターゲットの問題ドメインのプログラマの典型的な期待他のライブラリの側面と既存のコードとの統合が、CSR/CSCを使用する主な理由となっています。これらはツールごとに異なります（明らかに）。

とにかく、スパースストレージ形式の簡単な概要がhere見つけることができますが、より多くのストレージ・フォーマットが/いた疎行列研究で提案されている：

• ローカルに活用しようとするとブロック・ストレージ・フォーマットは、もありますマトリックスの密な部分構造。例えば、「可変ブロック構造を利用した高速スパース行列 - ベクトル乗算」（Richard W. Vuduc、Moon Hyun-Jin）を参照されたい。
• いくつかの一般的な保存形式の概要は、Python scipyの疎フォーマットのドキュメントにあります。
様々なフォーマットの利点のさらなる情報は、以下のテキスト（および多くの他）に見いだすことができる
• ：スパース線形システムのため
  • 反復方法、ユーズフ・サアド
  • SPARSKIT：疎行列のための基本的なツールキット計算、Tech。 Rep。CSRD TR 1029、イリノイ州イリノイ大学のCSRD、1990年。
  • LAPACK作業ノート50：線形代数演算のための分散疎データ構造。私は（疎行列アルゴリズムのためのカスタム・ハードウェア・アーキテクチャーを作成するには疎行列分野の研究をやってきた議員CS 92から169、コンピュータサイエンス学部、テネシー大学ノックスビル、テネシー州、1992年

SpMVなど）。経験から、いくつかのスパース行列ベンチマークは、さまざまな形式間の変換のオーバーヘッドを無視する傾向があります。これは、原則として、アルゴリズム全体の記憶形式を適合させることができると仮定することができるからです。 SpMV自体は孤立して使用されることはほとんどなく、一般に、より大きな反復アルゴリズム（例えば、線形または非線形ソルバー）の一部である。この場合、フォーマット間で変換するコストは、アルゴリズム全体の多くの反復および合計実行時間にわたって償却することができます。もちろん、あなたはこの状況であなたの前提が成立していることを正当化しなければならないでしょう。免責事項として

、コストと時間が線形ソルバーのためハードウェアアーキテクチャを実装するので、私の地域では、我々は、できるだけ多くの仮定を作るために、特に傾斜しているベンチマークに新しいSpMV保存形式は通常、かなりのものです（数ヵ月のオーダー）。ソフトウェアで作業する場合、できるだけ多くのベンチマークを実行することで、仮定をテスト、適格化、定量化する方が簡単です（D

Answer 2

これは答えではありませんが、コメントに書き込むことはできません。最良の表現形式は基本的な実装に依存します。例えば、

は、行とc1,2,3あなたは

M*v = [r1.v; 
     r2.v] 

としてのM * vを実装することができ、列 と

v = [v1; 
    v2; 
    v3] 

R1,2されている

M = [m_11 m_12 m_13; == [r1; == [c1 c2 c3] 
    m_21 m_22 m_23]  r2] 

をしましょう

または

M*v = v1*c1 + v2*c2 + v3*c3 

*は、スカラーベクトル乗算である。

マトリクスの希薄さに応じて形式を選択することで、操作の数を最小限に抑えることができます。通常は、行数や列数が少ないほど良いでしょう。