Abstract
Many stiff systems of ordinary differential equations (ODEs) modeling practical problems can be partitioned into loosely coupled subsystems. In this paper the objective of the partitioning is to permit the numerical integration of one time step to be performed as the solution of a sequence of small subproblems. This reduces the computational complexity compared to solving one large system and permits efficient parallel execution under appropriate conditions. The subsystems are integrated using methods based on low order backward differentiation formulas.
This paper presents an adaptive partitioning algorithm based on a classical graph algorithm and techniques for the efficient evaluation of the error introduced by the partitioning.
The power of the adaptive partitioning algorithm is demonstrated by a real world example, a variable step-size integration algorithm which solves a system of ODEs originating from chemical reaction kinetics. The computational savings are substantial.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
I. S. Duff and J. K. Reid, An implementation of Tarjan’s algorithm for the block triangularization of a matrix, ACM Trans. Math. Softw., 4 (1978), pp. 137–147.
M. W. Gery, G. Z. Whitten, J. P. Killus, and M. C. Dodge, A photochemical kinetics mechanism for urban and regional computer modeling, J. Geophys. Res., 94 (1989), pp. 12925–12956.
O. Hertel, R. Berkowicz, J. Christensen, and O. Hov, Test of two numerical schemes for use in atmospheric transport-chemistry models, Atmos. Environ., 27A (1993), pp. 2591–2611.
E. Lelarasmee, A.E. Ruehli, and A. L. Sangiovanni-Vincentelli, The waveform relaxation method for time-domain analysis of large scale integrated circuits, IEEE Trans. Comp. Aided Des. Integr. Circ. Syst., 1 (1982), pp. 131–145.
J. Sand and S. Skelboe, Stability of backward Euler multirate methods and convergence of waveform relaxation, BIT, 32 (1992), pp. 350–366.
S. Skelboe, Accuracy of decoupled implicit integration formulas, SIAM J. Sci. Comput., 21 (2000), pp. 2206–2224.
S. Skelboe, INTGR for the integration of stiff systems of ordinary differential equations, Report IT 9 (1977), Institute of Circuit Theory and Telecommunication, Technical University of Denmark, Lyngby, Denmark.
S. Skelboe, Methods for parallel integration of stiff systems of ODEs, BIT, 32 (1992), pp. 689–701.
S. Skelboe, Partitioning techniques for ODEs for decoupled implicit integration formulas, DIKU Report 05/04, January 28, 2004.
R. S. Varga, Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs, NJ, 1962.
Z. I. Woźnick, Basic comparison theorems for weak and weaker matrix splittings, Electron. J. Linear Alg., 8 (2001), pp. 53–59.
Author information
Authors and Affiliations
Corresponding author
Additional information
In memory of Germund Dahlquist (1925–2005).
AMS subject classification (2000)
65L06, 65Y05
Rights and permissions
About this article
Cite this article
Skelboe, S. Adaptive partitioning techniques for ordinary differential equations . Bit Numer Math 46, 617–629 (2006). https://doi.org/10.1007/s10543-006-0074-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-006-0074-z