c++ - 改进稀疏线性系统的解决方案

Question

我在 Linux 系统上用 C++ 编写了一个代码来求解线性系统 A x = b，其中 A 是一个稀疏对称矩阵，使用以下两种方法:

1. 使用 UMFPACK 顺序分解并进行向后向前替换。
2. 使用 UMFPACK 进行顺序因式分解，然后使用 cuSPARSE 库进行向后向前替换。

我的系统配置是:CUDA 5.0版本，UMFPACK 5.6.2版本，Linux内核版本Debian 3.2.46-1，使用的显卡:GeForce GTX Titan。

从理论上讲，第二种方法应该比第一种方法执行得更好，而且错误最少或没有错误。但是，我观察到以下问题:

1. 使用 UMFPACK 函数 umfpack_di_solve 的后向/前向替换几乎比 CUDA 变体快 2 倍。
2. 对于某些矩阵，使用UMFPACK和CUDA得到的结果误差很大，最大误差为3.2537，而对于其他矩阵，误差为1e-16 的顺序。

附件是我的包含以下组件的 tar 文件:

• 一个文件夹 factorize_copy，其中包含我用来求解线性系统的主文件 fc.cu。它从 grid_*_CSC.m 文件中读取稀疏矩阵，这些文件也存在于同一目录中。为方便起见，所提供的三个稀疏矩阵的结果也在文本文件中给出。
• 一个文件夹，其中包含编译和运行 UMFPACK 的所有依赖项(我们也将其用于计算)。

tar 文件的链接是 https://www.dropbox.com/s/9qfs5awclshyk3b/code.tar.gz

如果您想运行代码，我在 factorize_copy 目录中提供了我在系统中使用的 MAKEFILE。您可能需要重新编译 UMFPACK 库。

586 x 586 稀疏矩阵的程序输出示例如下所示(请注意，与我们检查的其他稀疏矩阵相比，这种情况下的错误非常高)。

***** Reading the Grids

    Reading Grids Successful

***** Solving a sparse matrix of size: 586x586

***** Solving the grid on umfpack

***** Factorizing The Grid

-------------- CPU TIME for umfpack factorization is: 0.00109107

-------------- Wall-Clock TIME for umfpack factorization is: 0

    Factorizing the Grid successful

    Solving the grid on umfpack successful

-------------- CPU TIME for umfpack solve is: 6.281e-05

***** Allocating GPU memory and Copying data

---------------- CPU Time for Allocating GPU memory and Copying Data: 1.6

***** Performing b = P*b to account for the row ordering in A 

    Matrix-Vector (Pb) multiplication successful

***** Solving the system: LUx=b

    Analyzing Ly = b successful

    Solving Ly = b successful

    Analyzing Ux = y successful

    Solving Ux = y successful

***** Performing x = Q*x to account for the column ordering in A

    Matrix-Vector (Qx) multiplication successful

---------- GPU Time for the solve is: 5.68029 ms

##### Maximum error between UMFPACK and CUDA: 3.2537

##### Average error between UMFPACK and CUDA: 0.699926

***** Writing the results to the output files

    Result Written to the file 'vout_586.m' and the file 'vout_umfpack_586.m'

(Operation Successful!)

如果有人能指出在这种情况下可能出现的错误，我将不胜感激。如果有我遗漏的使用 CUDA 求解稀疏线性系统的更好方法，请告诉我。

编辑: 我弄清楚了为什么它在某些情况下会出错，而在某些情况下却不会。我在代码中调用内核函数时，每个 block 的线程数有误。但是，我仍然有获得加速的问题。

Answer 1

如果您正在处理一个在 CPU 上花费亚毫秒级时间的问题，考虑到 gpu 计算中涉及的所有延迟，您很难期望 gpu 执行得更快。