High order linearly implicit methods for evolution equations

Dujardin, Guillaume; Lacroix-Violet, Ingrid

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 56 (2022) no. 3, pp. 743-766

This paper introduces a new class of numerical methods for the time integration of evolution equations set as Cauchy problems of ODEs or PDEs. The systematic design of these methods mixes the Runge–Kutta collocation formalism with collocation techniques, in such a way that the methods are linearly implicit and have high order. The fact that these methods are implicit allows to avoid CFL conditions when the large systems to integrate come from the space discretization of evolution PDEs. Moreover, these methods are expected to be efficient since they only require to solve one linear system of equations at each time step, and efficient techniques from the literature can be used to do so. After the introduction of the methods, we set suitable definitions of consistency and stability for these methods. This allows for a proof that arbitrarily high order linearly implicit methods exist and converge when applied to ODEs. Eventually, we perform numerical experiments on ODEs and PDEs that illustrate our theoretical results for ODEs, and compare our methods with standard methods for several evolution PDEs.

Classification : 65M12, 65M70, 65L20, 65L06, 81Q05, 35Q41, 35K05
Keywords: Cauchy problems, evolution equations, time integration, numerical methods, high order, linearly implicit methods

[1] G. Akrivis and M. Crouzeix, Linearly implicit methods for nonlinear parabolic equations. Math. Comput. 73 (2004) 613–635. | MR | Zbl

[2] G. Akrivis and C. Lubich, Fully implicit, linearly implicit and implicit-explicit backward difference formulae for quasi-linear parabolic equations. Numer. Math. 131 (2015) 713–735. | MR

[3] G. Bader and P. Deuflhard, A semi-implicit mid-point rule for stiff systems of ordinary differential equations. Numer. Math. 41 (1983) 373–398. | MR | Zbl

[4] A. Berman and R. J. Plemmons, Nonnegative matrices in the mathematical sciences. Classics in Applied Mathematics. Society for Industrial Mathematics (1987). | MR | Zbl

[5] C. Besse, A relaxation scheme for the nonlinear Schrödinger equation. SIAM J. Numer. Anal. 42 (2004) 934–952. | MR | Zbl

[6] C. Besse, G. Dujardin and I. Lacroix-Violet, High order exponential integrators for nonlinear Schrödinger equations with application to rotating Bose-Einstein condensates. SIAM J. Numer. Anal. 55 (2017) 1387–1411. | MR

[7] C. Besse, S. Descombes, G. Dujardin and I. Lacroix-Violet, Energy-preserving methods for nonlinear Schrödinger equations. IMA J. Numer. Anal. 41 (2020) 618–653. | MR

[8] J. Butcher, Diagonally-implicit multi-stage integration methods. Appl. Numer. Math. 11 (1993) 347–363. | MR | Zbl

[9] J. Butcher, General linear methods. Selected Topics in Numerical Methods. Comput. Math. App. 31 (1996) 105–112. | MR | Zbl

[10] J. Butcher and G. Wanner, Runge-Kutta methods: some historical notes. Special Issue Celebrating the Centenary of Runge-Kutta Methods. Appl. Numer. Math. 22 (1996) 113–151. | MR | Zbl

[11] M. Calvo, J. De Frutos and J. Novo, Linearly implicit Runge-Kutta methods for advection-reaction-diffusion equations. Appl. Numer. Math. 37 (2001) 535–549. | MR | Zbl

[12] Q. Cheng and J. Shen, Multiple Scalar Auxiliary Variable (MSAV) approach and its application to the phase-field vesicle membrane model. SIAM J. Sci. Comput. 40 (2018) A3982–A4006. | MR

[13] J. Crank and P. Nicolson, A practical method for numerical evaluation of solutions of partial differential equations of the heat-conduction type. Proc. Cambridge Philos. Soc. 43 (1947) 50–67. | MR | Zbl

[14] G. Dahlquist, A special stability problem for linear multistep methods. BIT Numer. Math. 3 (1963) 27–43. | MR | Zbl

[15] M. Delfour, M. Fortin and G. Payre, Finite-difference solutions of a nonlinear Schrödinger equation. J. Comput. Phys. 44 (1981) 277–288. | MR | Zbl

[16] G. Dujardin, Exponential Runge-Kutta methods for the Schrödinger equation. Appl. Numer. Math. 59 (2009) 1839–1857. | MR | Zbl

[17] R. Frank, J. Schneid and C. W. Ueberhuber, The concept of $B$-convergence. SIAM J. Numer. Anal. 18 (1981) 753–780. | MR | Zbl

[18] E. Hairer, G. Wanner, Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems, Vol. 14. Springer Verlag Series in Comput. Math. Springer Berlin Heidelberg (1996). | MR | Zbl

[19] E. Hairer, S. Nørsett and G. Wanner, Solving Ordinary Differential Equations I: Nonstiff Problems, Vol. 8. Springer (1993). | MR | Zbl

[20] E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, 2nd edition. Springer Series in Computational Mathematics. Vol. 31. Springer, Berlin Heidelberg (2002). | MR | Zbl

[21] K. Hayakawa, On nonexistence of global solutions of some semilinear parabolic differential equations. Proc. Jpn. Acad. 49 (1973) 503–505. | MR | Zbl

[22] M. Hochbruck and A. Ostermann, Exponential Runge-Kutta methods for parabolic problems. Tenth Seminar on Numerical Solution of Differential and Differential-Algebraic Equations (NUMDIFF-10). Appl. Numer. Math. 53 (2005) 323–339. | MR | Zbl

[23] M. Hochbruck and A. Ostermann, Exponential integrators. Acta Numer. 19 (2010) 209–286. | MR | Zbl

[24] P. Kaps and G. Wanner, A study of Rosenbrock-type methods of high order. Numer. Math. 38 (1981) 279–298. | MR | Zbl

[25] B. Kovàcs and C. Lubich, Linearly implicit full discretization of surface evolution. Numer. Math. 140 (2018) 121–152. | MR

[26] W. Kutta, Beitrag zur naherungsweisen integration totaler differentialgleichungen. Z. Math. Phys. 46 (1901) 435–453. | JFM

[27] C. Lubich, On splitting methods for Schrödinger-Poisson and cubic nonlinear Schrödinger equations. Math. Comp. 77 (2008) 2141–2153. | MR | Zbl

[28] C. Lubich and A. Ostermann, Linearly implicit time discretization of non-linear parabolic equations. IMA J. Numer. Anal. 15 (1995) 555–583. | MR | Zbl

[29] R. I. Mclachlan, Families of high-order composition methods. Numer. Algorithms 31 (2002) 233–246. | MR | Zbl

[30] H. H. Rosenbrock, Some general implicit processes for the numerical solution of differential equations. Comput. J. 5 (1963) 329–330. | MR | Zbl

[31] C. Runge, Ueber die numerische auflösung von differentialgleichungen. Math. Annal. 46 (1895) 167–178. | MR | JFM

[32] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd edition. Society for Industrial and Applied Mathematics (2003). | MR | Zbl

[33] J. Shen and J. Xu, Convergence and error analysis for the Scalar Auxiliary Variable (SAV) schemes to gradient flows. SIAM J. Numer. Anal. 56 (2018) 2895–2912. | MR

[34] K. Strehmel and R. Weiner, $B$-convergence results for linearly implicit one step methods. BIT Numer. Math. 27 (1987) 264–281. | MR | Zbl

[35] K. Strehmel, R. Weiner and I. Dannehl, A study of $B$-convergence of linearly implicit Runge-Kutta methods. Computing 40 (1988) 241–253. | MR | Zbl

[36] M. Suzuki, Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations. Special Issue Celebrating the Centenary of Runge–Kutta Methods. Phys. Lett. A 146 (1990) 319–323. | MR

[37] J. Wensch, K. Strehmel and R. Weiner, A class of linearly-implicit Runge-Kutta methods for multibody systems. Appl. Numer. Math. 22 (1996) 381–398. | MR | Zbl

[38] H. Yoshida, Construction of higher order symplectic integrators. Phys. Lett. A 150 (1990) 262–268. | MR