Time discretisation

From CFD-Wiki

Latest revision as of 02:25, 20 January 2008

Introduction

In seeking a numerical solution for a partial differential equation, discretization has to be carried out in both space and time. Although, mathematically, the time dependent terms, i.e. transient terms, are just derivatives with respect to an independent variable (time), these terms require special treatment when looked upon from a physical point of view.

Without loss of generality, in the context of conservation laws, transient terms describe the accumulation in time, of a certain variable inside an infinitesimal control volume. Discretization of the transient terms is usually called temporal discretization or discretization in time. It is always desirable to seek a time dependent solution especially that the discretization of the transient terms is directly associated with the stability of a numerical solution. If the flow at hand is inherently steady, it is generally advisable to compute a time dependent solution and reach the steady state solution hereafter.

With regard to the semi-discretised Navier-Stokes equations (NSE), there are two distinct cases to consider. These are the cases where the resulting system of equations are ordinary differential equations (ODEs) or differential algebraic equations (DAEs). Typically, solving the NSE for a compressible fluid gives rise to a coupled system of ODEs whereas solving the NSE in low-Mach number or incompressible contexts gives rise to a coupled system of DAEs. A DAE structure to the NSE generally arises because of a desire to suppress the fast acoustic time scale of the flow. This fast time scale is often irrelevant to many analyses yet it makes for a more costly computational analysis. Consider a whistle. Upon blowing into a whistle, a convective flow begins whose velocity is maybe one meter per second. Simultaneously, sound also eminates from the whistle at approximately 340 meters per second. The NSE are clearly supporting two distinct time scales. The idea is then to "project out" this fast time scale so that the remaining evolution equations describe a non-acoustic flow field. By doing this projecting, the differential equation for density ( continuity ) is replaced by an algebraic relation. Physically, this algebraic relation describes the condition for which the fast time scales are suppressed. As it acts as a constraint, and it exists in a lower dimensional space, it is often referred to as the constraint manifold. The goal is then to integrate the remaining differential equations subject to their solution trajectories staying on the surface of the constraint manifold. To complicate matters, the algebraic equation which ensures suppression of the fast time scale changes depending on things like whether the flow is isothermal or not. Another point worth mentioning is that all constraints are not the same. To give some indication of the computational difficulty expected while solving DAEs, the concept of an index is used. While there are several ways to approach this, two indices are often used. There is a differential and a perturbation index. ODEs are index-0 DAEs. The simple isothermal incompressible NSE are index-2 DAEs.

Independent of whether the equations being integrated are coupled systems of ODEs or DAEs ( or others ), the basic structure of the integrators is similar. The vast majority of existing integrators are what is called "linear methods." By this it is meant that the integation vector is updated using linear combinations of the integration vector and its time derivatives. There are essentially three different approaches to linear methods: Multistep methods, Multistage methods, and Multiderivative methods. More advanced methods may be constructed by combining the approaches. Multistep methods need no introduction. These include the popular Adams-Bashforth, Adams-Moulton, and BDF (Backward Differentiation Formulae ). Multistage methods are another name for Runge-Kutta methods, both explicit and implicit. lastly, there are Multiderivative methods, or, Taylor-Series methods. Combining these approaches;

General Linear Methods (GLMs): Multistep Multistage methods - These methods were formally introduced by John C. Butcher in 1966. [J.C. Butcher, On the convergence of numerical solutions to ordinary differential equations, Math. Comp., 20(93) (1966) 1-10.] Within the broad category of GLMs are many subcategories (with (one of) their originating papers:

---Cyclic Composite Multistep Methods (J. Donelson and E. Hansen (1971))

---Pseudo-Runge-Kutta Methods (G.D. Byrne and R.J. Lambert (1966))

---Hybrid Methods (C.W. Gear (1964))

---Multistep Runge-Kutta Methods (K. Burrage (1987))

---Two-Step Runge-Kutta Methods (Z. Jackiewicz and S. Tracogna (1995))

---Diagonally Implicit Multistage Integration Methods (DIMSIMs) (J.C. Butcher (1993))

---Inherent Runge-Kutta Stability Methods (IRKS) (J.C. Butcher (2001))

---Almost Runge-Kutta Methods (ARK) (J.C. Butcher (1987))

In the limit of a single stage, GLMs become Linear Multistep Methods (LMMs). Alternatively, in the limit of a single-step, GLMs become Runge-Kutta methods.

Obreshkov Methods: Multistep Multiderivative methods - These methods were introduced in 1940 and 1942 by Nikola Obreshkov. [N. Obreshkov, New quadrature formulas, Abh. Preu$\beta$. Akad. Wissen, Math. Natur., 4 (1940) 1-20. [In German, ISSN 0365-5342], N. Obreshkov, On the Mechanical Quadratures, Spisanie Bulg. Akad. Nauk., 65(8) (1942) 191-289. [In Bulgarian, ISSN 0007-3989]]

Turan Methods: Multistage Multiderivative methods - While the methods were not introduced by Pal Turan in 1950, he introduced the quadratures associated with Turan methods. Lubomir Chakalov made a similar contribution in 1948. [P. Tur\'{a}n, On the theory of mechanical quadrature, Acta. Sci. Math., Szeged \textbf{12} (1950) 30-37. See also \textit{Collected Papers of Paul Tur\'{a}n}, P. Erdos (Ed.), Vol. 1, Akad\'{e}miai Kiad\'{o}, Budapest (1990) pp 507-514, L. Chakalov (Tchakaloff), On a general quadrature formula, Comp. Rend. de l'Acad. Bulgare des Sci., 1(2-3) (1948) 9-12. [In German, ISSN 0861-1459]]. The first systematic treatment of Turan Methods was by K. Kastlunger and G. Wanner in 1972 -[Computing, 9(1) (1972) 9-24 and 9(4) (1972) 317-325.] Turan methods include:

---Fehlberg Methods (Fehlberg (1958,1960,1964,1966,1980))

---Mono-Implicit Turan methods (Gupta (1985))

---Elementary Differential Runge-Kutta Methods (EDRK) (Murua(1994))

Finally, all three approaches can be combined into a single method. For lack of a better name, they may be called Multistep Multistage Multiderivative methods. These were introduced by Hairer and Wanner in their 1973 and 1974 papers.

Multistep Multistage Multiderivative methods: [ E. Hairer and G. Wanner, Multistep-multistage-multiderivative methods of ordinary differential equations, Computing, 11(3) (1973) 287-303, E. Hairer and G. Wanner, On the Butcher group and general multivalue methods, Computing, 13(1) (1974) 1-15.]

The following sections discuss several temporal discretization schemes:

• Euler methods
• Runge Kutta methods