New Generation Algorithms for Computational Fluid Dynamics

Abstract

A new approach to the creation of new-generation CFD algorithms combining the advantages of conservative and characteristic difference schemes is discussed.

INTRODUCTION

Computational fluid dynamics (CFD) usually deals with the numerical solution of the Euler and Navier–Stokes equations taking into account the physicochemical processes involved. However, this term has recently gained a wider and deeper meaning. There has been a tendency [1] to treat the subject of CFD not as applications, but rather as the mathematical nature of solved equations, which is determined, on the one hand, by the nature of conservation laws and, on the other hand, by the property of hyperbolicity or “nearly hyperbolicity.”

By nearly hyperbolic systems of equations, we mean linear or quasilinear systems of conservation laws with a “perturbed” right-hand side representing an elliptic or integral operator multiplied by a small parameter $\varepsilon$. Nearly hyperbolic systems are also known as systems with dominant hyperbolicity (dominant transport). In the case of this treatment, CFD covers algorithms for the Euler equations, the Navier–Stokes equations at high Reynolds numbers, problems in dynamical elasticity theory, nonlinear optics, acoustics, classical nonstationary electrodynamics, and many others.

The hyperbolic nature of CFD problems determines their basic feature associated with the possibility of weak and strong discontinuities and, in the nonlinear case, mechanisms of their formation in the course of evolution. Quasilinear conservation laws with dominant hyperbolicity are characterized by multiple scales, i.e., by the nonlinear interaction of coherent structures of different sizes ranging from large ones determined by the size of the domain to the finest structures limited by the perturbation-of-hyperbolicity parameter $\varepsilon$.

Currently, a major problem in CFD is the convergence of the numerical solution to experimental observations under mesh refinement. Here, there are two intertwined components: the adequacy to the mathematical model used and the direct problem of grid convergence. We can say that the main issue of CFD is now to improve the predictive ability of computations under mesh refinement. This problem is solved theoretically for linear equations and at the level of recipes for nonlinear equations.

As applied to classical fluid dynamics problems, the problem of main interest is the predictive ability of numerical methods for turbulent flow simulation in the case of an incomplete resolution of the spectrum of turbulent fluctuations.

The number of recipes in CFD is constantly growing. However, in their wide variety, there is a tendency to unification. There appear treatments and approaches purporting to be universal. Primarily, we should note the principle of conservativeness [2, 3], according to which numerical algorithms at the discrete level have to express conservation laws underlying differential models. An important role is also played by the preservation of the monotonicity of the numerical solution [4] and nonlinear flux correction procedures ensuring monotonicity preservation [5–7].

As a rule, modern CFD methods are based on the finite volume method [1], which guarantees the fulfillment of conservation laws at the discrete level. The computation of convective fluxes is an independent problem.

To compute convective fluxes, it is natural to use the second determining property of CFD problems, namely, their characteristic nature. The hyperbolicity of the Euler equations is exhibited in that, in the one-dimensional case, they can be represented in the form of a system of homogeneous characteristic equations. In the multidimensional case, this is reduced to systems of inhomogeneous characteristic equations along an arbitrary spatial direction. The Navier–Stokes equations can also be brought to a similar form. As a result, in spite of their formally parabolic type, they can be treated as “perturbed” hyperbolic systems even at low Reynolds numbers.

In modern numerical algorithms of “high resolution” [5–7], the hyperbolic nature of CFD problems is reflected in the computation of fluxes by applying Riemann solvers (Godunov-type schemes). The next goal is a more organic union of conservative and characteristic methods. Numerical algorithms combining the advantages of characteristic and conservative methods are naturally called balance-characteristic algorithms, or new-generation algorithms.

CONSERVATIVE GRID-CHARACTERISTIC (CGCH) METHOD

Attempts to combine the advantages of grid and characteristic difference schemes [8] were made long ago [9]. Kholodov’s works [10] concerning the hybridization of the method of characteristics and grid methods had a large effect on the CFD community. The intensive development of computers led to a further call for new ideas on the combination of conservativeness and hyperbolicity in a unified computational technique.

Below, the basic idea of this combination is described as applied to the simplest linear transport equation

$$\frac{{\partial \varphi }}{{\partial t}} + c\frac{{\partial \varphi }}{{\partial x}} = 0,\quad c = {\text{const}} > 0.$$

The problem is to determine a grid function $\varphi _{j}^{{n + 1}}$ approximating the solution of this equation at grid nodes (Fig. 1) under given initial and boundary conditions. As applied to this equation, Kholodov’s grid-characteristic approach (the method of reverse characteristics) yields $\varphi _{j}^{{n + 1}} = \varphi\left( A \right)$, where $\varphi\left( A \right)$ is the value of the sought function at the point where the characteristic dropped from the node $\left( {n + 1,j} \right)$ intersects the time level $t = {{t}_{n}}$. This value is determined by interpolation based on known function values at nodes of this level. In this approach, we can choose interpolating polynomials of various orders, including ones with free parameters, whose values are then calculated by optimizing the dispersion characteristics of the scheme.

Fig. 1.

As was noted above, all these algorithms have the same shortcoming: they are not conservative.

They can be made conservative as follows.

In addition to the node values $\varphi _{j}^{n}$, we consider grid functions $\varphi _{{j - 1/2}}^{n}$ assigned to the middles of mesh cells. The former are referred to as “flux” variables, and the latter, as “conservative” variables.

For interpolation at the point $A$, we use a second-order polynomial coinciding with the grid function values at the midpoint and endpoints of the interval to obtain

$$\varphi _{j}^{{n + 1}} = (1 - 3r + 2{{r}^{2}})\varphi _{j}^{n} + 4r(1 - r)\varphi _{{j - 1/2}}^{n} + 2r(r - 0.5)\varphi _{{j - 1}}^{n};\quad r = c{\tau \mathord{\left/ {\vphantom {\tau h}} \right. \kern-0em} h},$$

((1))

where $\tau {\text{ and }}\;h$ are the step sizes in time and space, respectively. New values of the conservative variables $\varphi _{{j - 1/2}}^{{n + 1}}$ are computed using the second-order accurate conservative difference scheme

$$\frac{{\varphi _{{j - 1/2}}^{{n + 1}} - \varphi _{{j - 1/2}}^{n}}}{\tau } + c\frac{{\bar {\varphi }_{j}^{n} - \bar {\varphi }_{{j - 1}}^{n}}}{h} = 0;\quad \bar {\varphi }_{*}^{n}{\text{ = 0}}{\text{.5(}}\varphi _{*}^{n} + \varphi _{*}^{{n + 1}}{\text{)}}{\text{.}}$$

((2))

As a result, we obtain a new algorithm combining the characteristic and balance approaches.

It is easy to see that this algorithm has the second order of accuracy, and its viability is determined by its numerical stability and dispersion characteristics.

Let us analyze the dissipative and dispersion characteristics of the new scheme.

In Eqs. (1) and (2), we substitute the particular traveling-wave solution

$$\begin{gathered} \varphi _{j}^{n} = A\exp \left\{ {i\left( {\omega \tau n - kjh} \right)} \right\} = A{{q}^{n}}\exp \left\{ { - i\left( {kjh} \right)} \right\}; \\ \varphi _{{j - 1/2}}^{n} = B\exp \left\{ {i\left[ {\omega \tau n - k\left( {j - 0.5} \right)h} \right]} \right\} = B{{q}^{n}}\exp \left\{ { - i\left[ {k\left( {j - 0.5} \right)h} \right]} \right\}. \\ \end{gathered} $$

For the solution to exist, the following condition must be satisfied:

$$\left[ {q - (1 - 3r + 2{{r}^{2}}) - 2r(r - 0.5){{e}^{{ikh}}}} \right](q - 1){{e}^{{i{{kh} \mathord{\left/ {\vphantom {{kh} 2}} \right. \kern-0em} 2}}}} + 0.5Ar(q + 1)(1 - {{e}^{{ikh}}})4r(1 - r)B{{e}^{{i{{kh} \mathord{\left/ {\vphantom {{kh} 2}} \right. \kern-0em} 2}}}} = 0.$$

((3))

This quadratic equation has two roots, ${{q}_{1}} = {{q}_{1}}\left( {r,kh} \right)$ and ${{q}_{2}} = {{q}_{2}}\left( {r,kh} \right)$, which depend on the Courant number $r \in \left[ {0,1} \right]$ and the relative wave number $kh \in \left[ {\pi , - \pi } \right]$. The absolute values of these transition multipliers determine the stability domain of the scheme: the scheme is stable if $\left| {{{q}_{1}}} \right| = {{f}_{1}}\left( {r,kh} \right) \leqslant 1$ and $\left| {{{q}_{2}}} \right| = {{f}_{2}}\left( {r,kh} \right) \leqslant 1$. These quantities are plotted in Fig. 2, where the $x$ axis represents the Courant number $r$ and the $y$ axis, the relative wave number $kh$.

Fig. 2.

Dissipative surfaces.

It can be seen that the scheme is stable for $r < 0.7$.

Taking into account $q = \exp \left( {i\omega \tau } \right)$, the relative dispersion of the difference scheme is given by

$$\gamma \left( {r,kh} \right) = \frac{\omega }{{kc}} = - \frac{i}{{rkh}}\ln q,$$

which shows how the phase velocity of the harmonic with the relative wave number $kh$ differs from the velocity $c$ for various Courant numbers. The dispersion is called normal if $\gamma \left( {r,kh} \right) < 0$ and anomalous otherwise.

Figure 3 presents dispersion surfaces corresponding to different roots of characteristic equation (3). The first root is responsible for the dispersion of the numerical solution, and the second root, for the dispersion of the error in the consistency of the flux and conservative variables at the initial time [11].

Fig. 3.

Dispersion surfaces.

It can be seen that the scheme has normal dispersion for Courant numbers less than 0.7. The dispersion characteristics of the second root do not have a large effect on the solution.

Figure 4 compares the dispersion and dissipative surfaces of the first roots for the new scheme and the CABARET scheme [11]. It can be seen that, at low Courant numbers, CABARET has a high abnormal dispersion on short waves, which is compensated in the computations by nonlinear flux correction based on the maximum principle [12]. The new scheme is free of this shortcoming at low Courant numbers, so it can be expected to be more accurate in this range.

Fig. 4.

Comparison of dissipative and dispersion surfaces.

NONLINEAR FLUX CORRECTION

As was noted above, the conservative characteristic scheme (1), (2) has the second order of accuracy. Therefore, by Godunov’s theorem [4], it is not monotone. To make it monotone, the algorithm described above is supplemented with nonlinear flux correction [12] based on the maximum principle. Specifically, the new-level flux variable $\varphi _{j}^{{n + 1}}$ calculated according to (1) is treated as a preliminary value $\tilde {\varphi }_{j}^{{n + 1}}$, and its final value is determined as follows:

$$\varphi _{j}^{{n + 1}} = \left\{ {\begin{array}{*{20}{l}} {\tilde {\varphi }_{j}^{{n + 1}}\quad {\text{if}}\quad \left[ {\min \varphi } \right]_{{j - 1/2}}^{n} \leqslant \tilde {\varphi }_{j}^{{n + 1}} \leqslant \left[ {\max \varphi } \right]_{{j - 1/2}}^{n},} \\ {\left[ {\min \varphi } \right]_{{j - 1/2}}^{n}\quad {\text{if}}\quad \tilde {\varphi }_{j}^{{n + 1}} < \left[ {\min \varphi } \right]_{{j - 1/2}}^{n},} \\ {\left[ {\max \varphi } \right]_{{j - 1/2}}^{n}\quad {\text{if}}\quad \tilde {\varphi }_{j}^{{n + 1}} > \left[ {\max \varphi } \right]_{{j - 1/2}}^{n},} \end{array}} \right.$$

((4))

where

$$\left[ {\min \varphi } \right]_{{j - 1/2}}^{n} = \min \left\{ {\varphi _{{j - 1}}^{n},\;\varphi _{{j - 1/2}}^{n},\;\varphi _{j}^{n}} \right\};\quad \left[ {\max \varphi } \right]_{{j - 1/2}}^{n} = \max \left\{ {\varphi _{{j - 1}}^{n},\;\varphi _{{j - 1/2}}^{n},\;\varphi _{j}^{n}} \right\}.$$

((5))

Note that, when the final value $\varphi _{j}^{{n + 1}}$ given by (4) differs from $\tilde {\varphi }_{j}^{{n + 1}}$, the order of accuracy of the scheme is reduced to the first.

Fig. 5.

FEATURES OF THE CONSERVATIVE GRID-CHARACTERISTIC SCHEME FOR NONLINEAR INHOMOGENEOUS EQUATIONS

In the above-considered case, the transport velocity is a constant. For the more general quasilinear equation

$$\frac{{\partial \varphi }}{{\partial t}} + \frac{{\partial F{\text{(}}\varphi {\text{)}}}}{{\partial x}} = Q\left( {t,x,\varphi } \right);\quad \Rightarrow \;\frac{{\partial \varphi }}{{\partial t}} + c{\text{(}}\varphi {\text{)}}\frac{{\partial \varphi }}{{\partial x}} = Q\left( {t,x,\varphi } \right);\quad c{\text{(}}\varphi {\text{)}} = F' {\text{(}}\varphi {\text{)}} > 0,$$

((6))

the slope of the reverse characteristic depends on the solution, so the above-described algorithm becomes more complicated.

According to the predictor–corrector approach, we first compute an intermediate value of the conservative variable at a half-integer time level:

$$\frac{{\varphi _{c}^{{n + 1/2}} - \varphi _{c}^{n}}}{{{\tau \mathord{\left/ {\vphantom {\tau 2}} \right. \kern-0em} 2}}} + c_{c}^{n}\frac{{\varphi _{R}^{n} - \varphi _{L}^{n}}}{h} = Q_{c}^{{n + 1/2}}.$$

((7))

This intermediate variable is used to calculate the slope of the characteristic more accurately for computing new values of the flux variables (Fig. 5):

$$\begin{gathered} \varphi _{R}^{{n + 1}} = (1 - 3r + 2{{r}^{2}})\varphi _{R}^{n} + 4r(1 - r)\varphi _{c}^{n} + 2r(r - 0.5)\varphi _{L}^{n} + 0.5\tau Q_{c}^{{n + 1/2}}, \\ r = c_{c}^{{n + 1/2}}{\tau \mathord{\left/ {\vphantom {\tau h}} \right. \kern-0em} h}. \\ \end{gathered} $$

((8))

The new flux variables are also subjected to the nonlinear correction procedure (4), in which the minima and maxima are determined as

$$\begin{gathered} \left[ {\min \varphi } \right]_{{j - 1/2}}^{n} = \min \left\{ {\varphi _{{j - 1}}^{n},\;\varphi _{{j - 1/2}}^{n},\;\varphi _{j}^{n}} \right\} + \tau Q_{c}^{{n + 1/2}}; \hfill \\ \left[ {\max \varphi } \right]_{{j - 1/2}}^{n} = \max \left\{ {\varphi _{{j - 1}}^{n},\;\varphi _{{j - 1/2}}^{n},\;\varphi _{j}^{n}} \right\} + \tau Q_{c}^{{n + 1/2}}. \hfill \\ \end{gathered} $$

((9))

New conservative variables are found, as before, by applying the second-order accurate conservative difference scheme

$$\frac{{\varphi _{c}^{{n + 1}} - \varphi _{c}^{n}}}{\tau } + \frac{{F\left( {{{{\bar {\varphi }}}_{R}}} \right) - F\left( {{{{\bar {\varphi }}}_{L}}} \right)}}{h} = Q_{c}^{{n + 1/2}};\quad {{\bar {\varphi }}_{*}} = 0.5(\varphi _{*}^{{n + 1}} + \varphi _{*}^{n}).$$

((10))

GENERALIZATION TO MORE MEANINGFUL CASES

In the design of new-generation numerical algorithms for hyperbolic conservation laws in the multidimensional case, we can naturally distinguish several stages.

At the first stage, a spatial grid is constructed and the places to which the grid functions are assigned in mesh cells are determined. Two classes of grid functions (conservative and flux ones) are defined. Conservative grid functions correspond to the centers of mesh cells, and the flux grid functions, to the midpoints of faces (Fig. 6). The separation of the unknown grid functions into two classes is of fundamental importance. It is this separation that allows the hybridization of conservative and grid-characteristic difference schemes.

Fig. 6.

At the second stage, a system of integral equations is considered for each mesh cell and the fluxes on the faces are approximated by applying the midpoint rule [1]. As a result, we obtain a system of differential (in time) and discrete (in space) equations (known as differential-difference ones) that express the basic conservation laws on the grid.

This system of differential-difference equations is approximated in time by the predictor–corrector method up to second-order accuracy. At the predictor stage, intermediate values of the conservative variables are found at the level $\left( {n + 1{\text{/}}2} \right)$. At the corrector stage, these variables are calculated at the level $\left( {n + 1} \right)$ by applying a second-order scheme, provided that the flux variables at the new level are known.

New flux variables are computed using the characteristic form of the equations in a given direction. For hyperbolic conservation laws, such a form can always be constructed.

Given directions are determined as follows. A line segment is drawn from the face midpoint, at which the flux variables are determined, to the geometric center of a cell. For each face, there are two such segments, according to the number of adjacent cells. Characteristic forms are constructed along each of these segments.

For each eigenvalue of the one-dimensional hyperbolic operators, a local Riemann invariant is found [13] and the problem is reduced to one described in the previous sections. The values of the local Riemann invariants at the intersection point of the “direction characteristics” with the ${{t}_{n}}$ plane are calculated by interpolation based on known values of these invariants on the faces of the current cell and at its center at the current time.

The characteristic forms in the given directions are inhomogeneous, i.e., they contain nonzero right-hand sides depending on derivatives with respect to other directions. They can be calculated directly, but this is not reasonable. A much simpler and more efficient approach is to use the conservative variables at the intermediate time level obtained at the predictor phase. Specifically, the divergent equations are integrated in time by applying a first-order accurate explicit conservative difference scheme on the interval $\left[ {{{t}_{n}},\;{{t}_{n}} + {\tau \mathord{\left/ {\vphantom {\tau 2}} \right. \kern-0em} 2}} \right]$. The resulting intermediate values are used to replace the left-hand side of the characteristic form by its first-order approximation, thus determining the previously unknown right-hand side.

New values of the flux variables are found using the calculated right-hand sides and the values of the local invariants interpolated to the intersection point of the direction characteristics with the ${{t}_{n}}$ plane.

QUASI-HYDRODYNAMIC SYSTEMS OF EQUATIONS

A major characteristic feature of conservative characteristic difference schemes is that the variables involved are split into conservative and flux ones. As applied to systems of quasi-hydrodynamic equations [17, 18], this idea also generates a new class of numerical algorithms.

In the general case, a quasi-hydrodynamic system of equations can be written as

$$\frac{{\partial \mathbf{Q}}}{{\partial t}} + \varepsilon \frac{{{{\partial }^{2}}\mathbf{Q}}}{{\partial {{t}^{2}}}} = \operatorname{div} {\mathbf{S}_{k}},$$

((11))

where $\mathbf{Q}$ is the vector of variables to be determined, ${\mathbf{S}_{k}} = {\mathbf{S}_{k}}\left( {{\mathbf{Q}_{m}}} \right)$ are the fluxes determining the variation in the basic variable with index $k$, and $\varepsilon$ is a small parameter.

As applied to fluid dynamics problems, this system differs from the Navier–Stokes equations by terms of the second order of smallness in the Knudsen number: $\varepsilon = O(K{{n}^{2}})$ [17, 19, 20]. The quasi-hydrodynamic approach opens up new opportunities for the simulation of hydrodynamic flows on high-performance systems with massive parallelism [21, 22].

To apply the conservative characteristic approach, this system is represented in the form (see [21])

$$\frac{{\partial \mathbf{Q}}}{{\partial t}} = \operatorname{div} {{\Phi }_{k}};\quad \varepsilon \frac{{\partial {{\Phi }_{k}}}}{{\partial t}} = {\mathbf{S}_{k}} - {{\Phi }_{k}}.$$

((12))

The conservative variables $\mathbf{Q}$ are assigned to the cell centers, while the flux variables ${\mathbf{S}_{k}}$ and ${{\Phi }_{k}}$ are placed on cell faces.

At the first stage, in the transition from ${{t}_{n}}$ to ${{t}_{{n + 1}}} = {{t}_{n}} + {{\tau }_{n}}$, the second equation of system (12) is solved at corresponding points of the boundary:

$$\Phi _{k}^{{n + 1}} = \Phi _{k}^{n}\exp \left( { - \frac{\tau }{\varepsilon }} \right) + \mathbf{S}_{k}^{n}\left[ {1 - \exp \left( { - \frac{\tau }{\varepsilon }} \right)} \right].$$

((13))

At the second stage, the values of $\mathbf{Q}_{k}^{{n + 1}}$ are conservatively calculated from the known values of $\Phi _{k}^{{n + 1}}$.

Next, new values of the fluxes $\mathbf{S}_{k}^{{n + 1}}$ are calculated using their definition: $\mathbf{S}_{k}^{{n + 1}} = \mathbf{S}_{k}^{{}}\left( {\mathbf{Q}_{m}^{{n + 1}}} \right)$.

EXAMPLES OF NUMERICAL COMPUTATIONS

For the linear transport equation with initial data in the form of a rectangular profile, Fig. 7a shows the numerical solutions produced by CABARET (black curve), the conservative grid-characteristic scheme (red curve), and the first-order accurate upwind scheme after 100 time steps with a Courant number of 0.4.

Fig. 7.

Figure 7b presents the numerical solutions of the Hopf equation with the same initial conditions produced by CABARET (black curve) and the conservative grid-characteristic scheme (red curve) for a Courant number of 0.3.

DISCUSSION OF THE RESULTS

In the numerical solution of problems based on hyperbolic conservation laws, it is important to take into account their conservativeness and hyperbolicity. The importance of conservativeness was realized long ago. Accordingly, over the last decades, all numerical algorithms for such problems have been constructed using the finite volume method, which guarantees that the conservation laws are exactly satisfied at the discrete level. However, the determination of fluxes of conserved quantities remains an open question in this method.

Currently, a universal approach to finding fluxes relies on Godunov’s method, which involves solving a Riemann problem [4], and its numerous modifications [5–7, 14–16] aimed at reducing numerical viscosity, while preserving the monotonicity of the solution.

In recent years, another approach has appeared [12], which can be viewed as an alternative to Godunov’s method. It makes use of local Riemannian invariants of hyperbolic equations and is known as the CABARET scheme. However, along with its numerous advantages, this scheme has shortcomings associated with grid restrictions. Specifically, it has not yet been applied to triangular and tetrahedral grids, which are most popular in numerous applications.

The approach proposed in this paper combines the advantages of conservative and grid-characteristic methods and applies to grids of any type. A comparison of the conservative grid-characteristic (CGC) scheme and CABARET suggests the following conclusions.

• Both schemes are based on the finite volume approach and local Riemannian invariants.

• Both schemes are defined on the minimum stencil.

• Both schemes are second-order accurate on hexagonal unstructured grids.

• In contrast to CABARET, the CGC scheme does not have the time reversibility property.

• In contrast to CABARET, the CGC scheme has remarkable dispersion characteristics at low Courant numbers.

• In contrast to CABARET, the CGC scheme is relatively easy to extend to grids with an arbitrary cell topology.

• High-order accurate schemes can be constructed in the CGC class.