2

対称ではないスパース行列IEのスパース性はややランダムであり、対角線から設定された距離にあるすべての値を当てにすることはできません。

ただし、それでもまだまばらであり、マトリックスのストレージ要件を減らしたいと思います。したがって、最初の非ゼロから始まり、最後の非ゼロに到達するまで、各行を順番に格納する方法を理解しようとしています。

つまり、行mの最初の非ゼロが列2にあり、最後の非ゼロが列89にある場合、A[m]行2->89に格納します。

各行には同じ数の非ゼロがないため、Aのすべての行に同じ数の要素を持たせ、非ゼロ要素の数が少ない行の行の最後にゼロを埋め込みます。 。

この翻訳をCで行うにはどうすればよいですか？私は実際には、値をコピーするための元の完全なマトリックスを持っていません（元のマトリックスはCSR形式で私に届きます）。これをFortranで行っている場合は、配列を2次元として定義し、ゼロ以外の列の開始/停止値を追跡して各行を可変長にし、そのように格納することができます。

以下にデモンストレーションを試みます。

これは私が知っている値のマトリックス表現です-そして各値について、私は行と列の位置を知っています

  [1    2    3    4                   ]
  [   5    6    7    8                ]
  [       10    11    12    13        ]
 m[   14    15    16    17       18   ]
  [         19    20    21         22 ]

この1つの行mでは、最初の非ゼロと最後の非ゼロの間の「スパン」が最大であるため、新しいマトリックスは次のようになります。5x[span of row m]

  [1     2     3     4          ]
  [5     6     7     8          ]
  [10    11    12    13         ]
 m[14    15    16    17       18]
  [19    20    21       22      ]

ご覧のとおり、行mはとにかく最長の「スパン」であったため、ゼロのパディングは必要ありません。

他の行はすべて、最初の非ゼロとして行ゼロを持ち、各非ゼロ間のゼロ列の間隔を維持します。

4

3 に答える 3

3

これを不規則な配列として実装し、A[n][0]は常に対角線上の要素を返します。A [n] [1]は対角線のすぐ右側にアイテムを返し、A[n][2]は対角線の左側にアイテムを返します。次に、行列インデックス[i、j]を不規則配列インデックス[r][s]にマップする関数が必要です。

これにはスパース性の利点があり、値が対角線の近くにある場合、配列はそれほど長くありません。

または、次のように定義することもできます。

struct Row
{
    int InitialOffset;
    int NumElements;
    int[] Values;
}

次に、Row[]があります。マトリックスインデックスに基づいて値を取得すると、次のようになります。

//matrix is merely an array of rows...
int GetValue(*matrix this, int i, int j)
{
    Row CurrentRow = (*this)[i];
    if (CurrentRow.InitialOffset > j)
        return 0;
    else if (CurrentRow.InitialOffset + CurrentRow.NumElements < j)
        return 0; 
    return CurrentRow.Values[j - CurrentRow.InitialOffset]
}

私のC構文は少しぼんやりしていますが、あなたはその考えを理解する必要があります。

あなたのデモンストレーションに基づいて、私はこれをお勧めします：

struct Matrix
{
    int[,] Data
    int[] StartOffset;
    int[] NumberElements;
}

次のように使用されます...

int GetValue(*Matrix this, int i, int j)
{
    if (this.StartOffset[i] > j)
        return 0;
    else if (this.StartOffset[i] + this.NumberElements[i] < j)
        return 0; 
    return this.Data[i, j-this.StartOffset[i]];
}

初期化手順は次のようになります

//Data is a struct that holds row index, col index, and value
Matrix* InitMatrix (*Data values, int numVals)
{
    //loop through values to find longest row and number of rows
    //create new matrix, malloc matrix for longrow * numRows
    //malloc numrows elements for StartOffset and NumItems
    //foreach row, find min() and max()-min() of col indexs and 
    //store in StartOffset and NumItems
}

いくつかの処理を行う必要がありますが、データ圧縮は安価ではありません。

于 2010-08-12T18:53:24.917 に答える
2

別のアプローチは、リンクされた構造を使用することです（行列が非常にまばらである場合は非常に効率的であり、より多く満たされるほど良くはありません）。以前の回答で実装をほのめかしました。

連続実行の実装を使用する予定ですが、同じ長さの行を本当に使用する必要があるかどうかはわかりません。ジャグ配列を使用してみませんか？

于 2010-08-12T18:49:12.310 に答える
1

デレク、コメントの1つで、単一のmallocを使用したいとおっしゃいました。つまり、空でない要素がいくつあるかを知っているということです。これが与えられると、ttは、要素ごとに、行列要素の値と次の要素への「位置デルタ」を保持する配列にスパース行列を格納することができます。何かのようなもの：

struct melem {
    int value; // value of data
    int offset; // offset to next element
}

struct melem matrix[num_nonempty_elements];

...

// Note: this is pseudocode!
matrix[row*COLS + col].value = a[row][col];
matrix[row*COLS + col].offset = (row*COLS + col)_[i] - (row*COLS + col)_[i-1];

編集：それについて考えると、これはリンクリストのアプローチに非常に似ていますが、1つの割り当てが必要です。OTOH、必要なセルにアクセスするには、さらに計算が必要になる場合があります。

于 2010-08-12T19:32:16.973 に答える