Addititive Polynomial Block Methods, Part I: Framework and Fully-Implicit Methods

Tommaso Buvoli, Ben S. SouthwortharXiv 2021 · OpenReview

TL;DR

This paper introduces a new framework for developing additive polynomial time integrators, specifically focusing on Fully-Implicit-Explicit (FIMEX) methods. These new methods offer improved stability and computational efficiency compared to existing IMEX methods, particularly for solving complex partial differential equations (PDEs) by leveraging advancements in implicit solvers and parallel computing.

What Problem Does This Paper Address?

Many scientific and engineering problems are modeled by systems of ordinary differential equations (ODEs) that are "additively partitioned." This means the overall rate of change of a system can be expressed as a sum of several independent components, each potentially requiring different numerical treatment. For instance, in fluid dynamics or heat transfer, different physical processes like advection, diffusion, and reaction might be modeled by separate terms.

Traditional methods often struggle with these partitioned systems, especially when some components are "stiff" (requiring very small time steps for explicit methods) while others are not. Implicit-Explicit (IMEX) methods offer a solution by treating stiff components implicitly and non-stiff ones explicitly. However, constructing high-order, stable, and efficient IMEX methods, especially those based on fully implicit solvers, has been a significant challenge. This paper aims to bridge this gap by generalizing an existing polynomial time integration framework to handle additively partitioned problems and introducing a novel class of FIMEX methods.

Methods

The core of this work lies in generalizing the "polynomial time integration framework" to handle additively partitioned ODEs. This framework builds numerical integrators by fitting polynomials through solution and derivative values at specific time points (nodes).

The authors introduce Fully-Implicit-Explicit (FIMEX) collocation methods based on Radau IIA nodes. These methods leverage:

  • Polynomial ODEs: The framework uses interpolating polynomials to approximate solutions and their derivatives.
  • Additive Partitioning: The ODE system is split into components, with the first treated implicitly and the second explicitly.
  • Fully-Implicit Runge-Kutta (RK) Integration: The implicit part of the FIMEX method is based on fully-implicit RK methods (specifically, Radau IIA), known for their good stability properties.
  • Polynomial Block Methods (PBMs): The framework allows for the construction of PBMs, which are a simpler form of general linear methods (GLMs) that advance a "block" of solution points simultaneously.
  • Iterators: A special type of polynomial method (with an extrapolation factor of zero) is used to compute accurate initial conditions for the PBMs, improving overall accuracy and stability.
  • Composite Methods: Combining a propagator (the main integration step) with multiple applications of an iterator allows for achieving higher orders of accuracy.

The novelty lies in extending the polynomial framework to additive systems and constructing FIMEX methods that combine the stability of fully implicit methods with the efficiency of explicit treatments for certain components, all while benefiting from recent advances in parallel solvers.

Datasets

Not discussed in the paper. The paper focuses on developing and analyzing numerical methods for ODEs and PDEs, rather than training on datasets.

Key Insights and Ideas

  • Generalizing Polynomial Integration: The polynomial time integration framework, previously used for single ODEs, can be effectively extended to handle additively partitioned systems, opening doors to a wider range of high-order methods.
  • FIMEX with Radau IIA: Combining fully-implicit Radau IIA methods for the stiff component with explicit treatments for others leads to FIMEX integrators with excellent stability properties, often outperforming existing IMEX methods.
  • Leveraging Implicit Solvers: Recent advancements in preconditioning and parallel solvers for fully implicit systems make these methods computationally tractable and competitive, even for large-scale problems.
  • Iterator for Accuracy Boost: Using polynomial iterators as a correction step significantly improves the accuracy and stability of the FIMEX methods, especially for challenging problems.
  • Parallelism for Speedup: The structure of FIMEX methods allows for parallel evaluation of function components, leading to substantial speedups, particularly for problems where implicit solves are trivial or function evaluations are expensive.

Key Results

  • Improved Stability: The proposed FIMEX-Radau and FIMEX-Radau* methods demonstrate superior linear stability regions compared to traditional IMEX-RK methods, especially for diffusive or mixed advection-diffusion problems.
  • Computational Efficiency: For PDEs on periodic domains, parallelization of function evaluations leads to significant speedups. In finite-element discretizations, the new methods achieve higher accuracy or comparable accuracy much faster than existing IMEX-RK methods.
  • High Accuracy: The methods can achieve high orders of accuracy, with composite methods showing significant improvements through iterator applications. For example, the FIMEX-Radau*(5,2) method achieved a relative error of 10⁻² approximately two times faster than standard RK methods.
  • Order Reduction Mitigation: The methods show resilience to order reduction issues, particularly in stiff problems like the Van der Pol equation, where they maintain higher convergence rates.

Limitations and Future Work

  • Complexity of Implementation: While the framework is general, constructing and implementing specific FIMEX methods can still be complex, especially for higher numbers of partitions or stages.
  • Choice of Splitting: The performance and stability of FIMEX methods can depend on how the ODE system is partitioned. The paper explores several splitting strategies but notes that optimal choices may vary.
  • Future Work: The authors plan to introduce new families of diagonally implicit IMEX-Polynomial integrators based on BDF ODE polynomials in a future work. They also aim to explore the advantages of fully implicit RK methods for differential algebraic equations and conservation of invariants, and develop adaptive strategies for stepsize control and iterator applications.

Summary updated

Abstract

In this paper we generalize the polynomial time integration framework to additively partitioned initial value problems. The framework we present is general and enables the construction of many new families of additive integrators with arbitrary order-of-accuracy and varying degree of implicitness. In this first work, we focus on a new class of implicit-explicit polynomial block methods that are based on fully-implicit Runge-Kutta methods with Radau nodes, and possess high stage order. We show that the new fully-implicit-explicit (FIMEX) integrators have improved stability compared to existing IMEX Runge-Kutta methods, while also being more computationally efficient due to recent developments in preconditioning techniques for solving the associated systems of nonlinear equations. For PDEs on periodic domains where the implicit component is trivial to invert, we will show how parallelization of the right-hand-side evaluations can be exploited to obtain significant speedup compared to existing serial IMEX Runge-Kutta methods. For parallel (in space) finite-element discretizations, the new methods can achieve orders of magnitude better accuracy than existing IMEX Runge-Kutta methods, and/or achieve a given accuracy several times times faster in terms of computational runtime.
BibTeX
@misc{buvoli2021addititive,
  author = {Tommaso Buvoli and Ben S. Southworth},
  title = {{Addititive Polynomial Block Methods, Part I: Framework and Fully-Implicit Methods}},
  year = {2021},
  eprint = {2109.03317},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.03317},
}
Figure