MUSCL scheme

From Wikipedia, the free encyclopedia

MUSCL stands for Monotone Upstream-centered Schemes for Conservation Laws, and the term was introduced in a seminal paper by Bram van Leer (van Leer, 1979). In this paper he constructed the first high-order, total variation diminishing (TVD) scheme where he obtained second order spatial accuracy. It is a finite volume method that provides high accuracy numerical solutions to partial differential equations which can involve solutions that exhibit shocks, discontinuities or large gradients.

The idea is to replace the piecewise constant approximation of Godunov's scheme by reconstructed states, derived from cell-averaged states obtained from the previous time-step. For each cell, slope limited, reconstructed left and right states are obtained and used to calculate fluxes at the cell boundaries (edges). These fluxes are, in turn, used as input to the (approximate) Riemann solver. The Riemann solver solutions are averaged and used to advance the solution in time.

1 Linear reconstruction
2 Kurganov and Tadmor central scheme
3 Piecewise parabolic reconstruction
4 Euler equations example
5 References
6 Further reading
7 See also

[edit] Linear reconstruction

1D advective equation ut+ux=0, with step wave propogating to the right. Shows the analytical solution along with a simulation based upon a first order upwind scheme.

We will consider the fundamentals of the MUSCL scheme by considering the following simple first-order, scalar, 1D system, which is assumed to have a wave propogating in the positive direction,

$u_t + F_x\left(u \right)=0 .$

Where $u \$ represents a state variable and $F \$ represents a flux variable.

The basic scheme of Godunov uses piecewise constant approximations for each cell, and results in a first-order upwind discretisation of the above problem with cell centres indexed as $i$ . A semi-discrete scheme can be defined as follows,

$\frac{d u_i}{d t} + \frac{1}{\Delta x_i} \left[ F \left( u_{i + 1} \right) - F \left( u_{i} \right) \right] =0$ .

This basic scheme is not able to handle shocks or sharp discontinuities as they tend to become smeared. An example of this effect is shown in the diagram opposite, which illustrates a 1D advective equation with a step wave propogating to the right. The simulation was carried out with a mesh of 200 cells.

To provide higher resolution of discontinuities, Godunov's scheme can be extended to use piecewise linear approximations of each cell, which results in a central difference scheme that is second-order accurate in space. The piecewise linear approximations are obtained from

$u \left( x \right) = u_{i} + \frac{\left( x - x_{i} \right) }{ \left( x_{i+1} - x_{i} \right)} \left( u_{i+1} - u_{i} \right) , x \in \left[ x_{i}, x_{i+1} \right]$ .

Thus, evaluating fluxes at the cell edges we get the following semi-discrete scheme

$\frac{d u_i}{d t} + \frac{1}{\Delta x_i} \left[ F \left( u_{i + \frac{1}{2}} \right) - F \left( u_{i - \frac{1}{2}} \right) \right] =0$ ,

1D advective equation ut+ux=0, with step wave propogating to the right. Shows the analytical solution along with a simulation based upon a second order, central difference scheme.

where $u_{i + \frac{1}{2}}$ and $u_{i - \frac{1}{2}}$ are the piecewise approximate values of cell edge variables, i.e.

$u_{i + \frac{1}{2}} = 0.5 \left( u_{i} + u_{i + 1} \right)$ ,

$u_{i - \frac{1}{2}} = 0.5 \left( u_{i-1} + u_{i} \right)$ .

Whilst the above second-order scheme provides greater accuracy for smooth solutions, it is not a total variation diminishing (TVD) scheme and introduces spurious oscillations into the solution where discontinuities or shocks are present. An example of this effect is shown in the diagram opposite, which illustrates a 1D advective equation ut+ux=0, with a step wave propogating to the right. The simulation was carried out with a mesh of 200 cells. This loss of accuracy is to be expected due to Godunov's theorem.

An example of MUSCL type left and right state linear-extrapolation.

MUSCL based numerical schemes extend the idea of using a linear piecewise approximation to each cell by using slope limited left and right extrapolated states. This results in the following high resolution, TVD discretisation scheme,

$\frac{d u_i}{d t} + \frac{1}{\Delta x_i} \left[ F \left( u^*_{i + \frac{1}{2}} \right) - F \left( u^*_{i - \frac{1}{2}} \right) \right] =0$ .

Which, alternatively, can be written in the more succinct form,

$\frac{d u_i}{d t} + \frac{1}{\Delta x_i} \left[ F^*_{i + \frac{1}{2}} - F^*_{i - \frac{1}{2}} \right] =0$ .

The numerical fluxes $F^*_{i \pm \frac{1}{2}}$ correspond to a nonlinear combination of first and second-order approximations to the continuous flux function.

The symbols $u^*_{i + \frac{1}{2}}$ and $u^*_{i - \frac{1}{2}}$ represent scheme dependent functions (of the limited extrapolated cell edge variables), i.e.

$u^*_{i + \frac{1}{2}} = u^*_{i + \frac{1}{2}} \left( u^L_{i + \frac{1}{2}} , u^R_{i + \frac{1}{2}} \right), u^*_{i - \frac{1}{2}} = u^*_{i - \frac{1}{2}} \left( u^L_{i - \frac{1}{2}} , u^R_{i - \frac{1}{2}} \right)$ ,

and

$u^L_{i + \frac{1}{2}} = u_{i} + 0.5 \phi \left( r_{i} \right) \left( u_{i+1} - u_{i} \right), u^R_{i + \frac{1}{2}} = u_{i+1} - 0.5 \phi \left( r_{i+1} \right) \left( u_{i+2} - u_{i+1} \right)$ ,

$u^L_{i - \frac{1}{2}} = u_{i-1} + 0.5 \phi \left( r_{i-1} \right) \left( u_{i} - u_{i-1} \right), u^R_{i - \frac{1}{2}} = u_{i} - 0.5 \phi \left( r_{i} \right) \left( u_{i+1} - u_{i} \right)$ ,

$r_{i} = \frac{u_{i} - u_{i-1}}{u_{i+1} - u_{i}}$ .

The function ${\phi \left( r_i \right)}\$ is a limiter function that limits the slope of the piecewise approximations to ensure the solution is TVD, thereby avoiding the spurious oscillations that would otherwise occur around discontinuities or shocks - see Flux limiter section. The limiter is equal to zero when $r \le 0 \$ and is equal to unity when $r = 1 \$ . Thus, the accuracy of a TVD discretization degrades to first order at local extrema, but tends to second order over smooth parts of the domain.

The algorithm is straight forward to implement. Once a suitable scheme for $F^*_{i + \frac{1}{2}} \$ has been chosen, such as the Kurganov and Tadmor scheme (see below), the solution can proceed using standard integration techniques such as Numerical method of lines (NUMOL).

[edit] Kurganov and Tadmor central scheme

The Kurganov and Tadmor central scheme is a second-order, high-resolution scheme that uses MUSCL reconstruction. It is straight forward to implement and can be used on scalar and vector problems. The algorithm is based upon central differences with comparable performance to Riemann type solvers when used to obtain solutions for PDE’s describing systems that exhibit high-gradient phenomena. Here we consider the semi-discrete scheme.

The calculation is shown below:

$F^*_{i-\frac{1}{2}} =\frac{1}{2 \Delta x} \left\{ \left[ F \left(u^R_{i - \frac{1}{2}} \right) + F \left(u^L_{i - \frac{1}{2}} \right) \right] - a_{i - \frac{1}{2} } \left[u^R_{i - \frac{1}{2}} - u^L_{i - \frac{1}{2}} \right] \right\}$ .

$F^*_{i+\frac{1}{2}} =\frac{1}{2 \Delta x} \left\{ \left[ F \left(u^R_{i + \frac{1}{2}} \right) + F \left(u^L_{i + \frac{1}{2}} \right) \right] - a_{i + \frac{1}{2} } \left[u^R_{i + \frac{1}{2}} - u^L_{i + \frac{1}{2}} \right] \right\}$ .

1D advective equation ut+ux=0, with step wave propogating to the right. Shows the analytical solution along with a simulation based upon the Kurganov and Tadmor central scheme with SuperBee limiter.

Where the local propagation speed, $a_{i \pm \frac{1}{2}} \$ , is the maximum Jacobian of $F \left( u \left(x, t \right) \right)$ over cells ${i} , {i \pm 1}$ , given by,

$a_{i \pm \frac{1}{2} } \left( t \right) = \max \left[ \rho \left( \frac{\partial F \left( u_{i} \left( t \right) \right)}{\partial u} \right) , \rho \left( \frac{\partial F \left( u_{i \pm 1} \left( t \right) \right)}{\partial u} \right) \right]$ .

An example of the effectiveness of using a high resolution scheme is shown in the diagram opposite, which illustrates the 1D advective equation ut+ux=0, with a step wave propogating to the right. The simulation was carried out on a mesh of 200 cells, using the Kurganov and Tadmor central scheme with Superbee limiter. This simulation result contrasts extremely well against the above first-order upwind and second-order central difference results shown above. This scheme also provides good results when applied to sets of equations - see results below for this scheme applied to the Euler equations. However, care has to be taken in choosing an appropriate limiter because, for example, the Superbee limiter can cause unrealistic sharpening for some smooth waves.

The scheme can readily include diffusion terms, if they are present. For example, if the above 1D scalar problem is extended to include a diffusion term, we get

$u_t + F_x\left(u \right) = Q_x \left( u , u_x \right)$ ,

for which Kurganov and Tadmor propose the following central difference approximation,

$\frac{d u_i}{d t} = - \frac{1}{\Delta x_i} \left[ F^*_{i + \frac{1}{2}} - F^*_{i - \frac{1}{2}} \right] + \frac{1}{\Delta x_i} \left[ P_{i + \frac{1}{2}} - P_{i - \frac{1}{2}} \right]$ .

Where,

$P_{i + \frac{1}{2}} = \frac{1}{2} \left[ Q \left( u_{i} , \frac{u_{i+1} - u_i}{\Delta x_i} \right) + Q \left( u_{i+1} , \frac{u_{i+1} - u_i}{\Delta x_i} \right) \right]$ ,

$P_{i - \frac{1}{2}} = \frac{1}{2} \left[ Q \left( u_{i-1} , \frac{u_{i} - u_{i-1}}{\Delta x_{i-1}} \right) + Q \left( u_{i} , \frac{u_{i} - u_{i-1}}{\Delta x_{i-1}} \right) \right]$ .

Full details of the algorithm and its derivation can be found in the original paper (Kurganov and Tadmor, 1999), along with a number of 1D and 2D examples. Additional information is also available in an earlier related paper (Nessyahu and Tadmor, 1990).

Note: Whilst this scheme was originally presented by Kurganov and Tadmor as a 2nd order scheme, a later paper (Kurganov and Levy, 2000) demonstrates that it can also form the basis of a third order scheme. A 1D advective example and a Euler equation example of their scheme, using parabolic reconstruction (3rd order), are shown in the parabolic reconstruction and Euler equation sections below.

[edit] Piecewise parabolic reconstruction

An example of MUSCL type state parabolic-reconstruction.

It is possible to extend the idea of linear-extrapolation to higher order reconstruction, and an example is shown in the diagram opposite. However, for this case the left and right states are estimated by interpolation of a second-order, upwind biased, difference equation. This results in a parabolic reconstruction scheme that is third-order accurate in space.

We follow the approach of Kermani (Kermani, et al, 2003), and present a third-order upwind biased scheme, where the symbols $u^*_{i + \frac{1}{2}}$ and $u^*_{i - \frac{1}{2}}$ again represent scheme dependent functions (of the limited reconstructed cell edge variables). But for this case they are based upon parabolically-reconstructed states, i.e.

$u^*_{i + \frac{1}{2}} = f \left( u^L_{i + \frac{1}{2}} , u^R_{i + \frac{1}{2}} \right), u^*_{i - \frac{1}{2}} = f \left( u^L_{i - \frac{1}{2}} , u^R_{i - \frac{1}{2}} \right)$ ,

and

$u^L_{i + \frac{1}{2}} = u_{i} + \frac{\phi \left( r_{i} \right)}{4} \left[ \left( 1 - \kappa \right) \delta u_{i - \frac{1}{2} } + \left( 1 + \kappa \right) \delta u_{i + \frac{1}{2} } \right]$ ,

$u^R_{i + \frac{1}{2}} = u_{i+1} - \frac{\phi \left( r_{i+1} \right)}{4} \left[ \left( 1 - \kappa \right) \delta u_{i + \frac{3}{2} } + \left( 1 + \kappa \right) \delta u_{i + \frac{1}{2} } \right]$ ,

$u^L_{i - \frac{1}{2}} = u_{i-1} + \frac{\phi \left( r_{i-1} \right)}{4} \left[ \left( 1 - \kappa \right) \delta u_{i - \frac{3}{2}} + \left( 1 + \kappa \right) \delta u_{i - \frac{1}{2} } \right]$ ,

$u^R_{i - \frac{1}{2}} = u_{i} - \frac{\phi \left( r_{i} \right)}{4} \left[ \left( 1 - \kappa \right) \delta u_{i + \frac{1}{2} } + \left( 1 + \kappa \right) \delta u_{i - \frac{1}{2} } \right]$ .

1D advective equation ut+ux=0, with step wave propogating to the right. Shows the analytical solution along with a simulation based upon the Kurganov and Tadmor Central Scheme with parabolic reconstruction and van Albada limiter.

Where $\kappa \$ = 1/3 and,

$\delta u_{i + \frac{1}{2} } = \left( u_{i+1} - u_{i} \right) , \delta u_{i - \frac{1}{2} } = \left( u_{i} - u_{i-1} \right)$ ,

$\delta u_{i + \frac{3}{2} } = \left( u_{i+2} - u_{i+1} \right) , \delta u_{i - \frac{3}{2} } = \left( u_{i-1} - u_{i-2} \right)$ ,

and the limiter function $\phi \left( r \right)\$ , is the same as above.

Parabolic reconstruction is straight forward to implement and can be used with the Kurganov and Tadmor scheme in lieu of the linear extrapolation shown above. This has the effect of raising the spatial solution of the KT scheme to 3rd order. It performs well when solving the Euler equations, see below. However, whilst this increase in spatial order has certain advantages over 2nd order schemes for smooth solutions, for shocks it is more disipative - compare diagram opposite with above solution obtained using the KT algorithm with linear extrapolation and Superbee limiter. This simulation was carried out on a mesh of 200 cells using the same KT algorithm but with parabolic reconstruction and the alternative form of van Albada limiter, $\phi_{va} (r) = \frac{2 r}{1 + r^2 } \$ , to avoid spurious oscillations.

[edit] Euler equations example

For simplicity we consider the 1D case without heat transfer and without body force. Therefore, in conservation vector form, the general Euler equations reduce to

$\frac{\partial \mathbf{U}}{\partial t}+ \frac{\partial \mathbf{F}}{\partial x}=0$ ,

where

$\mathbf{U}=\begin{pmatrix}\rho \\ \rho u \\ E\end{pmatrix}\qquad \mathbf{F}=\begin{pmatrix}\rho u\\p+\rho u^2\\ u(E+p)\end{pmatrix}\qquad$ ,

and where $U$ is a vector of states and $F$ is a vector of fluxes.

The equations above represent conservation of mass, momentum, and energy. There are thus three equations and four unknowns, $ρ$ (density) $u$ (fluid velocity), $p$ (pressure) and $E$ (total energy). The total energy is given by,

$E=\rho e + \frac{1}{2} \rho u^2$ ,

where $e\$ represents specific internal energy.

In order to close the system an equation of state is required. One that suits our purpose is

$p=\rho \left(\gamma-1 \right)e$ ,

where $\gamma\$ is equal to the ratio of specific heats $\left[ c_p/c_v \right]$ for the fluid.

We can now proceed, as shown above in the simple 1D example, by obtaining the left and right extrapolated states for each state variable. Thus, for density we obtain

$\rho^*_{i + \frac{1}{2}} = \rho^*_{i + \frac{1}{2}} \left( \rho^L_{i + \frac{1}{2}} , \rho^R_{i + \frac{1}{2}} \right), \rho^*_{i - \frac{1}{2}} = \rho^*_{i - \frac{1}{2}} \left( \rho^L_{i - \frac{1}{2}} , \rho^R_{i - \frac{1}{2}} \right)$ ,

where

$\rho^L_{i + \frac{1}{2}} = \rho_{i} + 0.5 \phi \left( r_{i} \right) \left( \rho_{i+1} - \rho_{i} \right), \rho^R_{i + \frac{1}{2}} = \rho_{i+1} - 0.5 \phi \left( r_{i+1} \right) \left( \rho_{i+2} - \rho_{i+1} \right)$ ,

$\rho^L_{i - \frac{1}{2}} = \rho_{i-1} + 0.5 \phi \left( r_{i-1} \right) \left( \rho_{i} - \rho_{i-1} \right), \rho^R_{i - \frac{1}{2}} = \rho_{i} - 0.5 \phi \left( r_{i} \right) \left( \rho_{i+1} - \rho_{i} \right)$ .

Similarly, for momentum $ρ u$ , and total energy $E$ . Velocity $u$ , is calculated from momentum, and pressure $p$ , is calculated from the equation of state.

Having obtained the limited extrapolated states, we then proceed to contruct the edge fluxes using these values. With the edge fluxes known, we can now construct the semi-discrete scheme, i.e.

$\frac{d \mathbf{U}_i}{d t} = - \frac{1}{\Delta x_i} \left[ \mathbf{F}^*_{i + \frac{1}{2} } - \mathbf{F}^*_{i - \frac{1}{2}} \right]$ .

The solution can now proceed by integration using standard numerical techniques.

The above illustrates the basic idea of the MUSCL scheme. However, for a practical solution to the Euler equations, a suitable scheme has to be chosen which will also define the function $\mathbf{F}^*_{i \pm \frac{1}{2} }$ .

High resolution simulation of Euler equations based on G A Sod's 'Shock Tube' problem. Shows the analytical solutions along with simulated (2nd order) solutions based upon the Kuganov and Tadmor Central Scheme with Linear Extrapolation and Ospre limiter.

The diagram opposite shows a 2nd order solution to G A Sod's shock tube problem (Sod, 1978) using the above high resolution Kurganov and Tadmor Central Scheme (KT) with Linear Extrapolation and Ospre limiter. This illustrates clearly the effectiveness of the MUSCL approach to solving the Euler equations. The simulation was carried out on a mesh of 200 cells using Matlab code (Wesseling, 2001), adapted to use the KT algorithm and Ospre limiter. The following initial conditions (SI units) were used:

pressure left = 100000 [Pa];
pressure right= 10000 [Pa];
density left = 1.0 [kg/m3];
density right = 0.125 [kg/m3];
length = 20 [m];
velocity left = 0 [m/s];
velocity right = 0 [m/s];
duration =0.01 [s];
lambda = 0.001069;

High resolution simulation of Euler equations based on G A Sod's 'Shock Tube' problem - SI units. Shows the analytical solutions along with simulated (3rd order) solutions based upon the Kuganov and Tadmor Central Scheme with parabolic reconstruction and van Albada lmiter.

The diagram opposite shows a 3rd order solution to G A Sod's shock tube problem (Sod, 1978) using the above high resolution Kurganov and Tadmor Central Scheme (KT) but with parabolic reconstruction and van Albada limiter. This again illustrates the effectiveness of the MUSCL approach to solving the Euler equations. The simulation was carried out on a mesh of 200 cells using Matlab code (Wesseling, 2001), adapted to use the KT algorithm with Parabolic Extrapolation and van Albada limiter. The alternative form of van Albada limiter, $\phi_{va} (r) = \frac{2 r}{1 + r^2 } \$ , was used to avoid spurious oscillations. The same initial conditions were used:

Various other high resolution schemes have been developed that solve the Euler equations with good accuracy. Examples of such schemes are,

the Osher scheme, and
the Liou-Steffen AUSM (advection upstream splitting method) scheme.

More information on these and other methods can be found in the references below.

[edit] References

Kermani, M. J., Gerber, A. G., and Stockie, J. M. (2003), Thermodynamically Based Moisture Prediction Using Roe’s Scheme, The 4th Conference of Iranian AeroSpace Society, Amir Kabir University of Technology, Tehran, Iran, January 27–29. [1]
Kurganov, Alexander and Eitan Tadmor (2000), New High-Resolution Central Schemes for Nonlinear Conservation Laws and Convection-Diffusion Equations, J. Comp. Phys., 160, 214–282. [2]
Kurganov, Alexander and Doron Levy (2000), A Third-Order Semidiscrete Central Scheme for Conservation Laws and Convection-Diffusion Equations, SIAM J. Sci. Comput., 22, 1461–1488. [3]
van Leer, B. (1979), Towards the Ultimate Conservative Difference Scheme, V. A Second Order Sequel to Godunov's Method, J. Com. Phys.., 32, 101–136.
Nessyahu, H. and E. Tadmor (1990), Non-oscillatory central differencing for hyperbolic conservation laws, J. Comp. Phys.., 87, 408–463. [4]
Sod, G. A. (1978), A Numerical Study of a Converging Cylindrical Shock. J. Fluid Mechanics, 83, 785–794.
Wesseling, Pieter (2001), Principles of Computational Fluid Dynamics, Springer-Verlag.

[edit] Further reading

Hirsch, C. (1990), Numerical Computation of Internal and External Flows, vol 2, Wiley.

Laney, Culbert B. (1998), Computational Gas Dynamics, Cambridge University Press.

Toro, E. F. (1999), Riemann Solvers and Numerical Methods for Fluid Dynamics, Springer-Verlag.

Tannehill, John C., et al, (1997), Computational Fluid mechanics and Heat Transfer, 2nd Ed., Taylor and Francis.

Categories: Fluid dynamics | Numerical differential equations

MUSCL scheme

From Wikipedia, the free encyclopedia

Contents

[edit] Linear reconstruction

[edit] Kurganov and Tadmor central scheme

[edit] Piecewise parabolic reconstruction

[edit] Euler equations example

[edit] References

[edit] Further reading

[edit] See also

Views

Navigation

Search