c++ - 固定维数(N=9)、对称、半正定稠密线性系统的快速解

Question

对于固定维数 (N=9) 的稠密线性系统(矩阵是对称的，半正定的)的快速求解，您会推荐哪种算法？

• 高斯消元法
• LU分解
• Cholesky 分解
• 等等？

类型是 32 位和 64 位 float 。

这样的系统将被解决数百万次，因此算法在维度 (n=9) 方面应该相当快。

附言推荐算法的健壮 C++ 实现示例。

1) What do you mean by "solved million of times"? Same coefficient matrix with a million of different right hand terms, or a million of distinct matrices?

数百万个不同的矩阵。

2) Positive _semi_definite means that matrix can be singular (to machine precision). How would you like to deal with this case? Just raise an error, or try to return some sensible answer?

引发错误是可以的。

Answer 1

矩阵是对称的、半正定的，Cholesky 分解 严格优于 LU 分解。 (无论矩阵大小如何，大约比 LU 快两倍。来源:Trefethen 和 Bau 的“数值线性代数”)

它实际上也是小型密集矩阵的标准(来源:我攻读计算数学博士学位)迭代方法的效率低于直接方法，除非系统变得足够大(快速的经验法则毫无意义，但是总是很高兴:在任何现代计算机上，任何小于 100*100 的矩阵绝对是一个需要直接方法而不是迭代方法的小矩阵)

现在，我不建议自己动手。那里有大量经过全面测试的好库。但是，如果我必须向您推荐一个，那就是Eigen。 :

• 无需安装(仅 header 库，因此无需链接库，仅#include<>)
• 稳健且高效(他们在主页上有很多基准测试，结果不错)
• 易于使用且有据可查

顺便说一下，here in the documentation ，您可以在一个漂亮、简洁的表格中了解他们的 7 种直接线性求解器的各种优缺点。似乎在您的情况下，LDLT(Cholesky 的变体)获胜