预处理

预处理将线性系统转换为具有更有利谱的等效系统，从而使迭代求解器在更少的步骤中收敛；它通常是大型稀疏求解器性能中最重要的单一因素。

Definition

预处理器是一种矩阵，以隐式或显式方式应用于线性系统，它近似于系数矩阵或其逆，从而使预处理系统具有导致迭代方法更快收敛的谱特性。

Scope

本主题涵盖了近似逆（能够聚类特征值或降低条件数）的概念，预处理器的主要类型——对角和块对角、不完全LU和Cholesky分解、稀疏近似逆以及域分解和多重网格预处理器——以及预处理器的有效性与其构建和应用成本之间的权衡。

Core questions

• 预处理器如何改变系统的谱以加速迭代收敛？
• 什么构成一个好的预处理器，如何在近似质量与构建和应用成本之间取得平衡？
• 不完全分解和稀疏近似逆是如何构建的？
• 何时将多重网格或域分解方法用作预处理器而不是独立的求解器？

Key theories

谱变换

应用近似矩阵逆的预处理器会产生一个预处理算子，其特征值聚类或条件数降低；由于Krylov收敛取决于谱，这可以将迭代次数减少几个数量级。

不完全分解预处理器

不完全LU和不完全Cholesky分解在丢弃超出选定稀疏模式或阈值的填充项的同时计算近似三角因子，从而产生一个廉价的预处理器，它捕获了矩阵的大部分作用。

Mechanisms

选择预处理器M，使得用M求解系统成本低廉，并且预处理算子接近单位矩阵，使其特征值聚类。对角（Jacobi）预处理仅进行重新缩放；不完全LU或Cholesky分解通过在消元过程中丢弃小值或模式外项来构建近似的稀疏三角因子；稀疏近似逆直接构建一个稀疏的M来近似逆，这样只需要进行矩阵-向量乘法。更强大的预处理器在每次迭代中应用一个多重网格循环或一个域分解求解。在每种情况下，预处理器都在Krylov方法的每一步中应用，其设计平衡了它近似逆的程度与形成和应用它的成本。

Clinical relevance

预处理对于求解偏微分方程离散化和大规模优化产生的巨大病态系统具有决定性作用；正确的预处理器可以将停滞的迭代转化为在少数步骤内收敛的迭代，而选择和调整预处理器是计算科学和工程软件中的一个核心实际问题。

History

预处理与Krylov方法一起从20世纪70年代开始发展，不完全分解由Meijerink和van der Vorst于1977年引入，此后开发了广泛的代数和多级预处理器；现在它被认为对求解器性能的重要性往往超过Krylov方法本身的选择。

Key figures

• Yousef Saad
• Michele Benzi
• Henk van der Vorst
• Olof Widlund

Seminal works

• saad2003
• benzi2002

Frequently asked questions

什么使预处理器表现良好？

一个好的预处理器能紧密近似矩阵的逆，使得预处理系统对迭代方法来说易于处理，同时构建和应用成本低廉。关键在于平衡这些相互竞争的目标：一个更精确的预处理器每步成本更高，但需要的步骤更少。

求解器可以用作预处理器吗？

可以。多重网格的一个循环或一次域分解求解经常在Krylov方法内部用作预处理器，将Krylov迭代的鲁棒性与内部求解器的快速误差降低相结合。