快速稀疏矩阵乘法 [英] Fast sparse matrix multiplication

问题描述

对于类我必须为稀疏矩阵写我自己的线性方程求解器。
我可以随意使用任何类型的稀疏矩阵数据结构，我必须实现几个解决方案，包括接合渐变。

for class I have to write my own linear equation solver for sparse matrices. I am free to use any type of data structure for sparse matrices and I have to implement several solves, including conjuguate gradient.

我想知道是否有一个着名的方式来存储稀疏矩阵，使得与向量的乘法是相对快的。

I was wondering if there is a famous way to store sparse matrices such that multiplication with a vector is relatively fast.

现在我的稀疏矩阵基本上实现了一个包裹 std： ：map< std :: pair< int，int>，double> ，用于存储数据。这转换矩阵与向量到O（n 2）复杂度到O（n 2 log（n））的乘法，因为我必须对每个矩阵元素执行查找。
我已经查看过Yale稀疏矩阵格式，似乎一个元素的检索也在O（log（n）），所以我不知道是否会更快。

Right now my sparse matrices are basically implemented a wrapped std::map< std::pair<int, int>, double> which stores the data, if any. This transforms the multiplication of a matrix with from vector to a O(n²) complexity to a O(n²log(n)) as I have to perform look-up for each matrix elements. I've looked into the Yale Sparse matrix format and it seems that retrieval of an element is also in O(log(n)) so I'm not sure if it would be much faster.

对于引用，我有一个800x800的矩阵，填充5000个条目。

For reference I have a 800x800 matrix that is populated with 5000 entries. It takes roughly to 450 seconds solve such a system with the conjugate gradient method.

你认为使用另一个数据结构可以更快地做到这一点吗？

Do you think it's possible to do it much quicker with another data structure?

感谢！

推荐答案

最常见的选择是CSC或CSR存储。这些对于矩阵向量乘法都是有效的。它也很容易编写这些乘法程序，如果你必须自己做。

The most common choices are CSC or CSR storage. These are both efficient for matrix-vector multiplication. It's also very easy to code those multiplication routines, if you have to do it yourself.

也就是说，Yale存储也产生非常高效的矩阵向量乘法。如果你正在执行矩阵元素查找，那么你误解了如何使用格式。我建议你学习一些标准的稀疏库来了解如何实现矩阵矢量乘法。

That said, Yale storage also yields very efficient matrix-vector multiply. If you are performing matrix element lookup, then you have misunderstood how to use the format. I suggest you study some of the standard sparse libraries to learn how matrix-vector multiplication is implemented.

即使你当前的存储，你可以执行矩阵乘法在O（n）复杂。我所见过的所有稀疏矩阵向量乘法算法都归结到相同的步骤。例如考虑y = Ax。

Even with your current storage you can perform matrix multiplication in O(n) complexity. All sparse matrix-vector multiplication algorithms that I have ever seen boil down to the same steps. For example consider y = Ax.

1. 将结果向量y归零。


2. 初始化迭代器对于矩阵的非零元素，A。


3. 获取矩阵的下一个非零元素，A [i，j]注意，i，j的模式不遵循规则模式。它只是反映存储A的非零元素的顺序。


4. y [i] + = A [i，j] * x [j]


5. 如果有更多的元素A，goto 3.

1. Zeroise the result vector, y.
2. Initialise an iterator for the non-zero elements of the matrix, A.
3. Get the next non-zero element of the matrix, A[i,j] say. Note that the pattern of i,j doesn't follow a regular pattern. It simply reflects the order in which the non-zero elements of A are stored.
4. y[i] += A[i,j]*x[j]
5. If there are more elements of A, goto 3.

我怀疑你正在写经典的double for循环密码乘法码：

I suspect you are writing the classic double for loop dense multiplication code:

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

这就是引导你执行查找。

and that's what is leading you to perform lookups.

但我不建议你坚持你的 std :: map 存储。这不会是超级高效。我建议CSC主要是因为它是最广泛使用的。

But I'm not suggesting that you stick with your std::map storage. That's not going to be super efficient. I'd recommend CSC mainly because it is the most widely used.

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