A new parallel-in-time direct inverse method for nonlinear differential equations

Abstract We propose a new method for parallelization of the first-order backward difference discretization (BDF1) of the first-order time derivative in nonlinear partial differential equations, such as conservation law equations. The time derivative term is discretized by using the method of lines based on the implicit BDF1 scheme, while the inviscid and viscous terms are approximated by conventional 2nd-order central discretizations of the 1st- and 2nd-order derivatives in each spatial direction. The global system of nonlinear discrete equations in the space-time domain is solved by the Newton method for all time levels simultaneously. For the BDF1 discretization, this all-at-once system at each Newton iteration is block bidiagonal, which can be decoupled analytically by using the block Gaussian elimination so that each decoupled equation is associated with the corresponding time level. All product matrices on the left- and right-hand sides of this decoupled system of equations are calculated in parallel, such that their overall computational cost is linear in the number of spatial degrees of freedom. This allows for an efficient parallel-in-time implementation of the implicit BDF1 discretization for nonlinear differential equations of hyperbolic, parabolic or mixed type. Furthermore, the proposed parallel-in-time method preserves the quadratic rate of convergence of the Newton method of the sequential BDF1 scheme. Numerical results show that the new parallel-in-time BDF1 scheme provides the speedup of up to 28 on 32 computing cores for the 2-D nonlinear heat and Burgers equations with both smooth and discontinuous solutions.