DatumEdge

The website of James Shaw, a PhD student researching numerical methods for the atmosphere at University of Reading

Creating a high-order finite volume transport scheme

20 January 2017

Over the last year of my PhD I have been working to create a finite volume transport scheme, called ‘cubicFit’, that is second-order convergent on arbitrary meshes. Recently, I have tried modifying the cubicFit transport scheme to obtain high-order convergence: that is, convergence greater than second-order. Here I'll introduce a one-dimensional version of the cubicFit scheme and explain how it can be modified to obtain high-order convergence.

One-dimensional finite volume approximation

To formulate the one-dimensional cubicFit transport scheme, I'll start from the transport equation for a dependent variable \(\phi\) assuming a non-negative velocity \(u\) that is constant in time and space, \begin{equation} \frac{\partial \phi}{\partial t} = - u \frac{\partial \phi}{\partial x} \label{eqn:transport} \end{equation} where the term on the right-hand side is called the flux divergence. With a C-grid staggering, velocity values are stored at faces and \(\phi\) values are stored at cell centres. Using the finite volume method to discretise the flux divergence term, equation \eqref{eqn:transport} becomes \begin{equation} \frac{\partial \phi}{\partial t} = - u \frac{\phi_R - \phi_L}{\Delta x} \label{eqn:fluxdiv} \end{equation} where \(\phi_L\) and \(\phi_R\) are approximate values of \(\phi\) at the left and right faces respectively, and \(\Delta x\) is the distance between the faces.

The one-dimensional cubicFit transport scheme approximates face values \(\phi_L\) and \(\phi_R\) using four-point, upwind-biased stencils of cell centre values. Cell centres are marked by grey filled circles and faces are marked by black open circles.

The cubicFit scheme approximates a face value using four neighbouring cell centre values, as shown above. For each face, a cubic polynomial is found that interpolates the four data points, \begin{equation} \phi = a_1 + a_2 x + a_3 x^2 + a_4 x^3 \text{.} \label{eqn:cubic} \end{equation} By choosing a local coordinate with its origin at the face then the value of \(\phi\) at the face is just \(a_1\), which is calculated as follows. Assuming a uniform mesh with \(\Delta x = 1\) and choosing the position of \(\phi_{i+1/2}\) to be \(x=0\), equation \eqref{eqn:cubic} is evaluated at the cell centres \(\phi_{i-2}, \ldots, \phi_{i+1}\) to form the matrix equation \begin{align} \mathbf{B} \mathbf{a} &= \mathbf{\phi} \\ \begin{bmatrix} 1 & -5/2 & 25/4 & -125/8 \\ 1 & -3/2 & 9/4 & -27/8 \\ 1 & -1/2 & 1/4 & -1/8 \\ 1 & 1/2 & 1/4 & 1/8 \\ \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix} &= \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \text{.} \end{align} The unknown coefficients \(\mathbf{a}\) are found by inverting \(\mathbf{B}\) such that \(\mathbf{a} = \mathbf{B}^{-1} \mathbf{\phi}\). The inverse matrix is \begin{align} \mathbf{B}^{-1} = \frac{1}{48} \begin{bmatrix} 3 & -15 & 45 & 15 \\ 2 & -6 & -42 & 46 \\ -12 & 60 & -84 & 36 \\ -8 & 24 & -24 & 8 \end{bmatrix} \label{eqn:cubicfit-inverse} \end{align} Since \(x=0\) was chosen to be the position \(i+1/2\) then \begin{align} \phi_{i+1/2} = a_1 = \frac{1}{16} \begin{bmatrix} 1 \\ -5 \\ 15 \\ 5 \end{bmatrix} \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi{i+1} \end{bmatrix} \text{.} \label{eqn:cubicfit-fluxcoeffs} \end{align}

One-dimensional finite difference approximation

To obtain a high-order version of the one-dimensional cubicFit transport scheme I return to the flux divergence term on the right-hand side of equation \eqref{eqn:transport} and discretise it using the finite difference method. Using this method, the flux divergence of cell \(i\) is calculated using a cubic approximation using cell centre values \(\phi_{i-2}, \ldots, \phi_{i+1}\). A matrix equation is constructed using equation \eqref{eqn:cubic} evaluated at every cell centre. For convenience, assume that \(\Delta x = 1\) and that \(x=0\) at the cell centre position of \(\phi_i\), hence the matrix equation becomes \begin{align} \mathbf{B} \mathbf{a} &= \mathbf{\phi} \\ \begin{bmatrix} 1 & -2 & 4 & -8 \\ 1 & -1 & 1 & -1 \\ 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 1\\ \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ a_4 \end{bmatrix} &= \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \end{align} The unknown coefficients \(\mathbf{a}\) are found by calculating the inverse matrix, \begin{align} \mathbf{B}^{-1} = \frac{1}{6} \begin{bmatrix} 0 & 0 & 6 & 0 \\ 1 & -6 & 3 & 2 \\ 0 & 3 & -6 & 3 \\ -1 & 3 & -3 & 1 \end{bmatrix} \text{.} \end{align} To calculate the flux divergence I calculate the derivative \(\partial \phi / \partial x = a_2 + 2 a_3 x + 3 a_4 x^2\). Evaluating the flux divergence at \(\phi_i\) where \(x=0\) then \(\partial \phi_i / \partial x = a_2\). Hence I find that the finite difference weighted sum is \begin{align} -u \frac{\partial \phi_i}{\partial x} = -u a_2 = -u \cdot \frac{1}{6} \begin{bmatrix} 1 \\ -6 \\ 3 \\ 2 \end{bmatrix} \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \label{eqn:fd-fluxdiv} \end{align} The cubic finite difference approximation given in equation \eqref{eqn:fd-fluxdiv} is conservative on uniform meshes. This can be demonstrated by decomposing the weights vector, \begin{align} -u \cdot \frac{1}{6} \begin{bmatrix} 1 \\ -6 \\ 3 \\ 2 \end{bmatrix} \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} &= -u \cdot \frac{1}{6} \left( \begin{bmatrix} 0 \\ -1 \\ 5 \\ 2 \end{bmatrix} - \begin{bmatrix} -1 \\ 5 \\ 2 \\ 0 \end{bmatrix} \right) \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \\ &= -u \left( \frac{1}{6} \begin{bmatrix} -1 \\ 5 \\ 2 \end{bmatrix} \cdot \begin{bmatrix} \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} - \frac{1}{6} \begin{bmatrix} -1 \\ 5 \\ 2 \end{bmatrix} \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \end{bmatrix} \right) \text{.} \label{eqn:fd-fluxcoeffs} \end{align} Notice that the flux divergence has been rewritten as the difference between right and left fluxes as in equation \eqref{eqn:fluxdiv}.

High-order correction in one dimension

The high-order correction to the cubicFit scheme is calculated as the difference between the cubic finite difference approximation (equation \ref{eqn:fd-fluxcoeffs}) and the uncorrected cubicFit approximation (equation \ref{eqn:cubicfit-fluxcoeffs}), \begin{align} \mathrm{correction}(\phi_{i+1/2}) &= \left( \frac{1}{6} \begin{bmatrix} 0 \\ -1 \\ 5 \\ 2 \end{bmatrix} - \frac{1}{16} \begin{bmatrix} 1 \\ -5 \\ 15 \\ 5 \end{bmatrix} \right) \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \\ &= \frac{1}{48} \begin{bmatrix} -3 \\ 7 \\ -5 \\ 1 \end{bmatrix} \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \label{eqn:correction} \end{align} which can be decomposed into a linear combination of second derivatives where \(\partial_x^2 \phi_i = \phi_{i-1} - 2 \phi_i + \phi_{i+1}\), \begin{align} &= \frac{1}{48} \left( -3 \begin{bmatrix}1 \\ -2 \\ 1 \\ 0\end{bmatrix} + \begin{bmatrix}0 \\ 1 \\ -2 \\ 1\end{bmatrix} \right) \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \\ &= \frac{1}{48} \left( -3 \partial_x^2 \phi_{i-1} + \partial_x^2 \phi_i \right) \text{.} \end{align} Applying this correction using the three-point approximation of the second derivative results in third-order convergence on uniform meshes and second-order convergence on non-uniform meshes.

Convergence of uncorrected and corrected versions of the one-dimensional cubicFit transport scheme. A single sine wave is transported once around a periodic domain. The \(\ell_2\) error is calculated as \(\ell_2 = \sqrt{\sum_i{\left(\phi_i - \phi_i^T\right)^2 \Delta x_i} / \sum_i{\left(\phi_i^T\right)^2 \Delta x_i}}\) where \(\phi\) is the numeric solution and \(\phi_T\) is the analytic solution. The python source code is available on github.

Alternatively, the second derivative can be calculated from equation \eqref{eqn:cubic} such that \(\partial_x^2 \phi = 2a_3 + 6a_4x\) where \(a_3\) and \(a_4\) can be calculated using equation \eqref{eqn:cubicfit-inverse}. This approach results in fourth-order convergence on uniform meshes and second-order convergence on non-uniform meshes, as seen in the convergence plot above. Curiously, this approach yields the correction \begin{align} \mathrm{correction}(\phi_{i+1/2}) &= \frac{1}{48} \left( -3 \cdot \begin{bmatrix} 0 \\ 1 \\ -2 \\ 1 \end{bmatrix} + \begin{bmatrix} -1 \\ 4 \\ -5 \\ 2 \end{bmatrix} \right) \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \\ &= \frac{1}{48} \cdot \begin{bmatrix} -1 \\ 1 \\ 1 \\ -1 \end{bmatrix} \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} = \frac{1}{48} \left( \begin{bmatrix} -1 \\ 2 \\ -1 \\ 0 \end{bmatrix} + \begin{bmatrix} 0 \\ -1 \\ 2 \\ -1 \end{bmatrix} \right) \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \\ &= -\frac{1}{48} \left( \partial_x^2 \phi_{i-1} + \partial_x^2 \phi_i \right) \cdot \begin{bmatrix} \phi_{i-2} \\ \phi_{i-1} \\ \phi_i \\ \phi_{i+1} \end{bmatrix} \text{.} \end{align}

Can high-order be obtained in two dimensions?

The one-dimensional version of cubicFit exactly interpolates four data points with a cubic polynomial. However, on a two-dimensional mesh of rectangular cells, the stencil has four points in the \(x\) direction and three points in the \(y\) direction for a total of twelve data points. The multidimensional polynomial is then $$ \phi = a_1 + a_2 x + a_3 y + a_4 x^2 + a_5 xy + a_6 y^2 + a_7 x^3 + a_8 x^2 y + a_9 x y^2 \text{.} $$ Hence, we have an overconstrained system of equations with twelve data points and nine unknown coefficients \(a_1 \ldots a_9\) which is solved using a least-squares approach.

In two dimensions, it is no longer clear to me how to formulate a high-order correction, but Skamarock and Gassmann 2011 used their one-dimensional high-order correction in two dimensions by applying it at each cell face. It seems to me that their approach could be applied to cubicFit, though I have yet to have success applying a high-order correction to the OpenFOAM cubicFit implementation for arbitrarily-structured meshes. I hope to describe the features of this scheme in a future post.

Further reading