谱法中通常如何处理稠密系统?

计算科学 线性求解器 稀疏矩阵 谱法 密集矩阵
2021-12-24 04:32:42

与将原始 PDE 转换为稀疏线性系统的有限元 (FEM) 或有限差分方法 (FDM) 不同,谱方法返回密集线性系统。对于一个大型系统,使用直接消除方法是不切实际的,因此自然选择迭代方法。据我所知,大多数都是针对稀疏矩阵的。

那么,这个问题在科学计算界是如何处理的呢?对于切比雪夫多项式,FFT 可能会有所帮助。那么其他多项式呢,例如 Legendre 或 Lobatto?这个困难是这种方法没有像 FEM 或 FDM 那样广泛使用的原因吗?

2个回答

这里有几点需要说明。

准确性

谱方法适当地表现出谱(超代数)收敛。因此,需要更小的矩阵尺寸来产生与 FEM 或 FDM 相同的精度。当然,具体尺寸和相对优势取决于所选的具体方案以及所需的稳定性和分辨率。一个很好的例子如下所示(SW Arm eld et al. JCAM, 2009),其中计算了 Orr-Sommerfeld 算子的特征谱,并在标准 FDM 和各种光谱离散化之间进行了精度比较。事实上,这是频谱方法如何在计算科学中无处不在的一个主要例子,标志性论文 Orszag JFM, 1971 首次说明了这一点。

收敛

矩阵结构与求解

正如您正确指出的那样,光谱方法会产生密集且通常是非结构化的差分矩阵。计算特征系统或这种矩阵的线性求解的费用无疑比 FDM 方案中的对称稀疏系统更昂贵,如果它们的大小相同的话。同样,确切的费用取决于具体的方案和解决方法。解决这两种矩阵系统的方法在文献中得到了广泛的研究和详细记录。

调理

这是一个微妙但非常重要的一点。光谱方法通常受到可怕的限制。具体来说,多项式方法具有条件数

κσmaxσmin=O(N2p)
在哪里p是最高导数的阶,并且N是搭配点的数量。准确评估条件差矩阵的解决方案需要小心谨慎,有时还需要扩展精度,这使得此类操作成本更高。这也限制了您能够在给定精度下获得的准确度(您也可以方便地在上图中看到这种行为)。

有趣的是,上面的表达式为κ已经产生了旨在拆分运算符的方法,以便您有两个耦合顺序p/2方程,而不是单阶p方程。还有其他特殊方法可以解决您的问题,使其在计算上不那么可怕,尽管我不会在这里全部记录。

即使使用谱方法,矩阵仍然是稀疏的:如果您固定多项式次数(即使是一个很大的数)并细化网格,矩阵每行的非零数保持不变。这就是稀疏矩阵的定义。它也与您在每个单元格上使用的基础类型无关——Legendre、Gauss-Lobatto、Chebyshev,它们都只在单元格上局部耦合,因此会导致稀疏矩阵。

最好使用什么是一个单独的问题。首先,适用于低阶多项式次数的常用迭代求解器仍然有效。矩阵向量产品只是成本更高,因为矩阵不那么稀疏。作为回报,您可以有效地实现无矩阵的谱方法,即,在实际未形成矩阵的情况下,仅在与向量相乘时实现其动作。

一个更大的问题是如何最好地对线性系统进行预处理。我喜欢对此进行足够详细的评论的经验。