C++ 快速稀疏矩阵乘法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15693584/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fast sparse matrix multiplication
提问by lezebulon
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.
我想知道是否有一种著名的方法来存储稀疏矩阵，以便与向量相乘相对较快。
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(n2) complexity to a O(n2log(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.
现在我的稀疏矩阵基本上实现了一个std::map< std::pair<int, int>, double>存储数据的包装，如果有的话。这将矩阵与 from 向量的乘法转换为 O(n2) 复杂度到 O(n2log(n))，因为我必须对每个矩阵元素执行查找。我研究了耶鲁稀疏矩阵格式，似乎元素的检索也在 O(log(n)) 中，所以我不确定它是否会快得多。
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.
作为参考，我有一个 800x800 的矩阵，其中填充了 5000 个条目。用共轭梯度法求解这样一个系统大约需要 450 秒。
Do you think it's possible to do it much quicker with another data structure?
您认为使用另一种数据结构可以更快地完成吗？
thanks!
谢谢！
回答by David Heffernan
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.
最常见的选择是CSC 或 CSR 存储。这些对于矩阵向量乘法都很有效。如果您必须自己编写，那么编写这些乘法例程也很容易。
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.
也就是说，耶鲁存储还可以产生非常有效的矩阵向量乘法。如果您正在执行矩阵元素查找，那么您误解了如何使用格式。我建议你研究一些标准的稀疏库来了解矩阵向量乘法是如何实现的。
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.
即使使用您当前的存储，您也可以以 O(n) 复杂度执行矩阵乘法。我见过的所有稀疏矩阵向量乘法算法都归结为相同的步骤。例如考虑 y = Ax。
- Zeroise the result vector, y.
- Initialise an iterator for the non-zero elements of the matrix, A.
- 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.
- y[i] += A[i,j]*x[j]
- If there are more elements of A, goto 3.
- 将结果向量 y 归零。
- 为矩阵 A 的非零元素初始化迭代器。
- 获取矩阵的下一个非零元素，例如 A[i,j]。请注意， i,j 的模式不遵循常规模式。它只是反映了 A 的非零元素的存储顺序。
- y[i] += A[i,j]*x[j]
- 如果 A 的元素较多，则转到 3。
I suspect you are writing the classic double for loop dense multiplication code:
我怀疑您正在编写经典的 double for 循环密集乘法代码：
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.
这就是导致您执行查找的原因。
But I'm not suggesting that you stick with your std::mapstorage. That's not going to be super efficient. I'd recommend CSC mainly because it is the most widely used.
但我并不是建议您坚持使用std::map存储。这不会非常高效。我推荐 CSC 主要是因为它使用最广泛。
