6

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

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

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

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

4

3 回答 3

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 的数值求解器在适用的情况下通常可以产生卓越的性能。

于 2015-06-22T20:12:20.983 回答
1

是否有标准方法可以为多个 b_i 批量执行此操作?

一种选择是使用 CUDA 的 cuSOLVER 中的批处理重构模块,但我不确定它是否是标准的。

cuSOLVER 中的批量重构模块提供了一种有效的方法,可以基于 LU 分解来求解具有固定左侧稀疏矩阵(或具有固定稀疏模式但系数不同的矩阵)的批量线性系统。在与其相关的官方文档(截至 CUDA 10.1)中只能找到一些部分完成的代码片段。一个完整的例子可以在这里找到。

于 2020-06-18T10:00:48.617 回答
0

如果您不介意使用开源库,您还可以查看 CUSP: CUSP 快速入门页面

它有一套相当不错的求解器,包括一些预处理方法: CUSP Preconditioner Examples

只要您的 GPU 有足够的板载内存,平滑聚合预处理器(代数多重网格的一种变体)似乎工作得很好。

于 2015-08-15T01:57:56.057 回答