多次求解稀疏非对称系统的最快方法

计算科学 稀疏矩阵 迭代法 线性系统 矩阵分解
2021-12-15 18:00:44

我必须解决一个系统Ax(n)=b(n)多次,A是一个稀疏(其结构的大部分为五对角线)、非对称、常数矩阵。

目前,我正在使用行和列排列执行 LU 分解,即PAQ=LU,然后我使用这个分解来计算x(k)通过以下方式:

x(n)=Q(UL(Pb(n)))

我最近阅读了有关稀疏系统的迭代方法的文章,但我对它们不是很熟悉。您能否告诉我是否有任何迭代方法可以执行得更快,以及它是否已经在 Matlab 中实现?

谢谢,马努

1个回答

一般来说,对于许多右手边 (RHS) 问题,直接求解器是一种更可行的解决方案,原因如下:

  1. 主要计算在分解步骤期间执行(对所有 RHS 只执行一次),并且解决方案查找(对于每个 RHS)要便宜得多。
  2. 直接求解器不会受到矩阵条件差的影响,或者换句话说,您不必寻找一个好的预处理器(迭代求解器需要)确保O(1)每个 RHS(相对容易)和每个矩阵(更难)的迭代都是由数值模拟产生的。

注意。当然,如果矩阵非常病态,直接求解器也会受到影响,但是,直接求解器扩展了问题的“动态范围”,无需重新制定问题即可解决。

有几件事我应该提到:

  1. 通常,不建议使用基于 LU 分解的逆来求解。您可能希望使用更有效的反向替换 LU 子例程。从您的公式中,尚不清楚您是否以正确的方式进行操作。
  2. 由于您的矩阵是稀疏的并且具有稳定的结构,因此我将研究稀疏直接求解器,而不是完全直接求解器。它应该显着加快计算速度。
  3. 在您的情况下,我会考虑进行部分旋转(PA=LU) 仅,而不是全旋转 (PAQ=LU)。这可能会加快计算速度。
  4. 将高性能 LAPACK 库连接到 MATLAB 也是一种选择。

关于稀疏迭代求解器:

  1. 您可以尝试不同的迭代求解器,包括 GMRES、BiCGStab、TFQMR 等。您的任务是为它们提供快速的稀疏矩阵向量积。它们中的大多数已经包含在 MATLAB 中。如果你在那里使用稀疏矩阵存储,使用它们应该不会太难。
  2. 从上面重复一个关于直接求解器的优点的项目:您必须为所有这些方法实现一个体面的预处理器,以减少它们收敛所需的迭代次数。一种选择是使用不完全 LU (iLU) 作为预处理器。有更复杂和更简单的选项可用。
  3. 使用迭代求解器有点棘手。你必须弄清楚你的系统条件有多好,什么是预处理器的合理选择,与迭代求解器一起使用的良好容差是什么(获得的解决方案的准确性),感受什么样的问题(在您正在使用数值模拟解决的问题的子集)导致您的迭代算法不收敛或收敛缓慢。