计算科学 - 执行稀疏矩阵向量和矩阵转置向量乘法的库 - 吾爱随笔录

计算科学稀疏矩阵矩阵

2021-12-04 08:50:43

我的主要兴趣是形式的稀疏矩阵向量和矩阵转置向量乘法y=y+AA'x。有没有y=y+AA'x高效执行的库？我已经调查过 SPARSKIT、MKL、ARPACK，......但我无法找到相关的例程。操作不是y=y+AA'x广泛使用的吗？

4个回答

即使乘积矩阵已经可用，矩阵乘积通常也可以更快地应用为只有对于扩展因子极低的特殊图，乘积矩阵才会更快。 $B = AA^T$ $A (A^T x)$ $B$

二维或更多维的 PDE 图具有更高的扩展因子。例如，如果是 2D 矩形网格上的 9 点差分运算，则（或）是 25 点运算；应用 9 点操作两次更快。在 3D 中，模拟是 27 点和 125 点。 $A$ $A^2$ $A A^T$ $A$ $A^2$

请注意最坏的情况：如果包含单个密集列，则是密集的。 $A$ $A A^T$

所有稀疏线性代数库都支持应用和。 $A$ $A^T$

通常你会做以下两件事之一：

我不知道有任何库可以直接计算，如果有的话，他们可能会在幕后使用 (1)。 $AA'x$

SPARSKIT 有和例程，它们分别被称为和；这些用于压缩稀疏行格式的矩阵，在 SPARSKIT 文档中进行了描述。 $A\cdot x$ $A'\cdot x$ amuxatmux

你有语言偏好吗？如果您只是在试验并且不需要您的程序超快，您可以尝试 python 中的Scipy 稀疏矩阵模块，这比使用 Fortran 更容易。这些也将具有您正在寻找的功能。

编辑：由于您想要快速并且您提到了 GPU 计算，您可能需要考虑CUSP 库。ellpack 矩阵格式特别适合在 GPU 机器上使用，尽管有一些例外情况。

如果可以接受 C++ 库，我建议尝试 Eigen。

性能好，使用方便。特别是，您上面的表达式可以这样写：

Eigen::SparseMatrix<double> a(n,n);
Eigen::VectorXd y(n), x(n);
y += a*a.transpose()*x;

如果您想在共享内存中获得良好的并行性能，您可以尝试压缩稀疏块 (CSB) 代码： http: //gauss.cs.ucsb.edu/~aydin/csb/csb.html

它专门设计用于为 SpMV 和 SpMV_T（转置矩阵情况）提供同样良好的并行性能，而无需显式转置矩阵。无论非零分布如何，它还具有可证明的并行性保证（它可以尽可能偏斜）

其它你可能感兴趣的问题