CG求解器如何求解非正定稀疏矩阵

计算科学 线性求解器 稀疏矩阵 迭代法 共轭梯度
2021-11-25 18:14:27

我正在使用CUSP CG 求解器,并在佛罗里达大学稀疏矩阵集合中的几个稀疏矩阵上运行它。求解器能够求解非正定稀疏矩阵。我的理解是 CG 求解器无法求解非正定稀疏矩阵?那么 CUSP 的 CG 求解器是如何做到的呢?

2个回答

我强烈推荐以下阅读:

简而言之,如果矩阵是非正定的,则不能保证 CG 会失败它可能能够解决它(对于某些 RHS 和某些容差),但它不应该这样做,并且可能会比适当的方法收敛得慢。

您绝对应该研究其他迭代求解器(例如,BiCGStab 或其他东西,具体取决于您的问题属性)。

注意:我不熟悉 CUPS,所以我还会检查内部是否有一个函数可以检查矩阵的属性并切换到其他算法(不太可能,但可能)——尤其是在求解器日志不明确的情况下。

除了安东的回答,我想提供一个特殊情况,即使它是非正定的,CG 也能够解决一个系统。

在模拟不可压缩流体时,如果流体域被纯 Dirichlet BCs 包围(即仅指定边界速度,并且我们没有任何自由表面或边界压力),那么我们在系统中有一个零空间。因此矩阵是非正定的。

那个零空间全是一,e=(1,1,,1)T. 这并不奇怪,因为我们只有压力梯度p在等式中。如果p是一个解决方案p=0, 那么也是p+ce, 在哪里c是任何常数。

由于零空间是已知的,所以每当我们在 CG 中进行矩阵乘法时,我们都可以投影出该零空间:

k=Axk=k(ke)e/N
(N是方阵的宽度或高度A)

然后仅通过这个额外的投影,非正定系统仍然可以通过 CG 解决。