21

クラスの場合、疎行列用の独自の線形方程式ソルバーを作成する必要があります。疎行列には任意のタイプのデータ構造を自由に使用でき、共役勾配を含むいくつかの解を実装する必要があります。

ベクトルとの乗算が比較的高速になるようにスパース行列を保存する有名な方法があるかどうか疑問に思っていました。

現在、私のスパース行列は基本的にラップされて実装されstd::map< std::pair<int, int>, double>ており、データがあればそれを格納します。これは、各行列要素のルックアップを実行する必要があるため、ベクトルから O(n²) の複雑さの行列の乗算を O(n²log(n)) に変換します。Yale Sparse マトリックス形式を調べたところ、要素の取得も O(log(n)) にあるように見えるので、はるかに高速になるかどうかはわかりません。

参考までに、5000 のエントリが入力された 800x800 のマトリックスがあります。このような系を共役勾配法で解くには、およそ 450 秒かかります。

別のデータ構造でもっと速くできると思いますか?

ありがとう！

4

1 に答える 1

26

最も一般的な選択肢は、CSC または CSR ストレージです。これらは両方とも、行列とベクトルの乗算に効率的です。これらの乗算ルーチンは、自分でコーディングする必要がある場合でも、非常に簡単にコーディングできます。

そうは言っても、Yale ストレージは非常に効率的な行列とベクトルの乗算も行います。行列要素のルックアップを実行している場合は、形式の使用方法を誤解しています。行列とベクトルの乗算がどのように実装されているかを学ぶために、いくつかの標準的なスパース ライブラリを調べることをお勧めします。

現在のストレージでも、O(n) の複雑さで行列の乗算を実行できます。私がこれまでに見たすべての疎な行列とベクトルの乗算アルゴリズムは、同じ手順に要約されます。たとえば、y = Ax を考えてみましょう。

  1. 結果ベクトル y をゼロ化します。
  2. 行列 A の非ゼロ要素の反復子を初期化します。
  3. 行列の次の非ゼロ要素を取得します。たとえば、A[i,j] です。i,j のパターンは通常のパターンに従っていないことに注意してください。これは単に、A の非ゼロ要素が格納される順序を反映しています。
  4. y[i] += A[i,j]*x[j]
  5. A の要素がさらにある場合は、3 に進みます。

古典的な double for ループの密な乗算コードを書いているのではないかと思います。

for (i=0; i<N; i++)
    for (j=0; j<N; j++)
        y[i] += A[i,j]*x[j]

それがルックアップを実行するように導くものです。

std::mapしかし、ストレージに固執することを提案しているわけではありません。それは非常に効率的ではありません。主に CSC が最も広く使用されているため、CSC をお勧めします。

于 2013-03-28T22:57:17.033 に答える