Fast Solution of Fully Implicit Runge-Kutta and Discontinuous Galerkin in Time for Numerical PDEs, Part II: Nonlinearities and DAEs

Ben S. Southworth, Oliver A. Krzysik, Will Pazner

TL;DR

This paper presents a novel framework for efficiently solving complex partial differential equations (PDEs) using implicit Runge-Kutta (IRK) methods, particularly for nonlinear problems and those with algebraic constraints (DAEs). The authors introduce new linearization techniques and robust preconditioning strategies that significantly reduce computational cost and improve convergence, making high-order IRK methods practical for challenging fluid dynamics simulations.

What Problem Does This Paper Address?

Solving partial differential equations (PDEs) numerically often involves discretizing them in space and then using time-stepping methods to advance the solution. Fully implicit Runge-Kutta (IRK) methods are attractive for their accuracy and stability, especially for stiff problems where explicit methods struggle. However, their practical application to large-scale nonlinear PDEs has been hindered by the computational expense of solving the large, coupled nonlinear systems that arise at each time step. Traditional methods like simplified Newton iterations often lack robustness, and exact Newton methods are computationally prohibitive. This paper tackles the challenge of making high-order IRK methods efficient and practical for nonlinear PDEs and differential-algebraic equations (DAEs), which are common in fields like fluid dynamics.

Methods

The core contribution of this paper lies in developing new ways to approximate the large, nonlinear systems that arise from IRK discretizations. The authors introduce:

  • Novel Linearizations: They propose several new linearization techniques for the nonlinear IRK stage equations. These methods aim to provide faster and more robust convergence than simplified Newton approaches.
  • Block 2x2 Systems: A key aspect of their approach is reducing the problem to solving a series of smaller, block 2x2 systems. This significantly simplifies the computational burden.
  • Effective Preconditioning: For cases where exact Newton iterations are desired, they develop an effective preconditioner for the true Jacobian.
  • Theoretical Guarantees: They provide theoretical analysis proving that their preconditioned 2x2 operator has a condition number bounded by a small constant, independent of spatial discretization and time step, and with only weak dependence on the order of accuracy or number of stages.
  • Algorithm Design: A self-contained algorithm description is provided, integrating these new techniques.
  • DAE Extension: The framework is extended to handle differential-algebraic equations (DAEs), which are common in incompressible fluid dynamics.

Datasets

Not discussed in the paper. The paper focuses on developing and testing numerical methods on established fluid dynamics problems.

Key Insights and Ideas

  • Decomposition is Key: Breaking down the large, complex nonlinear systems into smaller, manageable 2x2 blocks is crucial for efficient solution.
  • Preconditioning for Robustness: The proposed preconditioning strategies are not just about speed but also about ensuring robust convergence, even for challenging nonlinear problems and DAEs.
  • Bridging Theory and Practice: The authors provide strong theoretical backing for their methods, demonstrating bounded condition numbers, which translates to predictable and efficient performance in practice.
  • Leveraging Existing Infrastructure: The new methods are designed to be compatible with existing preconditioners used for simpler time-stepping schemes (like backward Euler), making them easier to integrate into existing codes.
  • High-Order Accuracy is Achievable: The work demonstrates that high-order accuracy (up to 10th order) can be achieved with IRK methods without prohibitive computational cost.

Key Results

  • Significant Speedup: For challenging nonlinear fluid flow problems (compressible Euler/Navier-Stokes, incompressible Euler/Navier-Stokes in vorticity-streamfunction form), the proposed methods require roughly half the number of preconditioner applications compared to standard SDIRK methods for similar accuracy.
  • High-Order Accuracy Demonstrated: The methods successfully achieve high-order accuracy (up to 10th order with Gauss IRK) on test cases like the isentropic Euler vortex and the double shear layer problem.
  • Robustness Across Problems: The techniques are shown to be effective for both nonlinear PDEs and index-1 DAEs, including complex scenarios like flow over a NACA airfoil and the double shear layer problem.
  • Improved Iteration Counts: For the NACA airfoil test case, more accurate approximations of the Jacobian led to faster overall runtimes, despite higher per-iteration costs.

Limitations and Future Work

  • Assumption for L1 ≠ L2: In the theoretical analysis for the case where the linearized operators L1 and L2 are different, the authors rely on an assumption (L1w, L2w) ≥ 0, which they believe is not strictly necessary but was required for their proof. They hope for a more general proof.
  • Problem-Specific Analysis for Index-2 DAEs: While the framework is extended to DAEs, the authors note that for more general index-2 DAEs, preconditioning (34) might require more problem-specific analysis than the theory developed for ODEs.
  • Performance Dependence: The authors acknowledge that the performance of different solver strategies can be problem-dependent, particularly for smaller time steps or less stiff problems where simplified Newton might still be competitive.

Future work could explore removing the assumption for L1 ≠ L2, developing more general preconditioning strategies for higher-index DAEs, and further investigating the performance trade-offs between different nonlinear iteration approximations.

Summary updated

Abstract

Fully implicit Runge-Kutta (IRK) methods have many desirable accuracy and stability properties as time integration schemes, but high-order IRK methods are not commonly used in practice with large-scale numerical PDEs because of the difficulty of solving the stage equations. This paper introduces a theoretical and algorithmic framework for solving the nonlinear equations that arise from IRK methods (and discontinuous Galerkin discretizations in time) applied to nonlinear numerical PDEs, including PDEs with algebraic constraints. Several new linearizations of the nonlinear IRK equations are developed, offering faster and more robust convergence than the often-considered simplified Newton, as well as an effective preconditioner for the true Jacobian if exact Newton iterations are desired. Inverting these linearizations requires solving a set of block 2x2 systems. Under quite general assumptions, it is proven that the preconditioned 2x2 operator's condition number is bounded by a small constant close to one, independent of the spatial discretization, spatial mesh, and time step, and with only weak dependence on the number of stages or integration accuracy. Moreover, the new method is built using the same preconditioners needed for backward Euler-type time stepping schemes, so can be readily added to existing codes. The new methods are applied to several challenging fluid flow problems, including the compressible Euler and Navier Stokes equations, and the vorticity-streamfunction formulation of the incompressible Euler and Navier Stokes equations. Up to 10th-order accuracy is demonstrated using Gauss IRK, while in all cases 4th-order Gauss IRK requires roughly half the number of preconditioner applications as required by standard SDIRK methods.
BibTeX
@article{southworth2022fast,
  author = {Ben S. Southworth and Oliver A. Krzysik and Will Pazner},
  title = {{Fast Solution of Fully Implicit Runge-Kutta and Discontinuous Galerkin in Time for Numerical PDEs, Part II: Nonlinearities and DAEs}},
  journal = {SIAM J. Sci. Comput.},
  year = {2022},
  url = {https://openreview.net/forum?id=MeT3mchs08},
}
Figure