计算科学 - 稀疏对称矩阵的分解和求解大型线性方程的方法 - 吾爱随笔录

计算科学线性代数数值分析

2021-12-16 02:05:52

我在 mo.se 上问了同样的问题，有人建议 scicomp 会是一个更好的论坛。所以这里是：

我正在编写用于求解以下形式的线性方程的代码

A_{n \times n} \cdot x = 1_{n}

$A_{n\times n}\cdot x=1_n$

其中大约为，是一个对称矩阵，每行大约有非零条目。这使得它的大小几乎无法管理，但反转它是不可行的，而且我不确定哪种分解适合求解线性方程会导致稀疏矩阵。 $n$ $10^6$ $A$ $10^3$

因此问题：

1）希望分解是稀疏的吗？ $LU$

2) 是否可以利用 rhs 是一个标量来简化上述方程的解？

3) 处理这种大小的线性方程的最佳数值稳定算法是什么？

1个回答

在你的情况下，几乎没有希望。只有非常特定类型的稀疏矩阵具有稀疏分解。例如，（平凡的）对角矩阵和三对角矩阵。 $LU$
并不真地。你基本上说的是你想要所有列的总和。相反，如果 RHS 是稀疏的，您可能会使用选择性反转 (SelInv) 技术。 $A^{-1}$
我认为您的矩阵是真正对称的，因此您可以使用诸如共轭梯度（CG）之类的迭代方法。它所需要的只是您可以将矩阵向量乘积应用于任意矩阵。您可能需要一个预处理器，或者应用诸如代数/几何多重网格技术之类的东西。的低秩非对角结构有所了解，则可以考虑分层矩阵分解方法（这是非常先进的，并且那里的代码很少）。最后，您的矩阵不是那么稀疏。您可以考虑密集处理它们并使用核外稀疏 LU。如果没有其他方法，这实际上更像是最后的手段。 $A$

如果你知道是正定的，那么将上面的 LU 替换为 Cholesky，这样效率会更高一些。 $A$

其它你可能感兴趣的问题