MPDATA

Comparison of UPWIND (top panel), basic MPDATA (middle panel) and 3-iteration non-oscillatory MPDATA (bottom panel) applied to transport of a cone-shaped signal in a two-dimensional stationary rotational flow ("Molenkamp test")

In numerical analysis of partial differential equations, MPDATA is a family of iterative finite-difference/finite-volume methods for numerical integration of hyperbolic differential equations modelling conservation laws of the form:

where ψ(𝐱,t) is an advected scalar field (or advectee); 𝐯=G𝐱˙ is the flow velocity vector field (or advector), G(𝐱) may either play the role of the fluid density, the Jacobian of coordinate transformation from Cartesian to curvilinear framework 𝐱, or their product; R(𝐱) combines all source terms.

MPDATA stands for Multidimensional Positive Definite Advection Transport Algorithm. The algorithm was formulated by Piotr K. Smolarkiewicz (and is also referred to as Smolarkiewicz's method) at the US National Center for Atmospheric Research - NCAR (at the time, Smolarkiewicz was a fellow of the NCAR Advanced Study Program and a recent graduate from Krzysztof Haman's group at the University of Warsaw; the seminal 1983 and 1984 MPDATA publications mention both institutions).

The crux of the method lies in iterative application of the upwind scheme. The first iteration employs the advective velocity 𝐯, while each subsequent iteration employs a so-called antidiffusive velocity which corrects solution from prior iteration reducing the numerical diffusion. The antidiffusive velocities can be derived through modified equation analysis of the upwind scheme and feature cross-dimensional dependencies (i.e., applying MPDATA in multiple dimensions is not equivalent to application of one-dimensional MPDATA in all dimensions), the scheme is thus not dimensionally split, hence "M" in the algorithm name. Since each iteration of the scheme constitutes a forward-in-time upwind pass, the scheme inherits characteristics of the upwind scheme: CFL stability criterion, conservativeness, embarrassingly parallel domain decomposition, and sign-preservation. For non-negative fields ψ, sign-preservation translates to positive definiteness, hence the "PD" in the algorithm name. Application of the corrective iterations improves scheme convergence rate compared with first-order upwind. Depending on the MPDATA variant, convergence of up to third-order in time and space can be achieved.

While the original formulation of MPDATA employed structured grids, the algorithm has been subsequently also formulated for unstructured grids. Despite being formulated for and named in reference to advection problems, as any other advection numerical scheme, MPDATA also applies to solutions of advection-diffusion as well as diffusion-only problems if Fickian diffusive terms are expressed as advective fluxes (approach referred to as the pseudo-velocity technique).

Description of the basic scheme in 1D

MPDATA is inherently multi-dimensional, and primarily used in computational fluid dynamics where the advective volocities and problem geometries are variable in time. Still, the key idea underlying the MPDATA approach can be conveyed with a basic example of solenoidal stationary flow in one dimension (i.e., 𝐯=[u] constant in time and space), without coordinate transformation (G=1), for the case of homogeneous advection (R=0) of a nonnegative scalar field (ψ≥0), with the following flux form of the advection equation:

Upwind discretisation of the problem on a regular staggered grid with a time step Δt and a grid step Δx, with n=t/Δt, i=x/Δx, and the half-integer spatial indices corresponding to grid-cell walls:

ui−3/2ui−1/2ui+1/2ui+3/2
...|·|·|·|...
ψi−1ψiψi+1

can be formulated with:

with the flux function defined using positive and negative parts of ui±1/2 as:

Introducing the non-dimensional Courant number C=uΔt/Δx, the resultant explicit-in-time scheme (referred to as "upwind", "upstream" or "donor-cell"), for a constant C reads:

which is conservative, sing-preserving and stable for |C|≤1. However, the scheme is only first-order accurate in space (Δx) and time (Δt), and incurs numerical diffusion which can be quantified with the modified-equation analysis by substituting the discretised values other than ψin in (5) with their Taylor expansions (using the Big O notation):

which yields (up to second-order terms):

in which the highlighted second-order time derivative can be replaced with second-order spatial derivative using the Cauchy-Kovalevskaya procedure (i.e., by substituting eq. (2) into a time-derivative of eq. (2) giving ∂t2ψ=−u∂x∂tψ=u2∂x2ψ) yielding the following, so-called, modified equation:

which confirms that, as Δt→0 and Δx→0, the upwind scheme approximates eq. (2), but the truncation error has a leading-order Fickian source term with a coefficient of numerical diffusion given by k.

The concept of MPDATA lies in reversing the effect of numerical diffusion by using the pseudo-velocity technique that allows to express diffusion terms in transport problems using an equation of the same form as (2). To this end, Smolarkiewicz introduced the anti-diffusive pseudo velocity (note the opposite sign stemming from, de facto, integrating backwards in time to reverse the effect of diffusion):

and proposed discretisation allowing to perform a corrective step using upwind integration with an anti-diffusive Courant number field:

where m>0 numbers algorithm iterations. The first pass of the scheme is an ordinary upwind integration using Cm=1=C and yielding ψm=1. In the second pass, the values of the anti-diffusive Courant number Cm=2 are computed based on Cm=1 and ψm=1, and used to perform an upwind anti-diffusive pass yielding ψm=2. Note that even for constant-in-x physical Cm=1, the anti-diffusive Cm=1 varies in x (and thus corresponds to a divergent flow). Subsequent iterations are correcting the integration of the anti-diffusive corrections from previous passes. If M iterations are used, ψm=M is used as the result of integration of the advective term over one Δt.

Note that despite a constant flow field, the anti-diffusive velocity varies in space and time and is not solenoidal.

The values of ψi−1n at the left edge of the domain, and ψi+1n at the right edge of the domain are obtained by specifying boundary conditions.

Algorithm variants and techniques used in concert with MPDATA

The basic formulation of the scheme has been extended yielding a multitude of MPDATA variants, including (in chronological order of literature references):

Note that some of the non-basic variants of the algorithm have larger stencils) extent than the original formulation.

Some of the pertinent numerical techniques used together with MPDATA include:

Applications

Equation (1), which is numerically approximated with MPDATA, is used in modelling a wide range of transport phenomena across different scales and . MPDATA has documented applications in the following domains:

Open-source implementations

See also