Abstract
We present a second-order Godunov algorithm to solve time-dependent hyperbolic systems of conservation laws on irregular domains. Our approach is based on a formally consistent discretization of the conservation laws on a finitevolume grid obtained from intersecting the domain with a Cartesian grid. We address the small-cell stability problem associated with such methods by hybridizing our conservative discretization with a stable, nonconservative discretization at irregular control volumes, and redistributing the difference in the mass increments to nearby cells in a way that preserves stability and local conservation. The resulting method is second-order accurate in L 1 for smooth problems, and is robust in the presence of large-amplitude discontinuities intersecting the irregular boundary.
Introduction
In this paper, we present an extension of the unsplit method for time-dependent hyperbolic conservation laws in [8, 17] to the case of an embedded boundary representation of irregular geometries. Our approach is a generalization of the conservative method in [14] , following the ideas in [2, 6] . The present method uses the 
Notation
Cartesian grids with embedded boundaries are useful to describe finite-volume representations of solutions to PDE in the presence of irregular boundaries. In Fig. 1 , the gray area represents the region excluded from the solution domain. The underlying description of space is given by rectangular control volumes on a Cartesian grid Ç i ¼ ½ði À 1 2 vÞh; ði þ 1 2 vÞh; i 2 Z D , where D is the dimensionality of the problem, h is the mesh spacing, and v is the vector whose entries are all one. Given an irregular domain X, we obtain control volumes V i ¼ Ç i \ X and faces A Þhg. We also define A B i to be the intersection of the boundary of the irregular domain with the Cartesian control volume: A B i ¼ oX \ Ç i . For ease of exposition, we will assume here that there is only one control volume per Cartesian cell. The algorithm described here has been generalized to allow for boundaries whose width is less that the mesh spacing.
Notation
We recognize three kinds of cells and faces: regular, irregular and covered. Regular cells are cells within the solution domain away from the embedded boundary. Covered cells are completely covered by the boundary and are not part of the solution domain. Irregular cells are cells cut by the embedded boundary. State variables are defined at the geometric centers of regular grid cells, even if a cell is irregular. The classification for faces is similar. In the most general case, a face is defined as a pair of control volumes in adjacent cells. In order to avoid the notational complications this would entail, we will assume that, if a face is covered, then at least one of the cells adjacent to the face is covered. This is condition is equivalent to assuming a minimum thickness to the covered regions.
Notation
To construct finite-difference methods using this description, we will need several quantities derived from these geometric objects.
Notation
Volume fractions j and area fraction a:
Notation
; a where D is the dimension of space and 1 6 d 6 D. We assume we can compute all derived quantities to O(h 2 ). With just these geometric descriptors, we can define a conservative discretization of the divergence operator. LetF ¼ ðF 1 . . . F D Þ be a function of x. Then r ÁF % 1
Notation
where (1) is obtained by replacing the normal components of the vector fieldF with the values at the centroids.
Stable evolution of hyperbolic conservation laws
We want to solve a hyperbolic system of conservation laws
Stable evolution of hyperbolic conservation laws
While the algorithm we describe here applies to general systems of hyperbolic conservation laws, we will show results for the case of polytropic gas dynamics in two and three dimensions U ¼ ðq; qu; qEÞ
Stable evolution of hyperbolic conservation laws
Here q is the fluid density, ðu
Stable evolution of hyperbolic conservation laws
2 the total energy per unit mass, and p the pressure and c > 1 the ratio of specific heats.
Stable evolution of hyperbolic conservation laws
We discretize the solution to (5) in space and time, approximating U by values at Cartesian cell centers: U n i % U ðih; nDtÞ; i 2 Z D . We can also use the quadrature rule (1) to construct the following conservative discretization of r Á F :
Stable evolution of hyperbolic conservation laws
Ideally we would like to use an explicit finite difference approximation to compute
Stable evolution of hyperbolic conservation laws
Þ, and use (8) to compute the discrete evolution of U,
Stable evolution of hyperbolic conservation laws
The update formula (9) satisfies the following discrete conservation identity:
Stable evolution of hyperbolic conservation laws
where C is any collection of control volumes, and oC is the set of cell faces and boundary faces forming the boundary of C. The difficulty with this approach is that the CFL stability constraint on the time step is at best Dt ¼ Oð
Stable evolution of hyperbolic conservation laws
is the magnitude of the maximum wave speed for the ith control volume. This is the well-known small-cell problem for embedded boundary methods. There have been a number of proposals to deal with this problem, including merging the small control volumes with nearby larger ones [7, 16] , and the development of specialized stencils that guarantee the required cancellations in (8) [4, 3, 5, 10] . The approach we have taken to this problem has been to expand the range of influence of the small control volumes algebraically to obtain a stable method [2, 6, 14] . The starting point for this approach is to compute a stable, but nonconservative approximation to r ÁF . One computes the a flux difference on the full Cartesian cell:
Stable evolution of hyperbolic conservation laws
where the fluxes in this expression are centered at ði AE
Stable evolution of hyperbolic conservation laws
The initial update uses a linear hybridization of the two estimates of r ÁF
Stable evolution of hyperbolic conservation laws
If we choose, for example, g i ¼ j i , then the small denominator in ðr ÁF Þ C is cancelled, and we obtain a stable method. However, the method fails to conserve, in that it does not satisfy an identity of the form (10) . This lack of conservation is measured by the difference between the mass increment j i ðU nþ1 i À U n i Þ given by (9) and that given by (12) 
Stable evolution of hyperbolic conservation laws
To maintain overall conservation, we redistribute dM into nearby cells (Fig. 2) :
Stable evolution of hyperbolic conservation laws
where N ðiÞ is some set of indices in the neighborhood of i. The sum condition (14) makes the redistribution step conservative: a relationship of the form (10) is satisfied, with some additional boundary terms corre- sponding to redistribution into or out of the domain C. In addition, w i;i 0 must be bounded independent of ðj i 0 Þ À1 . One example of a redistribution strategy that meets our requirements is w i;i
Stable evolution of hyperbolic conservation laws
N ðiÞ is a set of indices whose components differ from those of i by no more than one. For problems in gas dynamics involving strong shocks, the following mass-weighted redistribution has been observed to be more robust [14] :
Stable evolution of hyperbolic conservation laws
where q NC is a nonconservative estimate of the density at the new time
Stable evolution of hyperbolic conservation laws
Our procedure for calculating the fluxes used to compute ðr ÁF Þ C assumes that we have a second-order accurate method for computing fluxes at the centers of cell faces
Stable evolution of hyperbolic conservation laws
For all noncovered control volumes i. We use these fluxes in (6) to compute ðr ÁF Þ NC . To compute r ÁF C ,
Stable evolution of hyperbolic conservation laws
we interpolate the fluxes (11) to the face centroids, following [9] . In two dimensions, we use linear interpolation
Stable evolution of hyperbolic conservation laws
In three dimensions, we use bilinear interpolation, following [18] : 
Stable evolution of hyperbolic conservation laws
where DtLðU Þ denotes the increment of the discrete solution by one time step outlined above, given data U at the beginning of the time step. This leads to a truncation error estimate 
& ð22Þ
This truncation error estimate follows from (1) and the fact that ðr ÁF Þ NC has a truncation error of O(h), independent of j. From this it follows that the truncation error of the hybrid method (12) satisfies (22).
& ð22Þ
The behavior of these methods can be understood from a modified equation analysis. We expect that the solution to the modified equation approximates the numerical solution to one order higher accuracy than the solution to the original conservation laws do, wheres is the piecewise constant interpolation of the grid function s nþ 1 2 in space and time over each control volume. This suggests that the reduced order of accuracy in (22) will behave differently depending on whether or not the irregular boundary is characteristic. In the case that the boundary is noncharacteristic, a signal is exposed to the O(h) forcing in (23) for a time that is OðDtÞ ¼ OðhÞ, leading to an integrated contribution to the solution error that is O(h 2 ). In the case that the boundary is characteristic, a signal propagates along the boundary for an O(1) length of time, leading to an integrated contribution to the solution error that is O(h). However, that contribution is concentrated along the boundary, so that the solution error in the interior remains O(h 2 ), leading to an
& ð22Þ
For the gas dynamics examples considered here, a solid wall boundary is characteristic for the particle paths, but mostly noncharacteristic for acoustic wave propagation, so we expect to see convergence rates intermediate between the two limiting cases.
& ð22Þ
Critical to the success of this approach is the calculation of ðr ÁF Þ NC . In control volumes with j i ( 1, ðr ÁF Þ NC is almost entirely responsible for the update of U i . For that reason, ðr ÁF Þ NC must be designed carefully, so that, for example, the solution on small control volumes comes into equilibrium with the larger ones around it.
Flux calculation
Given U n i , we need to compute an O(h 2 ) estimate of the fluxes
Flux calculation
Specifically, we want to compute the fluxes at the center of the Cartesian grid faces corresponding to the faces of the embedded boundary geometry. For many applications it is useful to perform the flux calculation using nonconservative variables W = W(U). For the case of polytropic gas dynamics, the primitive variables are W = (q, u, p)
Flux calculation
T . The quasilinear equations for these variables are given as follows:
Flux calculation
We use an upstream-centered Taylor expansion of the solution from the cell center at the initial time to the cell face at the half-time.
Flux calculation
where RðW L ; W R ; dÞ is the solution to the Riemann problem with left and right states W L ; W R for the 1D equations in the dth coordinate direction. In computing W nþ 1 2 i;AE;e d we follow the approach in [8, 17] . We use centered differences with limiting to approximate the derivatives in the d direction, and a lower-dimensional Godunov method to approximate the remaining tangential derivatives. In extending this to the case of embedded boundaries, it will be necessary to replace extrapolation step (26) on cells that are covered, but adjacent to valid control volumes.
Flux calculation
The algorithm is given as follows:
Flux calculation
(1)
Flux calculation
where k k are eigenvalues of A 
Flux calculation
(ii,2D):
Flux calculation
(ii,3D):
Flux calculation
5. Algorithm details
Slope calculation
The notation CC ¼ AjBjC means that the 3-point formula A is used for CC if all cell-centered values it uses are available, the 2-point formula B is used if the cell to the right (i.e., the high side) of the current cell is covered, and the 2-point formula C is used if the cell to the left (i.e., the low side) current cell is covered.
Slope calculation
To compute the limited differences in the first step on the algorithm, we use the fourth-order slope calculation [8] combined with characteristic limiting
Slope calculation
There are two versions of the van Leer limiter D vL ðdW C ; dW L ; dW R Þ that are commonly used. One is to apply a limiter to the differences in characteristic variables. We compute expansions of one-sided and centered differences in characteristic variables and apply van Leer limiter.
Slope calculation
For a variety of problems, including our gas dynamics example, it suffices to apply the van Leer limiter componentwise to the differences. Formally, this can be obtained from the more general case above by taking the matrices of left and right eigenvectors to be the identity.
Slope calculation
As discussed in [19] , for Godunov methods it is necessary to introduce additional dissipation at strong compressive discontinuities in continum mechanics problems. Following the approach in [8] , we do this using two mechanisms. One, discussed in Section 5.3, is to add a small amount of artificial viscosity to the fluxes. The other is to introduce additional slope limiting in places where the steepness of the discontinuity exceeds some threshhold. We compute a flattening coefficient f i , a multiplicative factor by which we reduce the slopes. We assume that there is a quantity corresponding to the pressure in gas dynamics (denoted here as p) which can act as a steepness indicator, and a quantity corresponding to the bulk modulus (denoted here as K, given as cp in a gas), that can be used to nondimensionalize differences in p
Slope calculation
ðK; dÞ i Þ;
Slope calculation
fðdp 1 ; dp 2 ; p 0 Þ ¼ 0 if 
Extrapolation to covered faces
A covered face is a face whose aperature vanishes. To compute the stable, nonconservative divergence of the flux (see (11)), we need a second-order flux at covered faces. The flux is obtained by solving a Riemann problem at the face. For the side of the face next to the control volume, we use the extrapolated state from the control volume. For the other side of the covered face, we must extrapolate from neighboring values at the same orientation of the face.
Extrapolation to covered faces
Specifically, assume that all i is not covered, but i Ç e d is covered, so that the face connecting the two is covered. Then we want to compute W iÇe d ;AE;d , given a collection of values fW i 0 ;AE;d g that are assumed to be defined if a i 0 AE 1 2 e d 6 ¼ 0.
Two-dimensional extrapolation
In two dimensions, extrapolation to covered faces is done as illustrated in Fig. 3 . First we define the control volumes involved
Two-dimensional extrapolation
where
Two-dimensional extrapolation
To extrapolate to the covered faces, we use a linear combination of the values defined above to compute the value along a ray normal to the boundary and passing through the center of the covered face. We then extrapolate that value to the covered face using the second-order slopes combined with characteristic limiting described in Section 5.1. In the case where one of the values being used to interpolate corresponds to a value on the cell adjacent to the covered face in question (the case illustrated in Fig. 3 ) we use a value extrapolated from i s (the cell adjacent in the d direction) rather than i. This choice satisfies the design criterion that the action of the nonconservative evolution should, over time, tend to make the solution at i tend toward the value of a locally constant solution in the surrounding cells. This was the design criterion for computing covered faces in [14] ; the procedure given here has the same goal, but using an approach that produces second-order accurate fluxes. For example, in the case of a linear equation and the normal pointing in the e 1 direction, extrapolation from a locally constant state to the right of i in Fig. 3 leads to the solution in i to eventually take on that constant value. If one used the value at the face extrapolated from i, the solution would tend to the locally constant value be true only if the advection velocity were negative; otherwise, the value at i would remain unchanged. Fig. 3 . Illustration of extrapolation to covered faces in two dimensions The covered face is at C. We extrapolate from A to Ae and interpolate between Ae and B to the point X where the boundary normal intersects the line. We then extrapolate back along the normal to get to the covered face.
Two-dimensional extrapolation
If jn d j P jn d 0 j:
Two-dimensional extrapolation
We found that the use of the linear interpolation algorithms (36), (37) to compute the slopes used in extrapolating to the covered faces led to a more robust and accurate algorithm than other simpler choices that we considered. The intent is to use slopes computed at the same cell centers as the values used in the original linear interpolation in Fig. 3 , and in the same proportions. By using that choice, it appears that no further limiting of those slopes is required. If one or both of the faces from which we are extrapolating are covered we drop order. If only one of the faces is covered we set the extrapolated value to be the value on the other face. If both faces are covered, we set the extrapolated value to W n i .
Extrapolation to covered face in three dimensions
We define the direction of the face normal to be d and d 1 ; d 2 to be the directions tangential to the face. The procedure extrapolation procedure is given as follows:
Extrapolation to covered face in three dimensions
Define the associated control volumes. Form a 2 Â 2 grid of values along a plane h away from the covered face and bilinearly interpolate to the point where the normal intersects the plane. Use the slopes of the solution to extrapolate along the normal to obtain a second-order approximation of the solution at the covered face.
Extrapolation to covered face in three dimensions
Which plane is selected is determined by the direction of the normal. See Fig. 4 for an illustration.
Extrapolation to covered face in three dimensions
we define a bilinear function B that interpolates the 2 Â 2 grid of values. Fig. 4 . Illustration of extrapolation to covered faces in three dimensions. The covered face is at C. We extrapolate from A to B to form a plane of values in d1 À d2. We interpolate within that plane to the point X where the boundary normal intersects the plane. We then extrapolate back along the normal to get to the covered face.
Extrapolation to covered face in three dimensions
If any of the values required to perform the interpolation are unavailable, e.g., because the cells are covered, we drop order by using a weighted sum of the available values:
Extrapolation to covered face in three dimensions
where the sums are over i 0 2 fi 00 ; i 01 ; i 10 ; i 11 g, provided that at least one of the i 0 is not covered. If all of the faces used for interpolation are covered, we set the extrapolated value to be W n i .
Artificial viscosity
For compressive discontinuities in continuum mechanics problems, we add a small artificial viscosity. This takes the form of an increment to the flux by an undivided difference of
Artificial viscosity
We modify the covered face with the same divergence used in the adjacent uncovered face.
Artificial viscosity
d is not, we set
Artificial viscosity
This has the effect of negating the effect of artificial viscosity on the nonconservative divergence of the flux at irregular cells.
Computing fluxes at the irregular boundary
The flux at the embedded boundary is centered at the centroid of the boundary x B . We extrapolate the primitive solution in space from the cell center. We then transform to the conservative solution and extrapolate in time using the stable, nonconservative estimate of the flux divergence 
Computing fluxes at the irregular boundary
Here R B denotes the solution to the boundary Riemann problem, which takes a value of W at the boundary and returns a flux that satisfies the boundary conditions. For continuum mechanics problems in which we are using an artificial viscosity, we calculate an approximation of the divergence of the velocity at the irregular cell ðDuÞ i and use it to modify the flux to be consistent with artificial viscosity. The d-direction momentum flux at the irregular boundary is given by p B n d , where p B is the pressure to emerge from the Riemann solution in Eq. (51). For artificial viscosity, we modify this flux as follows:
Results

Convergence tests
Our test problem is a simple wave propagating in a straight circular channel (a straight-walled channel in two dimensions). The flow field is a stagnant fluid with a small perturbation in a single Riemann invariant. We specify an initial profile for density at time t ¼ 0, 
Convergence tests
The parameters are: a, the amplitude of the wave; w, the width of the wave; andn, the direction of propagation of the wave. The initial pressure is found from the isentropic relation
Convergence tests
The initial fluid velocity is found by characteristic analysis. The value of the Riemann invariant
Convergence tests
is taken from the profile u ¼ u 0 ðxÞ, c ¼ c 0 ðxÞ, while the Riemann invariant
Convergence tests
is taken from the reference ambient conditions
Convergence tests
The exact solution uðx; tÞ is obtained by using the profile u 0 ðx þ Þ, c 0 ðx þ Þ in (56), where x þ ðx; tÞ ¼ x À ðu þ cÞt, and iterating to convergence of x þ .
Convergence tests
In the two-dimensional problem, the sides of the channel are at a 30°angle with the x-axis, and the width of the channel is 0.125. In three dimensions, axis of the cylinder is (4, 1, 1) and its radius is 0.0625. The parameters of the pulse are a ¼ 10 À4 , w ¼ 0.2, and its direction is along the axis of the cylinder. The finer grid is 256 · 64 · 64 and the coarser is 128 · 32 · 32 in three dimensions. For the two-dimensional problem, the grids are 256 · 256 and 128 · 128.
Convergence tests
The truncation error at a given grid resolution, s h , is approximated by
Convergence tests
where U e ðtÞ is the exact solution evaluated at grid points, and U h ðtÞ is the numerical solution computed with initial data given by U e ð0Þ. This expression is an O(h 2 ) estimate of the error in the right-hand side of the PDE during one time step. The solution error at a given grid resolution, h , is approximated by
Convergence tests
The L 1 norm of the error is calculated as follows:
Convergence tests
The L 2 norm of the error is calculated as follows:
Convergence tests
where t is some fixed time interval independent of the mesh spacing. The order of convergence p is estimated by
Convergence tests
Finally, for the purpose of the convergence study, we have turned off the van Leer limiters, using instead the linear difference formulas for computing slopes, this allows us to determine the extent to which the modified equation analysis is valid, without the contaminating effects of limiters acting at extrema in the interior of the domain. Similarly, we have also set the artificial viscosity coefficient to zero. The results of these convergence tests are shown in Tables 1-12 . In both two and three dimensions, we obtain the expected truncation results in all norms. The truncation error is first order in max norm, and because of the estimate (22) the effect of the truncation error on the solution error: the boundary is characteristic for the particle paths, but mostly noncharacteristic for acoustic waves, leading both first-and second-order contributions to the solution error.
Strong shock calculations
We have implemented an adaptive mesh refinement (AMR) version of the embedded boundary solver described above using the same fully conservative method described in [14] . We use this implementation to compute solutions to time-dependent compressible flow with strong shocks.
Strong shock calculations
In Fig. 5 , we show results for the double Mach reflection test problem in [19] using an embedded boundary representation of the ramp. In Fig. 6 we show the same problem computed using the method in [8] on the grid-aligned configuration in [19] . There are two differences between the grid-aligned and embedded boundary solutions. One is that the grid-aligned case displays signs of incipient Kelvin-Helmholtz instability in the main contact discontinuity, while the embedded boundary solution at the same resolution does not. Such a result is not surprising, since the contact discontinuity in the grid-aligned solution is moving much more slowly in the vertical direction than the embedded boundary solution, and consequently undergoes less dissipation. The second difference is the signal originating in the grid-aligned case from the point where the incident shock meets the top boundary. This signal is a numerical artifact stemming from the mismatch between the discrete traveling wave profile of the computed shock and the analytic solution imposed as a boundary condition. The embedded boundary calculation uses a solid wall boundary condition at the top boundary, which does not lead to such an artifact. Otherwise, the solutions are very similar. In particular, the leading edge of the jet in the double Mach region intersects the boundary at right angles in both cases, as it should. This particular feature of the solution is very sensitive to the details of the solid wall boundary condition, even in the grid-aligned case, and is a discriminating test of the accuracy of the embedded boundary representation of the boundary conditions. Finally, we show a computation in three dimensions of a planar shock reflecting off an ellipsoidal object (Fig. 7) . This calculation demonstrates the ability of the three-dimensional algorithm to compute with strong discontinuities intersecting the irregular boundary.
Conclusions
We presented here a new Cartesian grid embedded boundary algorithm for systems of conservation laws, generalizing the unsplit second-order Godunov method described in [8, 17] . It is formally consistent, with a truncation error that vanishes as the mesh spacing goes to zero, leading to a method that is at least secondorder accurate in L 1 , and first-order accurate in L 1 . On standard strong-shock test problems, it is robust, leading to results that are nearly indistinguishable from corresponding grid-aligned calculations. Using the ideas in [14] , we have developed an adaptive mesh refinement version of this algorithm. With appropriate software support, the present algorithm can be used to compute solutions to a broad range of problems in complex geometries.
Conclusions
There are several ways in which the algorithmic ideas described here can be generalized. One is to revisit the hyperbolic free-boundary algorithms in [2, 6, 12, 15] . Such an approach could potentially lead to more accurate free-boundary methods: for the case of noncharacteristic boundaries, such as shocks and flame fronts, we would expect uniformly second-order accurate methods in the absence of secondary captured discontinuities. A second application would be to combine this algorithm with the finite-volume algorithms for elliptic and parabolic problems in [9, 11, 18] to solve incompressible or low-Mach number flow problems with irregular fixed or free boundaries, following the ideas in [1] .

{'paper_id': '15681734', 'title': 'A Cartesian grid embedded boundary method for hyperbolic conservation laws', 's2_url': 'https://api.semanticscholar.org/CorpusID:15681734', 'source': 'S2ORC'}