c++ - 求解线性方程组的最有效方法

Question

我有一个 (n x n) 对称矩阵 A 和一个 (n x 1) vector B。基本上，我只需要为 x 求解 Ax = b。问题是A可能会很大。所以我正在寻找在 C++ 中求解线性方程组的最有效算法。我查看了 Eigen 库。显然它有一个 SVD 方法，但我被告知它很慢。求解 x=inverse(A)*b 似乎也不是最理想的。 uBLAS 更快吗？有没有更有效的方法？谢谢。

编辑:矩阵 A 是正定的，不是稀疏的。

Answer 1

求解 Ax = b 形式的线性方程组的最佳方法是执行以下操作。

• 将A分解成A = M1 * M2的格式(其中M1和M2是三角形的)
• 使用反向替换解决 M1 * y = b 为 y
• 使用反向替换解决 x 的 M2 * x = y

对于方阵，第 1 步将使用 LU Decomposition .

对于非方阵，第 1 步将使用 QR Decomposition .

如果矩阵 A 正定且不稀疏，您将使用 Cholesky Decomposition第一步。

如果你想使用eigen，你必须先decompose it然后 triangular solve它。

如果这仍然很慢，谢天谢地，有许多线性代数库可以帮助提高性能。您应该寻找的例程是 dpotrs。一些实现了这个的库如下:

• Netlib 的 lapack:Documentation和 Download (免费)
• 英特尔的 MKL:Documentation和 Download (非商业用途免费)。
• AMD 的 ACML:Download (免费)
• 等 ionic :Download (免费，多核优化)
• 岩浆:Download (免费，在 CUDA、OpenCL 中实现)
• CULA:Download (免费增值，在 CUDA 中实现)。

如果您在整个项目中使用 eigen，您可以按照 here 中所述连接所需的 LAPACK 例程.