Fast parallel 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 theoretical and algorithmic framework for efficiently solving complex nonlinear partial differential equations (PDEs) using fully implicit Runge-Kutta (IRK) methods. By developing new linearization techniques and robust preconditioning strategies for the resulting linear systems, the authors enable high-order accurate and stable time integration for challenging fluid dynamics problems, significantly reducing computational cost compared to existing methods.

What Problem Does This Paper Address?

High-order fully implicit Runge-Kutta (IRK) methods offer excellent accuracy and stability for solving time-dependent partial differential equations (PDEs), especially those with stiff behavior. However, their practical application to large-scale nonlinear PDEs has been hindered by the computational expense of solving the numerous nonlinear equations that arise at each time step. This paper tackles this challenge by developing efficient methods to solve these nonlinear systems, including those with algebraic constraints (Differential Algebraic Equations or DAEs), which are common in fluid dynamics.

Methods

The core of this work lies in developing new ways to approximate the Jacobian matrix that arises from the linearization of the nonlinear IRK stage equations. Instead of solving the full, large system, the authors propose solving smaller, block 2x2 systems. They introduce novel linearizations and a block-triangular preconditioner that, under certain assumptions, guarantees a well-conditioned linear system. This approach leverages existing preconditioners for simpler time-stepping schemes, making it easier to integrate into existing codes. The theoretical analysis proves that the condition number of the preconditioned system is bounded by a small constant, independent of spatial discretization and time step, and only weakly dependent on the order of accuracy.

Datasets

Not discussed in the paper. The paper focuses on numerical methods and their application to benchmark fluid flow problems.

Key Insights and Ideas

  • Bridging the gap between theory and practice: The paper provides a practical framework to unlock the potential of high-order IRK methods, which have been theoretically attractive but computationally prohibitive for nonlinear PDEs.
  • Efficient linearization for nonlinear systems: The development of new linearization techniques that avoid solving the full, coupled system is a key innovation.
  • Robust preconditioning for 2x2 systems: The theoretical guarantee of a bounded condition number for the preconditioned 2x2 systems is crucial for the efficiency of iterative solvers.
  • Leveraging existing infrastructure: The fact that the new methods use preconditioners compatible with simpler schemes like backward Euler significantly lowers the barrier to adoption.
  • Extending to DAEs: The framework is shown to be applicable to DAEs, broadening its utility for problems with inherent algebraic constraints.

Key Results

The paper demonstrates significant improvements in computational efficiency for solving nonlinear PDEs using high-order IRK methods. For challenging fluid flow problems (compressible Euler/Navier-Stokes, incompressible Euler/Navier-Stokes), the proposed methods achieve up to 10th-order accuracy. Notably, 4th-order Gauss IRK requires roughly half the number of preconditioner applications compared to standard SDIRK methods. Numerical results show that the new methods can achieve high accuracy with very large time steps, outperforming traditional approaches.

Limitations and Future Work

The theoretical analysis relies on certain assumptions about the eigenvalues of the Runge-Kutta matrix and the field of values of the linearized spatial operators. While these assumptions are often met in practice, their limitations for certain types of problems (e.g., indefinite saddle-point systems arising in incompressible flow) are acknowledged. The authors suggest that for more general DAEs (like index-2 DAEs), more problem-specific analysis might be required. Future work could explore further extensions to more complex DAE systems and investigate the performance of these methods on a wider range of physical applications.

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 parallel 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},
}

Loading related content...

Figure