Fast Direct Solvers
Per-Gunnar Martinsson and Michael O'Neil
本调查描述了一类被称为“快速直接求解器”的方法。 这些算法解决了解决由椭圆PDE或相关积分方程离散化产生的线性方程系统的问题。 Ax=b 当PDE直接离散时,矩阵A将是稀疏的,当使用积分方程公式时会密集。 无论哪种情况,大型问题的行业实践几十年来一直是使用迭代求解器,如多网格,GMRES或共轭梯度。 相反,直接求解器构建对A的反向的近似,或者,一个易于倒置的因子化(例如。 LU 或 Cholesky )。 在过去的几十年中,数值分析的一个主要发展是用于构建此类因子化或在线性时间执行此类反转的算法的出现。 这种方法必须利用矩阵A^-1是“数据稀疏”,通常情况下,它可以被tessellat化为具有低数值等级的块。 本调查为稀疏和致密的快速直接求解器提供了一个统一的上下文,介绍了具有最小符号开销的关键概念,并提供了帮助用户确定用于给定应用程序的最佳方法的指导。
This survey describes a class of methods known as "fast direct solvers". These algorithms address the problem of solving a system of linear equations Ax=b arising from the discretization of either an elliptic PDE or of an associated integral equation. The matrix A will be sparse when the PDE is discretized directly, and dense when an integral equation formulation is used. In either case, industry practice for large scale problems has for decades been to use iterative solvers such as multigrid, G...