×

Minimal residual multistep methods for large stiff non-autonomous linear problems. (English) Zbl 1458.65074

Summary: The purpose of this work is to introduce a new idea of how to avoid the factorization of large matrices during the solution of stiff systems of ODEs. Starting from the general form of an explicit linear multistep method we suggest to adaptively choose its coefficients on each integration step in order to minimize the norm of the residual of an implicit BDF formula. Thereby we reduce the number of unknowns on each step from \(n\) to \(O(1)\), where \(n\) is the dimension of the ODE system. We call this type of methods Minimal Residual Multistep (MRMS) methods. In the case of linear non-autonomous problem, besides the evaluations of the right-hand side of ODE, the resulting numerical scheme additionally requires one solution of a linear least-squares problem with a thin matrix per step. We show that the order of the method and its zero-stability properties coincide with those of the used underlying BDF formula.
For the simplest analog of the implicit Euler method the properties of linear stability are investigated. Though the classical absolute stability analysis is not fully relevant to the MRMS methods, it is shown that this one-step method is applicable in stiff case. In the numerical experiment section we consider the fixed-step integration of a two-dimensional non-autonomous heat equation using the MRMS methods and their classical BDF counterparts. The starting values are taken from a preset slowly-varying exact solution. The comparison showed that both methods give similar numerical solutions, but in the case of large systems the MRMS methods are faster, and their advantage considerably increases with the growth of dimension. Python code with the experimental code can be downloaded from the GitHub repository https://github.com/bfaleichik/mrms.

MSC:

65L04 Numerical methods for stiff equations
65L05 Numerical methods for initial value problems involving ordinary differential equations
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65L20 Stability and convergence of numerical methods for ordinary differential equations

Software:

RODAS; mrms; GitHub
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] J. Van Der Houwen, P.; P. Sommeuer, B., A special class of multistep Runge—Kutta methods with extended real stability interval, IMA J. Numer. Anal., 2, 183-209 (1982) · Zbl 0481.65038
[2] Lebedev, V., Explicit difference schemes with variable time steps for solving stiff systems of equations, (Vulkov, L.; Wasniewski, J.; Yalamov, P., Numerical Analysis and Its Applications. Numerical Analysis and Its Applications, Lecture Notes in Computer Science, vol. 1196 (1997), Springer Berlin Heidelberg), 274-283
[3] Faleichik, B.; Bondar, I.; Byl, V., Generalized picard iterations: A class of iterated Runge-Kutta methods for stiff problems, J. Comput. Appl. Math., 262, 37-50 (2014), Selected Papers from NUMDIFF-13 · Zbl 1301.65059
[4] Brown, P. N.; Hindmarsh, A. C., Matrix-free methods for stiff systems of ODE’s, SIAM J. Numer. Anal., 23, 3, 610-638 (1986) · Zbl 0615.65078
[5] Rosenbrock, H. H., Some general implicit processes for the numerical solution of differential equations, Comput. J., 5, 4, 329-330 (1963) · Zbl 0112.07805
[6] Curtiss, C.; Hirschfelder, J. O., Integration of stiff equations, Proc. Natl. Acad. Sci., 38, 3, 235-243 (1952) · Zbl 0046.13602
[7] Ortega, J. M.; Rheinboldt, W. C., Iterative solution of nonlinear equations in several variables, (Computer Science and Applied Mathematics (1970), Academic Press), I-XV, 1-572 · Zbl 0949.65053
[8] Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 1002.65042
[9] Hairer, E.; Wanner, G., Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0859.65067
[10] Demmel, J. W., Applied Numerical Linear Algebra (1997), SIAM · Zbl 0879.65017
[11] Faleichik, B., MRMS Methods experimental code, GitHub Repository (2019)
[12] Li, X. S.; Shao, M., A supernodal approach to incomplete LU factorization with partial pivoting, ACM Trans. Math. Software, 37, 4, 43:1-43:20 (2011) · Zbl 1365.65078
[13] Dahlquist, G., Convergence and stability in the numerical integration of ordinary differential equations, Math. Scand., 4, 1, 33-53 (1956) · Zbl 0071.11803
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.