4

新しいスパース線形ソルバーのいくつかをテストしたいのですが、マトリックスをすばやく埋める方法があるかどうかを知りたいです。私が興味を持っている形式は CSR (http://goo.gl/hLXYd) です。CSR形式のマトリックスが次のように与えられるとしましょう：

values(num non-zero elements)
columns(num non-zero elements)
rowIndex(num rows + 1)

検討中の疎行列は、ネットワークから派生します。そのため、何千ものノードがあり、そのうちのいくつかはそれらの間を線で接続しています。したがって、マトリックスは構造的に対称です。各接続 (i,j) は、対角項 (i,i) および (j,j) と非対角項 (i,j) および (j,i) に何かを追加します。同じノード (i,j,1)、(i,j,2) 間に複数の接続を作成できます。したがって、2 つの対角要素と 2 つの非対角要素を複数回再検討する必要がある場合があります。

rowIndex(i) を実行することで行の先頭を取得できることはわかっています。次に、j がどこにあるかを見つけるために、要素 columns(rowIndex(i):rowIndex(i+1)-1) を実行する必要があります。

質問：

要素を更新するたびに検索を実行することなく、CSR 形式で要素にすばやくアクセスする方法はありますか?

いくつかの明確化: マトリックスを最初から入力する必要があるだけです。マトリックスは構造的に対称であり、実際には対称ではありません。保存される値は、ネットワーク データ (インピーダンス、抵抗など) に関係しており、実際の値を持っています。一般に、Value(i,j)<>Value(j,i) です。(name1,i1,j1,value1)、(name2,i2,j2,value2) などの形式のタプルがあります。これらのタプルはソートされておらず、2 つのタプルが同じ i,j 値を参照できます。追加される

前もって感謝します！

4

2 に答える 2

1

あなたの質問は2つのかなり異なる質問を混同しているようです：

  1. CSR形式でマトリックスをすばやく作成する方法は何ですか？
  2. CSR形式ですでに保存されているマトリックスから値を読み取るより速い方法はありますか？（より速く、つまり、あなたが説明する簡単なアプローチよりも）

だからここに2つの答えがあります：

  1. 一般に、ネットワークデータをどのような形式でもキーの辞書のようなものに読み取ります（他の中間形式が利用可能であり、速度やその他の理由でより魅力的な場合があります）。次に、その中間構造をマトリックスのCSR形式に変換します。これについては、以下で詳しく説明します。
  2. 私はそうは思わない。CSR形式で保存されたマトリックスではない。この比較的遅いアクセスは、スペースを節約するために支払う代償の一部です。あなたは自分の視点に応じて、時間を空間と交換したり、空間を時間と交換したりしました。

入力データの説明は、生データをマーシャリングするための独自の中間形式を考案することを検討する必要があることを示唆しています。隣接行列は対称であるため、任意の形式でその半分を格納するだけで済みます。さらに、主対角線に沿って要素を格納する必要はおそらくありません。ノードiが常にノードに接続されているiか、ネットワークの性質によってに格納される値が決まることはないと推測しています(i,i)。マトリックスの各ノードに格納する情報が少しわかりません。それは、との間の接続の数ですかi、jそれとも他の何かですか？

于 2012-10-23T09:27:26.013 に答える