C中的稀疏矩阵存储 [英] Sparse matrix storage in C

问题描述

我有一个非对称的稀疏矩阵稀疏度在某种程度上是随机的，我不能指望所有值都与对角线保持一定距离.

I have a sparse matrix that is not symmetric I.E. the sparsity is somewhat random, and I can't count on all the values being a set distance away from the diagonal.

但是，它仍然很稀疏，我想减少矩阵上的存储需求.因此，我试图找出如何存储从第一个非零开始的每一行，直到到达最后一个非零为止.

However, it is still sparse, and I want to reduce the storage requirement on the matrix. Therefore, I am trying to figure out how to store each row starting at the first non-zero, in order, until I get to the last non-zero.

也就是说，如果行m的第一个非零出现在第2列，而最后一个非零出现在第89列，则我想存储在A [m]行2-> 89中.

That is, if the first non-zero of row m occurs at column 2, and the last non-zero is at column 89, I want to store in A[m] rows 2-> 89.

由于每行不具有相同数量的非零，所以我将使A的所有行具有相同数量的元素，并对具有较少数量的non的行填充零至行末-零元素.

Since each row does not have the same number of non-zeros, I will make all the rows of A have the same number of elements, and pad zeros to the end of the row for rows that have a smaller number of non-zero elements.

我该如何用C语言翻译?我实际上并没有原始的完整矩阵来复制其值(原始矩阵以CSR形式出现在我的眼中).如果我在fortran中执行此操作，则可以通过跟踪非零列的开始/停止值并将其存储为这样，将数组定义为二维数组，并使每一行的长度可变.

How do I do this translation in C? I do not actually have an original, full matrix to just copy the values from (the original matrix is coming to me in CSR form). If I was doing this in fortran, I could just define my array to be two dimensional and just have each row be variable length by tracking the start/stop values of non-zero columns and store it like that.

我将尝试在下面进行演示:

I will try to demonstrate below:

这是我知道的值的矩阵表示形式-对于每个值，我都知道行和列的位置

This is a matrix representation of the values I know - and for each value, I know the row and column location

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

现在，此行m在第一个非零和最后一个非零之间具有最大的跨度" 所以我的新矩阵将是5x[span of row m]

Now for this one row m has the largest "span" between the first non-zero and last non-zero so my new matrix is going to be 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不需要零填充，因为它无论如何是最长的跨度"

As you can see, row m needs no zero padding since it was the longest "span" anyway

现在其他所有行都将第零行作为第一个非零行，并保持每个非零行之间的零列间隔.

The other rows now all have row zero as the first non-zero, and maintain the spacing of zeros columns between each non-zero.

推荐答案

我将其实现为一个参差不齐的数组，其中A [n] [0]总是返回对角线上的元素. A [n] [1]将返回对角线右边的项目，A [n] [2]将返回对角线左边的项目，依此类推.然后，您只需要一个将矩阵索引[i，j]映射到参差不齐的数组索引[r] [s]的函数.

I would implement this as a ragged array, with A[n][0] always returning the element on the diagonal. A[n][1] will return the item just to the right of the diagonal, A[n][2] will return the item to the left of the diagonal, and so. Then, you just need a function that maps matrix index [i,j] to ragged array index[r][s].

这具有稀疏性的优点，如果您的值保持在对角线附近，则数组不会很长.

This has the advantage of sparsity, and if your values stay close to the diagonal the arrays are not very long.

或者，您可以有以下定义:

Alternatively, you could have this definition:

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

然后您将获得一个Row [].根据矩阵索引检索值如下所示:

Then you would have a Row[]. Retrieving a value based on matrix index would look like this:

//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语法有点朦胧，但是您应该明白这一点.

My C syntax is a little hazy, but you should get the idea.

根据您的演示，我建议这样做:

Based on your demonstration, I would recommend this:

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]];
}

您的初始化过程看起来像这样

Your initialization procedure would look something like this

//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
}

您需要进行一些处理，但是数据压缩并不便宜.

You need to do some processing, but data compression isn't cheap.

这篇关于C中的稀疏矩阵存储的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！