论文标题
抛物线PDE的完全隐式runge-kutta方案的最佳和低内存近乎最佳的预处理
Optimal and Low-Memory Near-Optimal Preconditioning of Fully Implicit Runge-Kutta Schemes for Parabolic PDEs
论文作者
论文摘要
Runge-kutta（RK）方案，尤其是高斯 - 莱格德尔（Gauss-Legendre）和其他一些完全隐式的RK（FIRK）方案，对于抛物线偏微分方程的时间整合由于其A稳定性和高阶精度而需要时间整合。但是，与对角线隐含的RK（或Dirk）方案相比，为其构建最佳的预处理的最佳预处理更具挑战性。为了应对这一挑战，我们首先引入了数学上最佳的预处理，称为块复杂的Schur分解（BCSD），块真正的Schur分解（BRSD）和Block Jordan形式（BJF），由块循环前循环预处理器和Jordan形式的IRK溶液技术动机。然后，我们通过使用具有单个对角色值的优化上三角形矩阵在实际Schur分解中近似于真实Schur分解中的准三角矩阵，从而得出了有效的，几乎最佳的单基因近似BRSD（SABRSD）。 SABRSD的一个理想特征是它具有可比的内存要求和分解（或设置）成本，即Dirk（Sdirk）。我们使用（接近）线性复杂性（例如Multilevel ILU，ILU（0））或具有基于ILU的基于ILU的Multigrid方法，使用（接近）线性复杂性的不完全分解来近似这些预处理技术中的对角线块。我们在右键基本的GMRE中应用块预处理程序，以使用有限元和有限差方法在3D中求解对流扩散方程。我们表明，BCSD，BRSD和BJF在GMRES的迭代方面显着优于其他预处理，而SABRSD在计算成本方面与他们及其先前的最新情况竞争，同时需要最少的内存。
Runge-Kutta (RK) schemes, especially Gauss-Legendre and some other fully implicit RK (FIRK) schemes, are desirable for the time integration of parabolic partial differential equations due to their A-stability and high-order accuracy. However, it is significantly more challenging to construct optimal preconditioners for them compared to diagonally implicit RK (or DIRK) schemes. To address this challenge, we first introduce mathematically optimal preconditioners called block complex Schur decomposition (BCSD), block real Schur decomposition (BRSD), and block Jordan form (BJF), motivated by block-circulant preconditioners and Jordan form solution techniques for IRK. We then derive an efficient, near-optimal singly-diagonal approximate BRSD (SABRSD) by approximating the quasi-triangular matrix in real Schur decomposition using an optimized upper-triangular matrix with a single diagonal value. A desirable feature of SABRSD is that it has comparable memory requirements and factorization (or setup) cost as singly DIRK (SDIRK). We approximate the diagonal blocks in these preconditioning techniques using an incomplete factorization with (near) linear complexity, such as multilevel ILU, ILU(0), or a multigrid method with an ILU-based smoother. We apply the block preconditioners in right-preconditioned GMRES to solve the advection-diffusion equation in 3D using finite element and finite difference methods. We show that BCSD, BRSD, and BJF significantly outperform other preconditioners in terms of GMRES iterations, and SABRSD is competitive with them and the prior state of the art in terms of computational cost while requiring the least amount of memory.
