求解非对称非对角占优稀疏系统的最佳方法

计算科学 线性代数 稀疏矩阵
2021-12-04 10:36:58

的迭代线性求解器通常要求当被分解为Ax=bA

A=D+M

其中 D 是对角矩阵且具有零对角线,的元素应该在中的条目上占主导地位,以便迭代求解器能够很好地执行。MDM

如果不是这种情况并且的条目变得非常小怎么办?D

那我应该使用直接求解器吗?

更具体地说,我要解决的线性系统涉及一个矩阵 ,其中非对角线部分是常数,但对角线部分取决于参数在某些非琐碎的方式。到目前为止,我还没有找到解决每个的方法。

A(ω)=D(ω)+M
ωA(ω)x=bω

对角线条目的形式为其中是一个取决于我们所在行的实数,而是一个非常小的收敛因子,而是虚数单位。时,这会导致数值不稳定吗?Ajj=ω+zj+iηzjηiω+z0

的性质还有一件事:如果将精确设置保证有极点。这是因为最终我使用这个矩阵来计算频域中的(多体)格林函数,并且这些函数需要收敛因子来将它们的极点从实轴上移开。每行非对角矩阵元素的绝对值之和最多为,但对角线上总会有一些实部非常接近或等于0的条目。A(ω)η0A(ω)η10

3个回答

虽然它对哪些方法可以工作设置了一些限制,但缺乏对角线优势或对称性并不是天生的灾难。然而,这些属性通常与更困难的非局部影响和粗化困难问题相关联,许多“黑盒”求解器将无法工作。为了以更实质性的方式回答您的问题,我们需要了解这个特定系统的细节(物理、离散化、参数制度)。

我的实际建议是从直接求解器开始,仅在必要时才深入研究迭代求解器。您可以将职业生涯用于为特定难题开发强大的迭代求解器。

根据 Gershgorin 定理,对角占优矩阵保证具有所有正的(如果对角线的元素都是正的)或所有负的(如果元素都是负的)特征值。大多数迭代方法仅在迭代矩阵的特征值位于复平面的特定区域时才有效,因此对角优势确保所有特征值都具有严格的正实部或严格的负实部(或者所有特征值都位于某个数字的特定半径)。

如果您的迭代矩阵的特征值位于特定方法的规定区域之外,则它通常无法正常工作。那里有很多方法,但如果不了解更多关于范围的信息,我就无法选择一个具体的方法A(ω).

您的系统有多大/稀疏?你真的需要迭代地解决这个问题吗?

我建议尝试使用稀疏求解器在 Matlab 或 Octave 中求解(只需使用“稀疏”初始化矩阵,然后使用反斜杠)。如果这对您有用,那么直接使用 UMFPACK,这是 Matlab 和 Octave 在内部用于稀疏求解的方法。