RungeKutta Solution of Initial Value Problems: Methods, Algorithms and Implementation
(1998) Abstract
 The last decades have seen a strongly increasing use of computers for modeling larger and more complex systems. This has been made possible by a combination of increasing computer power and easytouse graphical modeling environments and libraries of components. An important class of systems are described by initial value problems for dynamical systems, and the increasing size and complexity imply that problems are more often either Differential Algebraic Equations (DAE), or stiff Ordinary Differential Equations (ODE).
Timestepping methods for solving DAEs and stiff ODEs have been extensively studied, and the methods have also been implemented in a number of successful codes. Turning a method into a practical... (More)  The last decades have seen a strongly increasing use of computers for modeling larger and more complex systems. This has been made possible by a combination of increasing computer power and easytouse graphical modeling environments and libraries of components. An important class of systems are described by initial value problems for dynamical systems, and the increasing size and complexity imply that problems are more often either Differential Algebraic Equations (DAE), or stiff Ordinary Differential Equations (ODE).
Timestepping methods for solving DAEs and stiff ODEs have been extensively studied, and the methods have also been implemented in a number of successful codes. Turning a method into a practical implementation requires a number of supporting algorithms, but in spite of their importance we find these to be less wellstudied than the timestepping methods.
The supporting algorithms are the key to adaptivity: how to estimate errors, which stepsizes to use, how to start iterations, when to terminate them, when to refactor Jacobians, etc.
The goal of this dissertation is to partially bridge the gap between methods and implementations by studying and improving the algorithms supporting Implicit RungeKutta (IRK) methods applied to DAEs and stiff ODEs.
Studies of supporting algorithms require both the construction and analysis of simplified models and experimental validation, where we only vary the algorithmic aspect under consideration. The experimental validation has been carried out in the Generic ODE Solving System (Godess), which has been developed in parallel to this thesis and facilitates the necessary means for a strict validation.
The dissertation focuses on the iterative process used to compute the intermediate stages in the steps of the IRK methods. The difficulties in the iterative process and the results presented in this dissertation are:
The iterative process need accurate predictors to minimize the number of iterations. We construct predictors of orders exceeding the stage order of the method. We also prove that this is only possible by adapting the predictors to the individual stages. The iterations must be terminated after a finite number of iterations. The effects of this are studied in this dissertation and the results include: For algebraically accurate IRK methods starting with an explicit stage we introduce stage derivative reuse (SDR) methods. We prove stiffness independent bounds for the error propagation in the SDR methods. All algebraically accurate IRK methods can employ SDR methods as accurate and inexpensive error estimators. The iterations are in general terminated when the iteration error is below a predefined tolerance. We relate the error at the endpoint of the step to the errors in the stages. We present a formula relating the tolerance for the iterations to the tolerance for the timestepping method. The factorization of the Jacobian is often kept for several consecutive steps. An algorithm giving nearly optimal balance between the time spent in the iterations for the stages and the refactorization and recomputation of the Jacobian is given. The algorithm uses a simple criterion based on the rate of convergence of the iterations. An analysis verifies that the algorithm also has the right asymptotic behavior. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/39211
 author
 Olsson, Hans ^{LU}
 supervisor
 opponent

 Thuné, Michael, Associate Professor, Department of Scientific Computing, Uppsala University
 organization
 publishing date
 1998
 type
 Thesis
 publication status
 published
 subject
 keywords
 Computer science, stiffness, software, computational process, differential algebraic equations, ordinary differential equations, RungeKutta, initial value problems, timestepping, system, kontroll, numerisk analys, Datalogi, control, numerical analysis, systems
 pages
 178 pages
 publisher
 Department of Computer Science, Lund University
 defense location
 Building E, Lund Institute of Technology
 defense date
 19981211 13:15:00
 external identifiers

 other:ISRN: LUTEDX/(TECS1009)/1178/(1998)
 language
 English
 LU publication?
 yes
 additional info
 Article: H. Olsson:"Object Oriented Solvers for Initial Value Problems",in Modern Software Tools for Scientific Computingpage 4562(proceedings of SciTools'96 published by Birkhäuser Boston) Article: H. Olsson and G. Söderlind "Stage Value Predictors and Efficient Newtoniterations in Implicit RungeKutta Methods"Will appear in SIAM Journal on Scientific Computing20(1):185202, 1999 Article: H. Olsson and G. Söderlind"The Approximate RungeKutta Computation Process"Submitted for publication
 id
 da2f862e09d445ea946816d317f8c3a2 (old id 39211)
 date added to LUP
 20160404 10:05:05
 date last changed
 20181121 20:56:37
@phdthesis{da2f862e09d445ea946816d317f8c3a2, abstract = {{The last decades have seen a strongly increasing use of computers for modeling larger and more complex systems. This has been made possible by a combination of increasing computer power and easytouse graphical modeling environments and libraries of components. An important class of systems are described by initial value problems for dynamical systems, and the increasing size and complexity imply that problems are more often either Differential Algebraic Equations (DAE), or stiff Ordinary Differential Equations (ODE).<br/><br> <br/><br> Timestepping methods for solving DAEs and stiff ODEs have been extensively studied, and the methods have also been implemented in a number of successful codes. Turning a method into a practical implementation requires a number of supporting algorithms, but in spite of their importance we find these to be less wellstudied than the timestepping methods.<br/><br> <br/><br> The supporting algorithms are the key to adaptivity: how to estimate errors, which stepsizes to use, how to start iterations, when to terminate them, when to refactor Jacobians, etc.<br/><br> <br/><br> The goal of this dissertation is to partially bridge the gap between methods and implementations by studying and improving the algorithms supporting Implicit RungeKutta (IRK) methods applied to DAEs and stiff ODEs.<br/><br> <br/><br> Studies of supporting algorithms require both the construction and analysis of simplified models and experimental validation, where we only vary the algorithmic aspect under consideration. The experimental validation has been carried out in the Generic ODE Solving System (Godess), which has been developed in parallel to this thesis and facilitates the necessary means for a strict validation.<br/><br> <br/><br> The dissertation focuses on the iterative process used to compute the intermediate stages in the steps of the IRK methods. The difficulties in the iterative process and the results presented in this dissertation are:<br/><br> <br/><br> The iterative process need accurate predictors to minimize the number of iterations. We construct predictors of orders exceeding the stage order of the method. We also prove that this is only possible by adapting the predictors to the individual stages. The iterations must be terminated after a finite number of iterations. The effects of this are studied in this dissertation and the results include: For algebraically accurate IRK methods starting with an explicit stage we introduce stage derivative reuse (SDR) methods. We prove stiffness independent bounds for the error propagation in the SDR methods. All algebraically accurate IRK methods can employ SDR methods as accurate and inexpensive error estimators. The iterations are in general terminated when the iteration error is below a predefined tolerance. We relate the error at the endpoint of the step to the errors in the stages. We present a formula relating the tolerance for the iterations to the tolerance for the timestepping method. The factorization of the Jacobian is often kept for several consecutive steps. An algorithm giving nearly optimal balance between the time spent in the iterations for the stages and the refactorization and recomputation of the Jacobian is given. The algorithm uses a simple criterion based on the rate of convergence of the iterations. An analysis verifies that the algorithm also has the right asymptotic behavior.}}, author = {{Olsson, Hans}}, keywords = {{Computer science; stiffness; software; computational process; differential algebraic equations; ordinary differential equations; RungeKutta; initial value problems; timestepping; system; kontroll; numerisk analys; Datalogi; control; numerical analysis; systems}}, language = {{eng}}, publisher = {{Department of Computer Science, Lund University}}, school = {{Lund University}}, title = {{RungeKutta Solution of Initial Value Problems: Methods, Algorithms and Implementation}}, year = {{1998}}, }