对于各种b,稀疏带状Ax = b的批量CUDA解决方案

Question

我有一个稀疏的带状矩阵A,我想(直接)解决Ax = b.我有大约500个向量b,所以我想解决相应的500 x.我是CUDA的新手,所以我对我有哪些选择感到困惑.

cuSOLVER有一个批量直接求解器cuSolverSP,用于在这里使用QR的稀疏A_i x_i = b_i .(由于A的条件很好,我对LU也没问题.)但是,据我所知,我无法利用我所有的A_i都是一样的事实.

另一种选择是首先确定CPU或GPU上的稀疏LU(QR)因子分解,然后并行执行GPU上的后置替换(分别为backsub和matrix mult)吗？如果cusolverSp <t> csrlsvlu()用于一个b_i,是否有一种标准方法可以为多个b_i批量执行此操作？

最后,由于我对此没有直觉,考虑到必要的开销,我是否应该期望在这些选项中的GPU加速？x的长度约为10000-100000.谢谢.

Answer 1

我目前正在做类似的事情。我决定基本上将 CUDA SDK 附带的共轭梯度和 0 级不完整 cholesky 预处理共轭梯度求解器实用程序示例包装到一个小类中。

您可以在以下路径下的 CUDA_HOME 目录中找到它们 samples/7_CUDALibraries/conjugateGradient：/Developer/NVIDIA/CUDA-samples/7_CUDALibraries/conjugateGradientPrecond

基本上，您可以将矩阵加载到设备内存中一次（对于 ICCG，计算相应的调节器/矩阵分析），然后使用不同的 b 向量调用求解内核。

我不知道你期望你的矩阵能带结构是什么样子，但如果它是对称的并且是对角占主导的（沿每行和列的非对角线带与对角线的符号相反，并且它们的总和小于对角线条目）或正定（没有特征值为 0 的特征向量。）那么 CG 和 ICCG 应该有用。或者，如果您愿意对它们进行编码，则各种多重网格算法也是另一种选择。

如果您的矩阵只是半正定矩阵（例如，至少有一个特征值为零的特征向量），您仍然可以经常使用 CG 或 ICCG，只要您确保： 1) 右侧（b 向量）与零空间正交（零空间意味着特征值为零的特征向量）。2) 您获得的解与零空间正交。

有趣的是，如果确实有一个非平凡的零空间，那么不同的数值求解器可以为同一个系统提供不同的答案。解决方案最终会因零空间的线性组合而有所不同......这个问题在我最终明白之前给我带来了很多工时的调试和挫败感，所以意识到它是件好事。

最后，如果您的矩阵具有循环带结构，您可以考虑使用基于快速傅立叶变换 (FFT) 的求解器。基于 FFT 的数值求解器在适用的情况下通常可以产生卓越的性能。