Advection schemes
In AMReX-Hydro, the fundamental algorithm is either a Method-of-Lines (MOL) or Godunov approach. Each method provides functions for two separate usages:
Construct values of the normal velocity at the centroid on each cell face, termed “Pre-MAC” or extrapolated velocity. Typically, this velocity is later MAC projected before being used as the advective velocity. (Information on the MAC projection is in the MAC Projection section.)
Construct states on faces, termed “edge states” or “Post-MAC.” These are typically later used to make fluxes which are then differenced to create the advective term. (Information on how fluxes and the convective term are constructed from edge states is given in the Computing Fluxes and Constructing the advective term sections.)
Domain boundary conditions affect the computation of these pre- and post-MAC states in the same way for all advection methods, and this is described in the Boundary conditions section. Note that while these routines ensure that the resulting computed states obey the boundary conditions, they also still require input with filled grow cells. All schemes also use the same routines to construct fluxes and then the convective term.
Next, we provide notation, and then detail the available advection schemes in EB-regular, as well as EB-aware form when available.
Note
If a cell and all of its neighbors have volume fraction of 1 (i.e. they are not cut or covered cells), the EB methodology will return exactly the same answer (to machine precision) as the non-EB methodology. Here we define neighbor to mean any cell that would be involved in the calculation of the face-based state, and the extent of the resulting neighborhood varies depending on the order of the slope used.
Notation
Here we use \((i,j,k)\) to denote cell centers (or centroids for EB), and thus \((i-\frac{1}{2},j,k)\) denotes the lower x-face of the \((i,j,k)\)-th cell, \((i,j+\frac{1}{2},k)\) denotes the upper y-face of the \((i,j,k)\)-th cell, etc.
Super- or subscript \(L\) (for left) indicates a state that has been extrapolated from values at lower x indices. \(R\) (for right) indicates extrapolation higher x indices. For example, for the x-face located at \((i+1/2,j,k)\), \(L\) indicates extrapolation from the \((i,j,k)\)-th cell center/centroid, and \(R\) extrapolation from the \((i+1,j,k)\)-th cell center/centroid.
Similarly, for the y-dimension, \(F\) (for forward) indicates a state that has been extrapolated from values at lower y indices and \(B\) (for back) indicates extrapolation from higher y indices. And for the third dimension, \(D\) (for down) indicates a state that has been extrapolated from values at lower z indices. \(U\) (for up) indicates extrapolation from higher z indices.
\(\U^{MAC}\) is the MAC-projected velocity at face centers (or centroids for EB).
We define \(\varepsilon = 1.e-8\) in Utils/hydro_constants.H. This is an empirically determined constant that works well for flows where velocities are on the order of 1.
Method of Lines (MOL)
The procedure for computing MAC velocities and edge states with MOL involves extrapolation in space only, and does not involve any time derivatives. All slope computations use second-order limited slopes as described in Slopes.
These algorithms are applied in the MOL namespace. For API documentation, see Doxygen: MOL Namespace.
Pre-MAC (API ref. MOL::ExtrapVelToFaces)
For computing the pre-MAC edge states to be MAC-projected, we define on every x-face:
where \(u^x\) are the (limited) slopes in the x-direction.
Boundary conditions are applied (as described in Boundary conditions). Then, at each face we upwind based on \(u_L\) and \(u_R\)
We similarly compute \(v_{i,j-\frac{1}{2},k}\) on y-faces and \(w_{i,j,k-\frac{1}{2}}\) on z-faces.
Post-MAC (API ref. MOL::ComputeEdgeState)
Once we have the MAC-projected velocities, we extrapolate all quantities to faces as above:
where \(s^x\) are the (limited) slopes in the x-direction.
Boundary conditions are applied (as described in Boundary conditions). Then, at each face, we upwind based on \(u^{MAC}_{i-\frac{1}{2},j,k}\)
Method of Lines with Embedded Boundaries (EBMOL)
AMReX-Hydro has also implemented an embedded boundary (EB) aware version of the MOL algorithm discussed above. All slope computations use second-order limited slopes as described in EB Slopes.
Pre-MAC (API ref. EBMOL::ExtrapVelToFaces)
For computing the pre-MAC edge states to be MAC-projected, we define on every x-face with non-zero area fraction:
where we calculate \(u^x\), \(u^y\) and \(u^z\) as described in EB Slopes, and \(\delta_x\), \(\delta_y\), and \(\delta_z\) are the components of the distance vector from the cell centroid to the face centroid of the face at \((i-\frac{1}{2},j,k).\)
Boundary conditions are applied (as described in Boundary conditions). Then, at each face we upwind based on \(u_L\) and \(u_R\)
We similarly compute \(v_{i,j-\frac{1}{2},k}\) on y-faces and \(w_{i,j,k-\frac{1}{2}}\) on z-faces.
Post-MAC (API ref. EBMOL::ComputeEdgeState)
Once we have the MAC-projected velocities, we predict all quantities to faces with non-zero area fractions as above:
where we calculate \(s^x\), \(s^y\) and \(s^z\) as described in EB Slopes, and \(\delta_x\), \(\delta_y\), and \(\delta_z\) are the components of the distance vector from the cell centroid to the face centroid of the face at \((i-\frac{1}{2},j,k).\)
Boundary conditions are applied (as described in Boundary conditions). Then, at each face we then upwind based on \(u^{MAC}_{i-\frac{1}{2},j,k}\)
Godunov Methods
AMReX-Hydro’s implementation uses dimenensionally unsplit algorithms with full corner coupling in 3D, with the option to use either piecewise linear (PLM) [Saltzman, 1994, Colella, 1990] or piecewise parabolic (PPM) [Colella and Woodward, 1984, Miller and Colella, 2002] reconstructions of the state.
These algorithms are applied in the Godunov namespace. For API documentation, see Doxygen: Godunov Namespace.
Pre-MAC (API ref. Godunov::ExtrapVelToFaces)
We extrapolate the normal velocities to cell faces using a second-order Taylor series expansion in space and time. For each face, we extrapolate the normal velocity component from the centers of the cells on either side to the face, creating left (L) and right (R) states. For face \((i+1/2,j,k)\) this gives
extrapolated from \((i,j,k)\), and
extrapolated from \((i+1,j,k).\) Here, \(\F\) is the sum of forcing terms, which typically might include viscous, gravitational, and the pressure gradient terms.
If the parameter use_ppm is false, the first derivatives normal to the face (in this
case \(u_x^{n,lim}\)) are evaluated using a monotonicity-limited fourth-order
slope approximation as described in Slopes.
Otherwise the Piecewise Parabolic Method (PPM) [Colella and Woodward, 1984, Miller and Colella, 2002] is used
to compute
The transverse derivative terms (\(\widehat{v u_y}\) and \(\widehat{w u_z}\) in this case) are evaluated using a three step process: first extrapolating all velocity components to the transverse faces from the cell centers on either side (either via PLM or PPM), applying boundary conditions and then choosing between these states using the upwinding procedure defined below. In particular, in the \(y\) direction we define
Values are similarly traced from \((i,j,k)\) and \((i,j,k+1)\) to the \((i,j,k+\frac{1}{2})\) faces to define \(\widehat{\boldsymbol{U}}^D_{i,j,k+\frac{1}{2}}\) and \(\widehat{\boldsymbol{U}}^{U}_{i,j,k+\frac{1}{2}}\), respectively.
If the parameter use_forces_in_trans is true, the forcing terms (\(\F\) in
Eqs. (1) and (2)) are added to \(\widehat{\U}\) now. Otherwise, they are included later in the the
formation of the edge state.
Next, boundary conditions are enforced on domain faces as described in Boundary conditions #2. Note that this means face-based values lying within the physical boundary but not exactly on the boundary face (e.g. values located on the y-faces of ghost cells abutting the x-boundary but not on the y-boundary) do not have boundary conditions enforced at this point.
Now, we define a normal advective velocity on the face (suppressing the \(({i,j+\frac{1}{2},k})\) spatial indices on front and back states here and in the next equation):
We now upwind \(\widehat{\boldsymbol{U}}\) based on \(\widehat{v}_{{i,j+\frac{1}{2},k}}^{adv}\):
In 3D, we complete the intermediate transverse-face centered states by accounting for transverse corner coupling following [Saltzman, 1994, Colella, 1990]. For example, for \(u\) predicted to y-faces we modify with a factor of the z-derivative at cell centers
and then apply boundary conditions on domain faces before upwinding according to \(\hat{v}_{i,j+\frac{1}{2},k}^{adv}\) as was done above for \(\widehat{\U}\). \(\widebreve{\boldsymbol{U}}_{{i,j-\frac{1}{2},k}}, \widebreve{\boldsymbol{U}}_{i,j,k+\frac{1}{2}}\) and \(\widebreve{\boldsymbol{U}}_{i,j,k-\frac{1}{2}}\) are constructed in a similar manner. For 2D, we take \(\widebreve{\U} = \widehat{\U}\).
We use these upwind values to form the transverse derivatives in Eqs. (1) and (2) :
We now have all the terms needed to form \(\tilde{u}\).
If use_forces_in_trans is false, the forcing terms were not included in the computation of the
transverse deriviates and are instead included at this point.
We apply boundary conditions on domain faces,
including preventing backflow (as described in Boundary conditions #2 & 3).
The normal velocity at each face is then determined by an upwinding procedure based on the states predicted from the cell centers on either side. The procedure is similar to that described above, i.e. (suppressing the (\(i+\frac{1}{2},j,k\)) indices)
We follow a similar procedure to construct \(\tilde{v}^{n+\frac{1}{2}}_{i,j+\frac{1}{2},k}\) and \(\tilde{w}^{n+\frac{1}{2}}_{i,j,k+\frac{1}{2}}\). We refer to this unique value of normal velocity on each face as \(\boldsymbol{U}^{MAC,*}\).
Post-MAC (API ref. Godnuov::ComputeEdgeState)
Here, the face-centered advective velocity field, which we will call \(\U^{MAC}\), is already known. Typically, this is the MAC projection of \(\U^{MAC,*}\), which would have been computed via the Pre-MAC procedure detailed above. We extrapolate all quantities to faces as above:
extrapolated from \((i,j,k)\), and
extrapolated from \((i+1,j,k).\) Details of how these terms are computed are analogous to the Pre-MAC case.
At each face we then upwind based on \(u^{MAC}_{i-\frac{1}{2},j,k}\)
Godunov with Embedded Boundaries (EBGodunov)
AMReX-Hydro contains an embedded boundary (EB) aware version of the Godunov algorithm discussed above, although with fewer options available. This EB implementation employs a piecewise linear method (PLM), and always includes any forcing terms after the computation of the transverse terms. EBGodunov attempts to use fourth-order limited slopes wherever possible, as described in EB Slopes.
Pre-MAC (API ref. EBGodunov::ExtrapVelToFaces)
We extrapolate the normal velocities to cell faces using a second-order Taylor series expansion in space and time. For each face with a non-zero area fraction, we extrapolate the normal velocity component from the centroids of the cells on either side to the face centroid, creating left (L) and right (R) states. For face \((i+1/2,j,k)\) this gives
extrapolated from \((i,j,k)\), where
and
extrapolated from \((i+1,j,k),\) where
Here, \(F\) is the sum of forcing terms; \(\delta_x,\) \(\delta_y\) and \(\delta_z\) are the components of the distance vector from the cell centroid to the face centroid of the \(x\)-face at \((i-\half,j,k)\); and the slopes \((u^x,u^y,u^z)\) are calculated as described in the EB Slopes section.
The transverse derivative terms ( \(\widehat{v u_y}\) and \(\widehat{w u_z}\) in this case) are evaluated by first extrapolating all velocity components to the face centroids of the transverse faces from the cell centers on either side, applying boundary conditions on domain faces, and then choosing between these states using the upwinding procedure defined below. In particular, in the \(y\) direction we define \(\widehat{\boldsymbol{U}}^F_{i,j+\frac{1}{2},k}\) and \(\widehat{\boldsymbol{U}}^B_{i,j+\frac{1}{2},k}\) analogously to how we defined \(\hat{u}_{i+\frac{1}{2},j,k}^{R}\) and \(\hat{u}_{i+\frac{1}{2},j,k}^{L}\), but here on the y-faces and including all three velocity components. Values are similarly traced from \((i,j,k)\) and \((i,j,k+1)\) to the \((i,j,k+\frac{1}{2})\) faces to define \(\widehat{\boldsymbol{U}}^D_{i,j,k+\frac{1}{2}}\) and \(\widehat{\boldsymbol{U}}^{U}_{i,j,k+\frac{1}{2}}\), respectively.
In this upwinding procedure we first define a normal advective velocity on the face (suppressing the \(({i,j+\frac{1}{2},k})\) spatial indices on front and back states here and in the next equation):
We now upwind \(\widehat{\boldsymbol{U}}\) based on \(\widehat{v}_{{i,j+\frac{1}{2},k}}^{adv}\):
In 3D, we modify the intermediate transverse-face centered states to accounting for transverse corner coupling. For example, for \(u\) predicted to y-faces we add a factor of the z-derivative
where \(alpha\) are cell face area fractions and \(kappa\) is the cell volume fraction. Then we apply boundary conditions on domain faces before upwinding according to \(\hat{v}_{i,j+\frac{1}{2},k}^{adv}\) as was done above for \(\widehat{\U}\). \(\widebreve{\boldsymbol{U}}_{{i,j-\frac{1}{2},k}}, \widebreve{\boldsymbol{U}}_{i,j,k+\frac{1}{2}}\) and \(\widebreve{\boldsymbol{U}}_{i,j,k-\frac{1}{2}}\) are constructed in a similar manner. For 2D, we take \(\widebreve{\U} = \widehat{\U}\).
If any of the four faces that contribute to the transverse derivatives for a particular cell have zero area, all of the transverse and forcing terms are identically set to 0. For example, when constructing \(\tilde{u}_{i+\half,j,k}^{L,\nph}\), if any of the areas \(a_{i,\jph,k}, a_{i,\jmh,k}, a_{i,j,\kmh}\) or \(a_{i,j,\kph}\) are zero, then we simply define
and use this in the upwinding step given by Eq. (11).
For cut faces (i.e. faces intersecting the EB), \(\widebreve{\U}\) and \(\widehat{\U}_{ad}\) are linearly extrapolated from face centroids to face centers. Then the transverse derivatives are constructed from these face centered values using the same formulas as for the non-EB case (Eq. (3)).
The normal velocity at each face is then determined by an upwinding procedure based on the states predicted from the cells on either side. The procedure is similar to that described above, i.e. (suppressing the (\(i+\frac{1}{2},j,k\)) indices)
We follow a similar procedure to construct \(\tilde{v}^{n+\frac{1}{2}}_{i,j+\frac{1}{2},k}\) and \(\tilde{w}^{n+\frac{1}{2}}_{i,j,k+\frac{1}{2}}\). We refer to these unique values of normal velocity on each face as \(\boldsymbol{U}^{MAC,*}\).
Post-MAC (API ref. EBGondunov::ComputeEdgestate)
Here, the face-centered advective velocity field, which we will call \(\U^{MAC}\), is already known. Typically, this is the MAC projection of \(\U^{MAC,*}\), which would have been computed via the Pre-MAC procedure detailed above. Now we predict all quantities to faces. Let the scalar \(s\) represent any advected quantities as well as all three velocity components. We now extrapolate \(s\) from cell centroids to face centroids as described in Sec. Pre-MAC (API ref. EBGodunov::ExtrapVelToFaces). For example, on face \((i+1/2,j,k)\) we define
extrapolated from \((i,j,k)\), where
and
extrapolated from \((i+1,j,k),\) where
Here again \(\delta_x,\) \(\delta_y\) and \(\delta_z\) are the components of the distance vector from the cell centroid to the face centroid of the \(x\)-face at \((i-\half,j,k)\), and the slopes \((u^x,u^y,u^z)\) are calculated as decribded in the EB Slopes section.
The transverse terms are computed exactly as described earlier for the Pre-MAC case, except for the upwinding process. Where we previously used the predicted states themselves to upwind, we now use the component of the advective velocity normal to the face in question.
We upwind \(\tilde{s}_{i+\half,j,k}^{L,\nph}\) and \(\tilde{s}_{i+\half,j,k}^{L,\nph}\) using the normal component of \(\U^{MAC}\) to define \(\tilde{s}_{i+\half,j,k}^{\nph}.\) Again, suppressing the subscripts, we define
BDS Algorithm
The Bell-Dawson-Shubin (BDS) algorithm is a higher order Godunov method for scalar conservation laws in multiple dimensions. Satisfying the maximum principal for constant coefficient linear advection, the BDS routine provides accurate resolution for smooth problems while avoiding undershoot and overshoot for non-smooth profiles. Additional details and comparisons to other schemes can be found in [Nonaka et al., 2011] and references therein.
This implementation of BDS closely follows the Godunov approach and leverages some of the same code. The difference appears in the computation of edge states given face-centered velocities, i.e. the Post-MAC computation. Currently, periodic, Dirichlet, and outflow (extrapolation) boundary conditions are supported. Embedded boundaries are not supported within BDS at this time. If additional functionality is desired, or if questions remain after reading this guide, further help is available by submitting an issue through Github
Pre-MAC
The BDS routine follows the Godunov PLM method to extrapolate velocities to cell faces, see Godunov Methods: Pre-MAC.
Post-MAC
In the notation below, \(s\) is a scalar field of the form \(s=s(x,y,z,t)\) and \({\U}=(u,v,w)\) represents a known face-centered velocity field, typically the projected velocity field from the Pre-MAC step (\(\U^{MAC}\)). \(s^n_{ijk}\) represents the average value of \(s\) over the cell with index \((ijk)\) at time \(t^n\). At each face the normal velocity (e.g., \(u_{i+1/2,j,k}\)) is assumed constant over the time step.
Obtaining the edge states is a two step process:
Step 1: Construct a limited piecewise trilinear (bilinear in 2D) representation of the solution in each grid cell of the form,
Step 2: Construct edge states \(s_{i+1/2,j,k}\), etc. by integrating the limited piecewise trilinear (bilinear in 2D) profiles over the space-time region determined by the characteristic domain of dependence of the face. We enforce no inflow at an outflow face as described in the post-MAC Boundary Conditions Section.