Preconditioners for the Discontinuous Galerkin time-stepping method of arbitrary order

Basting, Steffen; Bänsch, Eberhard

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 51 (2017) no. 4, pp. 1173-1195.

We develop a preconditioner for systems arising from space-time finite element discretizations of parabolic equations. The preconditioner is based on a transformation of the coupled system into block diagonal form and an efficient solution strategy for the arising $2\times 2$ blocks. The suggested strategy makes use of an inexact factorization of the Schur complement of these blocks, for which uniform bounds on the condition number can be proven. The main computational effort of the preconditioner lies in solving implicit Euler-like problems, which allows for the usage of efficient standard solvers. Numerical experiments are performed to corroborate our theoretical findings.

T. Akman and B. Karasözen, Variational time discretization methods for optimal control problems governed by diffusion–convection–reaction equations. J. Comput. Appl. Math. 272 (2014) 41–56. | DOI | MR | Zbl

G. Akrivis, Ch. Makridakis and R.H. Nochetto, Galerkin and Runge–Kutta methods: unified formulation, a posteriori error estimates and nodal superconvergence. Numer. Math. 118 (2011) 429–456. | DOI | MR | Zbl

E. Bänsch,, P. Morin and R.H. Nochetto, Preconditioning a class of fourth order problems by operator splitting. Numer. Math. 118 (2011) 197–228. | DOI | MR | Zbl

A. Bonito, I. Kyza and R.H Nochetto, Time-discrete higher-order ale formulations: Stability. SIAM J. Num. Anal. 51 (2013) 577–604. | DOI | MR | Zbl

A. Bonito, I. Kyza and R.H. Nochetto, A dG approach to higher order ale formulations in time. In Recent Developments in Discontinuous Galerkin Finite Element Methods for Partial Differential Equations. Springer (2014) 223–258. | MR | Zbl

J.C. Butcher, On the implementation of implicit Runge–Kutta methods. BIT Numer. Math. 16 (1976) 237–240. | DOI | MR | Zbl

K. Eriksson and C. Johnson, Adaptive finite element methods for parabolic problems i: A linear model problem. SIAM J. Numer. Anal. 28 (1991) 43–77. | DOI | MR | Zbl

A. Ern and J.L. Guermond, Theory and practice of finite elements. Vol. 159. Springer Science & Business Media (2013). | MR | Zbl

L.C. Evans, Partial differential equations. Vol. 19 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2nd edition (2010). | MR | Zbl

R. Freund, On conjugate gradient type methods and polynomial preconditioners for a class of complex non-hermitian matrices. Numer. Math. 57 (1990) 285–312. | DOI | MR | Zbl

R.W. Freund, Conjugate gradient-type methods for linear systems with complex symmetric coefficient matrices. SIAM J. Sci. Stat. Comput. 13 (1992) 425–448. | DOI | MR | Zbl

G.H. Golub and Ch.F. Van Loan, Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 4th edition (2013). | MR | Zbl

E. Hairer and G. Wanner, Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems. Springer, second revised edition (1991). | MR | Zbl

R. Herbin and F. Hubert, Benchmark on discretization schemes for anisotropic diffusion problems on general grids. In Finite volumes for complex applications V. Wiley (2008) 659–692. | MR

S. Hussain, F. Schieweck and S. Turek, Higher order Galerkin time discretizations and fast multigrid solvers for the heat equation. J. Numer. Math. 19 (2011) 41–61. | DOI | MR | Zbl

L.O. Jay, Inexact simplified Newton iterations for implicit Runge–Kutta methods. SIAM J. Numer. Anal. 38 (2000) 1369–1388. | DOI | MR | Zbl

L.O. Jay and Th. Braconnier, A parallelizable preconditioner for the iterative solution of implicit Runge–Kutta-type methods. J. Comput. Appl. Math. 111 (1999) 63–76. | DOI | MR | Zbl

P. Lesaint and P.A. Raviart,On a Finite Element Method for Solving the Neutron Transport Equation. Univ. Paris VI, Labo. Analyse Numérique (1974). | MR | Zbl

R.J. Leveque, High-resolution conservative algorithms for advection in incompressible flow. SIAM J. Numer. Anal. 33 (1996) 627–665. | DOI | MR | Zbl

Ch. Makridakis and R.H. Nochetto, A posteriori error analysis for higher order dissipative methods for evolution problems. Numer. Math. 104 (2006) 489–514. | DOI | MR | Zbl

K.-A. Mardal, T.K. Nilssen and G.A. Staff, Order-optimal preconditioners for implicit Runge–Kutta schemes applied to parabolic pdes. SIAM J. Sci. Comput. 29 (2007) 361–375. | DOI | MR | Zbl

A. Napov and Y. Notay, An algebraic multigrid method with guaranteed convergence rate. SIAM J. Sci. Comput. 34 (2012) A1079–A1109. | DOI | MR | Zbl

Y. Notay, An aggregation-based algebraic multigrid method. Electr. Trans. Numer. Anal. 37 (2010) 123–146. | MR | Zbl

Y. Notay, Aggregation-based algebraic multigrid for convection-diffusion equations. SIAM J. Sci. Comput. 34 (2012) A2288–A2316. | DOI | MR | Zbl

Y. Notay, AGMG software and documentation. See http://homepages.ulb.ac.be/˜ynotay/AGMG/ (2015).

Th. Richter, A. Springer and B. Vexler, Efficient numerical realization of discontinuous Galerkin methods for temporal discretization of parabolic problems. Numer. Math. 124 (2013) 151–182. | DOI | MR | Zbl

F. Schieweck and G. Matthies, Higher order variational time discretizations for nonlinear systems of ordinary differential equations. Otto-von-Guericke-Universität Magdeburg. Preprint (2011) 23.

D. Schötzau and Ch. Schwab, Time discretization of parabolic problems by the hp-version of the discontinuous Galerkin finite element method. SIAM J. Numer. Anal. 38 (2000) 837–875. | DOI | MR | Zbl

D. Schötzau and Ch. Schwab, hp-discontinuous galerkin time-stepping for parabolic problems. C. R. Acad. Sci. Sér. I. Math. 333 (2001) 1121–1126. | MR | Zbl

G.A. Staff, K.A. Mardal and T.K. Nilssen, Preconditioning of fully implicit Runge-Kutta schemes for parabolic PDEs. Model. Identif. Control 27 (2006) 109. | DOI | MR

M. Stoll, One-shot solution of a time-dependent time-periodic PDE-constrained optimization problem. IMA J. Numer. Anal. (2013) drt019. | MR | Zbl

M. Stoll and A. Wathen, All-at-once solution of time-dependent Stokes control. J. Comput. Phys. 232 (2013) 498–515. | DOI | MR

R. Temam, Navier-Stokes equations. Theory and numerical analysis. Vol. 2. North-Holland Publishing Co., Amsterdam-New York-Oxford (1977). | MR | Zbl

V. Thomée, Galerkin Finite Element Methods for Parabolic Problems. Number 1054 in Springer Lecture notes in Mathematics. Springer, 2 edition (1984). | MR | Zbl

Sh.W. Walker, Felicity: Finite element implementation and computational interface tool for you. MATLAB/C++, Tech. Report (2013).

S. Weller and S. Basting, Efficient preconditioning of variational time discretization methods for parabolic partial differential equations. ESAIM: M2AN 49 (2015) 331–347. | DOI | Numdam | MR | Zbl

Th. Werder, K. Gerdes, D. Schötzau and Ch. Schwab, hp-discontinuous Galerkin time stepping for parabolic problems. Comput. Methods Appl. Mech. Engrg. 190 (2001) 6685–6708. | DOI | MR | Zbl