betaFeedback

WorksMathematics

An Efficient Implementation of Edge-Based Discretization without Forming Dual Control Volumes

Abstract

This paper shows that lumped directed-area vectors at edges and dual control volumes required to implement the edge-based discretization can be computed without explicitly defining the dual control volume around each node for triangular and tetrahedral grids. It is a simpler implementation because there is no need to form a dual control volume by connecting edge-midpoints, face centroids, and element centroids, and also reduces the time for computing lumped directed-area vectors for a given grid, especially for tetrahedral grids. The speed-up achieved by the proposed algorithm may not be large enough to greatly impact the overall simulation time, but the proposed algorithm is expected to serve as a major stepping stone towards extending the edge-based discretization to four dimensions and beyond (e.g., space-time simulations). Efficient algorithms for computing lumped directed-area vectors and dual volumes without forming dual volumes are presented, and their implementations are described and compared with traditional algorithms in terms of complexity as well as actual computing time for a given grid.

Introduction

The node-centered edge-based discretization method is widely used today in practical unstructured-grid computational fluid dynamics (CFD) solvers [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. It is a second-order accurate conservative discretization on arbitrary simplex-element (triangular or tetrahedral) grids with point-valued solutions stored at nodes [13] that can be implemented in an efficient edge loop, where only solutions and gradients at two end nodes are needed to compute a numerical flux at each edge. The method has also been shown to achieve third-order accuracy with a single numerical flux per edge on arbitrary triangular [14, 15, 16] and tetrahedral grids [17, 18] without high-order grids [17, 19] nor second derivatives [20]. Because of these special properties, it has been a subject for active CFD algorithm research towards automated CFD simulations with anisotropic viscous grid adaptation that can be performed efficiently with simplex-element grids [21, 22].

The edge-based discretization method constructs a residual over a medial dual control volume around each node, which is formed by connecting edge midpoints, geometric centroids of elements, and geometric centroids of faces (in three dimensions). To implement the edge-based discretization method, we need to compute volumes of the medial dual control volumes and lumped directed-area vectors at all edges for a given grid. The lumped directed-area vector is defined at each edge as the sum of the directed-area vectors of dual-volume faces attached to that edge. Typically, these two grid metrics are computed in a loop over elements, accumulating local contributions at nodes for dual volumes and at edges for lumped directed-area vectors. This is done by partially forming a median dual control volume within each element. Therefore, the construction of the median dual control volume is essential. In extending the edge-based discretization method to four and higher dimensions (e.g., space-time simulations), however, we encounter a difficulty that it is not straightforward, although perhaps possible, to construct a median dual control volume and compute such local contributions in a higher-dimensional element such as a pentatope in four dimensions. Although various discretization methods have been extended to four-dimensional grids [23, 24, 25, 26, 27], to the author’s knowledge at the time of writing this paper, the edge-based discretization has not been applied to four- or higher-dimensional simplex-element grids. It motivated the author to develop an alternative implementation that does not require the construction of median dual control volumes, which is the main subject of this paper. Such an implementation is expected not only to greatly simplify the coding of an edge-based solver for higher dimensions, but also simplify and potentially improve the efficiency of edge-based solvers in two and three dimensions. Leaving the former as important future work, we focus here on the basic idea, and derive and demonstrate efficient computations of lumped directed-area vectors and dual volumes without forming median dual control volumes for triangular and tetrahedral grids.

The main idea is to express directed-area vectors of dual faces entirely in terms of directed-area vectors of element faces. In doing so, we would have to introduce extra vectors on side faces, but they all cancel out after summing local contributions over a set of elements sharing an edge of interest, for all interior edges. As a result, we obtain an efficient formula for computing lumped directed-area vectors at interior edges without explicitly constructing median dual control volumes. At boundary edges, the lumped directed-area vectors need to be corrected with extra vectors, but this correction can be performed efficiently in a loop over boundary elements, again, without explicitly forming dual volumes and dual faces. Moreover, dual volumes can also be computed efficiently, without forming median dual control volumes, in a loop over edges using the lumped directed-area vectors. Therefore, there is no need at all to form the median dual control volumes. It is possible that some of the proposed implementations have already known to some researchers especially in early years when the edge-based discretization was discussed in relation to a continuous Galerkin finite-element discretization in the 1990s (see, e.g., Ref. [1]). However, such implementations might not have been considered particularly attractive partly because the grid metric computation takes only a fraction of an entire CFD simulation time in many cases and the construction of dual volumes is not difficult in two and three dimensions, and also because extensions to four and higher dimensions have not been received much attention. In this paper, we focus on two- and three-dimensional simplex-element grids. Extensions and applications to higher dimensions will be reported in a separate paper.

The paper is organized as follows. In Section 2, we describe the edge-based discretization. In Section 3, we begin with a traditional algorithm for computing lumped directed-area vectors based on median dual volumes and then introduce a more efficient algorithm that does not require median dual volumes. In Section 4, we discuss two approaches to computing median dual volumes without explicitly constructing median dual control volumes. In Section 5, we present numerical results comparing the efficiency of the new algorithms to traditional algorithms. In Section 6, we end the paper with concluding remarks.

Edge-Based Discretization

Consider a conservation law in the differential form:

∂u∂t+div⁡F=s,(1)\frac{\partial\mathbf{u}}{\partial t}+\operatorname{div}\mathcal{F}=\mathbf{s}, \tag*{(1)}

where tt is time, u\mathbf{u} is a vector of solution variables, F\mathcal{F} is a flux tensor, and s\mathbf{s} is a source (or forcing) term vector. The edge-based discretization method is a method of discretizing a conservation law (1) at a node in a conservative manner over a median dual control volume defined by connecting edge midpoints and geometric centroids of elements (and geometric centroids of element faces in three dimensions), with point-valued solutions stored at nodes. See Figure 1(a) and Figure 1(b). In this paper, we focus on simplex-element grids (triangular grids in two dimensions and tetrahedral grid in three dimensions): the edge-based discretization at a node jj is given by

Figure 1. Median dual control volumes in two and three dimensions, constructed with edge midpoints and geometric centroids of triangular elements in two dimensions, and edge midpoints, geometric centroids of tetrahedral elements, and geometric centroids of triangular faces in three dimensions. Note that the center node jj in the tetrahedral grid is located inside the median control volume and is not seen in the figure.

Vjdujdt+∑k∈{kj}Φjk∣njk∣=sjVj,(2)V_j\frac{d\mathbf{u}_j}{dt}+\sum_{k\in\{k_j\}}\Phi_{jk}\lvert\mathbf{n}_{jk}\rvert=s_jV_j, \tag*{(2)}

where VjV_j is the measure of the median dual control volume around the node jj, {kj}\{k_j\} is a set of edge-connected neighbor nodes of the node jj, Φjk\Phi_{jk} is a numerical flux, and njk\mathbf{n}_{jk} is the lumped directed-area vector, which is the sum of the directed-area vectors corresponding to the dual faces associated with all elements sharing the edge {j,k}\{j,k\}. In two dimensions, the lumped directed-area vector is defined as the sum of two directed-area vectors njkL\mathbf{n}_{jk}^{L} and njkR\mathbf{n}_{jk}^{R} as illustrated in Figure 1(a). In three dimensions, it is defined as the sum of the surface directed-area vectors of all the triangular dual faces associated with the edge {j,k}\{j,k\} as illustrated in Figure 1(b) (arrows are illustrated only for two of the eight relevant dual triangular faces). Note that each edge is oriented from one node to the other and the lumped directed-area vector is directed consistently. A simple way of defining the orientation is to define an edge as oriented from a node with a smaller node number to the other: njk\mathbf{n}_{jk} pointing from jj to kk, where j<kj < k. Throughout this paper, we assume that all edges are oriented in this way.

The numerical flux is computed at the edge midpoint, for example, by an upwind flux,

Φjk(uL,uR,n^jk)=12[f(uL)+f(uR)]−12∣∂f∂u∣(uR−uL),(3)\Phi_{jk}(\mathbf{u}_{L},\mathbf{u}_{R},\hat{\mathbf{n}}_{jk}) = \frac{1}{2}[\mathbf{f}(\mathbf{u}_{L})+\mathbf{f}(\mathbf{u}_{R})] - \frac{1}{2}\left|\frac{\partial\mathbf{f}}{\partial\mathbf{u}}\right|(\mathbf{u}_{R}-\mathbf{u}_{L}), \tag*{(3)}

where f=F⋅n^jk\mathbf{f}=\mathcal{F}\cdot\hat{\mathbf{n}}_{jk}, n^jk=njk/∣njk∣\hat{\mathbf{n}}_{jk}=\mathbf{n}_{jk}/|\mathbf{n}_{jk}|, and the subscripts LL and RR indicate values at the left and right sides of the edge midpoint. The left and right solution values, uL\mathbf{u}_{L} and uR\mathbf{u}_{R}, are reconstructed from the solutions stored at jj and kk, respectively, by an algorithm that is exact at least for linear functions: e.g., the U-MUSCL scheme [28, 29] and the V4 scheme [30]. The edge-based discretization described above is known to produce second-order accurate point-valued solutions at nodes on arbitrary simplex-element grids, and it can also produce third-order accurate point-valued solutions at nodes with minor modifications, as mentioned earlier.

The flux balance ∑k∈{kj}Φjk∣njk∣\sum_{k\in\{k_j\}}\Phi_{jk}|\mathbf{n}_{jk}| in the residual (2) can be computed by looping over edges: e=1,2,3,⋯ ,Nee=1,2,3,\cdots,N_e, where NeN_e is the number of edges in a grid. More precisely, we first initialize the residual array Res⁡j=0\operatorname{Res}_j=0 for all nodes, k=1,2,3,⋯ ,Nvk=1,2,3,\cdots,N_v, where NvN_v is the number of nodes, and then looping over edges, we compute the flux and distribute it to the left and right nodes at each edge ee:

Res⁡j=Res⁡j+Φjk,Res⁡k=Res⁡k−Φjk,(4)\operatorname{Res}_j=\operatorname{Res}_j+\Phi_{jk},\qquad\operatorname{Res}_k=\operatorname{Res}_k-\Phi_{jk}, \tag*{(4)}

where jj and kk are the nodes of the edge ee, which may be stored in a two-dimensional array, edge(e,1)=jedge(e,1)=j and edge(e,2)=kedge(e,2)=k, and njk\mathbf{n}_{jk} is defined as pointing from jj and kk. If boundary conditions are imposed weakly, the residuals at boundary nodes need to be closed with boundary flux contributions, and it can be performed by a loop over boundary elements (see Ref. [31]). If necessary, the time derivative and the source term can be added afterwards in a loop over nodes.

The edge-based discretization is efficient because it requires only a single numerical flux per edge even for third-order accuracy. This exceptional efficiency is due to the special property of the edge-based discretization defined with the lumped directed-area vectors and the median dual volume: it gives ∑k∈{kj}Φjk∣njk∣/Vj=(div⁡F)j\sum_{k\in\{k_j\}}\Phi_{jk}|\mathbf{n}_{jk}|/V_j=(\operatorname{div}\mathcal{F})_j exactly at a node jj on arbitrary simple-element grids for a linearly-varying (in space) flux F\mathcal{F}, and the same is true for a quadratically-varying flux in the case of the third-order edge-based discretization [20].

Note that only two grid metrics need to be precomputed for a given grid to implement the second- and third-order edge-based discretizations: the lumped directed-area vectors at edges and the volumes of median dual volumes at nodes. Our main interest here is in the computations of these quantities. In the next section, we begin with algorithms to compute the lumped directed-area vectors, and then discuss algorithms for computing the median dual volumes.

Efficient Computations of Lumped Directed-Area Vectors

In this section, we first review a traditional algorithm for computing the lumped directed-area vectors for triangular and tetrahedral grids, and describe a more efficient algorithm proposed in this paper. Then, we provide a complexity analysis and discuss the relative cost of the two algorithms.

A Traditional Algorithm for Computing Lumped Directed-Area Vectors

Triangular Grid

Typically, the lumped directed-area vectors are computed by summing dual-face contributions at edges in a loop over elements. For a triangular grid, at an edge {j,k}\{j,k\} in an element EE as shown in Figure 2(a), we form a dual face by connecting the edge midpoint (xm,ym)=(xj+xk2,yj+yk2)(x_m,y_m)=\left(\frac{x_j+x_k}{2},\frac{y_j+y_k}{2}\right) and the geometric centroid of the element (xE,yE)=(xj+xk+xr3,yj+yk+yr3)(x_E,y_E)=\left(\frac{x_j+x_k+x_r}{3},\frac{y_j+y_k+y_r}{3}\right), and compute the directed-area vector:

Figure 2. (a) Triangular element. (b) Tetrahedral element. Lumped directed-area vector contributions from an element EE to the edge {j,k}\{j,k\}.

njkE=(ΔymE,ΔxEm),(5)\mathbf{n}_{jk}^{E}=(\Delta y_{mE},\Delta x_{Em}), \tag*{(5)}

where ΔymE=ym−yE\Delta y_{mE}=y_m-y_E, ΔxEm=xE−xm\Delta x_{Em}=x_E-x_m, and we have assumed the edge is oriented from jj to kk (i.e., j<kj<k). Then, we add it to the lumped directed-area vector of the edge {j,k}\{j,k\}:

njk=njk+njkE.(6)\mathbf{n}_{jk}=\mathbf{n}_{jk}+\mathbf{n}_{jk}^{E}. \tag*{(6)}

Repeat the same for the other two edges, {j,r}\{j,r\} and {r,k}\{r,k\}, and move onto the next element. At the end of the process, we will have the lumped directed-area vectors at all edges.

Tetrahedral Grid

Similarly, for a tetrahedral grid, we typically compute the lumped directed-area vectors by summing dual-face contributions at edges in a loop over tetrahedra. In this case, we have two triangular dual faces in each element: {xm,xE,xL}\{x_m,x_E,x_L\} and {xm,xR,xE}\{x_m,x_R,x_E\} as illustrated in Figure 2(b). Here, mm is the midpoint of the edge {j,k}\{j,k\}, EE is the geometric centroid of the element EE, and LL and RR are the geometric centroids of the triangular faces {j,ℓ,k}\{j,\ell,k\} and {j,r,k}\{j,r,k\}, respectively:

(xm,ym,zm)=(xj+xk2,yj+yk2,zj+zk2),(7)(x_m,y_m,z_m)=\left(\frac{x_j+x_k}{2},\frac{y_j+y_k}{2},\frac{z_j+z_k}{2}\right), \tag*{(7)}
(xE,yE,zE)=(xj+xk+xℓ+xr4,yj+yk+yℓ+yr4,zj+zk+zℓ+zr4),(8)(x_E,y_E,z_E)=\left(\frac{x_j+x_k+x_\ell+x_r}{4},\frac{y_j+y_k+y_\ell+y_r}{4},\frac{z_j+z_k+z_\ell+z_r}{4}\right), \tag*{(8)}
(xL,yL,zL)=(xj+xℓ+xk3,yj+yℓ+yk3,zj+zℓ+zk3),(9)(x_L,y_L,z_L)=\left(\frac{x_j+x_\ell+x_k}{3},\frac{y_j+y_\ell+y_k}{3},\frac{z_j+z_\ell+z_k}{3}\right), \tag*{(9)}
(xR,yR,zR)=(xj+xr+xk3,yj+yr+yk3,zj+zr+zk3).(10)(x_R,y_R,z_R)=\left(\frac{x_j+x_r+x_k}{3},\frac{y_j+y_r+y_k}{3},\frac{z_j+z_r+z_k}{3}\right). \tag*{(10)}

Therefore, we add the directed-area vectors of the two triangular dual faces njkE,L\mathbf{n}_{jk}^{E,L} and njkE,R\mathbf{n}_{jk}^{E,R} to the lumped directed-area vector njk\mathbf{n}_{jk}:

njk=njk+njkE,L+njkE,R,(11)\mathbf{n}_{jk}=\mathbf{n}_{jk}+\mathbf{n}_{jk}^{E,L}+\mathbf{n}_{jk}^{E,R}, \tag*{(11)}

where

njkE,L=12(ΔyEmΔzLm−ΔzEmΔyLm, ΔzEmΔxLm−ΔxEmΔzLm, ΔxEmΔyLm−ΔyEmΔxLm),(12)\mathbf{n}_{jk}^{E,L}=\frac{1}{2}\left(\Delta y_{Em}\Delta z_{Lm}-\Delta z_{Em}\Delta y_{Lm},\ \Delta z_{Em}\Delta x_{Lm}-\Delta x_{Em}\Delta z_{Lm},\ \Delta x_{Em}\Delta y_{Lm}-\Delta y_{Em}\Delta x_{Lm}\right), \tag*{(12)}
njkE,R=12(ΔyRmΔzEm−ΔzRmΔyEm, ΔzRmΔxEm−ΔxRmΔzEm, ΔxRmΔyEm−ΔyRmΔxEm),(13)\mathbf{n}_{jk}^{E,R}=\frac{1}{2}\left(\Delta y_{Rm}\Delta z_{Em}-\Delta z_{Rm}\Delta y_{Em},\ \Delta z_{Rm}\Delta x_{Em}-\Delta x_{Rm}\Delta z_{Em},\ \Delta x_{Rm}\Delta y_{Em}-\Delta y_{Rm}\Delta x_{Em}\right), \tag*{(13)}

where again we have assumed j<kj<k, so that the edge is oriented from jj to kk. We repeat the same for the other five edges in the element EE, and move onto the next element. At the end of the process, we will have the lumped directed-area vectors at all edges. In the actual implementation, the factor 1/21/2 can be applied, after summing 2njkE,L2\mathbf{n}_{jk}^{E,L} and 2njkE,R2\mathbf{n}_{jk}^{E,R} over elements, in a subsequent loop over edges for efficiency.

An Efficient Algorithm for Computing Lumped Directed-Area Vectors

Triangular Grid

For a triangular grid, we derive a more efficient algorithm for computing the lumped directed-area vectors as follows. Consider the triangle E1E_1 having the edge {j,k}\{j,k\} as illustrated in Figure 3. By summing the outward directed-area vectors of the three faces of the triangle {m,r,k}\{m,r,k\}, we have

3(−njkE1)+njE1+12nr=0,(14)3\left(-\mathbf{n}_{jk}^{E_1}\right)+\mathbf{n}_{j}^{E_1}+\frac{1}{2}\mathbf{n}_{r}=0, \tag*{(14)}

where njE1=(yk−yr,xr−xk)\mathbf{n}_{j}^{E_1}=(y_k-y_r,x_r-x_k) is the outward directed-area vector of the face opposite to the node jj, nr=(yj−yk,xk−xj)\mathbf{n}_r=(y_j-y_k,x_k-x_j) is the outward directed-area vector of the face opposite to the node rr. It gives

njkE1=13[njE1+12nr].(15)\mathbf{n}_{jk}^{E_1}=\frac{1}{3}\left[\mathbf{n}_{j}^{E_1}+\frac{1}{2}\mathbf{n}_r\right]. \tag*{(15)}

Similarly, for the triangle E2E_2, we obtain

njkE2=13[njE2+12nℓ].(16)\mathbf{n}_{jk}^{E_2}=\frac{1}{3}\left[\mathbf{n}_{j}^{E_2}+\frac{1}{2}\mathbf{n}_{\ell}\right]. \tag*{(16)}

The lumped directed-area vector for the edge {j,k}\{j,k\} is then given by the sum of the two:

njk=13(njE1+njE2),(17)\mathbf{n}_{jk}=\frac{1}{3}\left(\mathbf{n}_{j}^{E_1}+\mathbf{n}_{j}^{E_2}\right), \tag*{(17)}

where nr\mathbf{n}_r and nℓ\mathbf{n}_{\ell} have been canceled out because nℓ=−nr\mathbf{n}_{\ell}=-\mathbf{n}_r. It can be formally expressed as

njk=13∑E∈{Ejk}njE,(18)\mathbf{n}_{jk}=\frac{1}{3}\sum_{E\in\{E_{jk}\}}\mathbf{n}_{j}^{E}, \tag*{(18)}

where {Ejk}\{E_{jk}\} denotes the set of elements sharing the edge {j,k}\{j,k\}.

The formula (3.14) can be implemented in a loop over elements: distribute the local contribution as

njk=njk+13njE(19)\mathbf{n}_{jk}=\mathbf{n}_{jk}+\frac{1}{3}\mathbf{n}_{j}^{E} \tag*{(19)}

if the edge {j,k}\{j,k\} is oriented from jj to kk (i.e., if j<kj<k), or

nkj=nkj+13nkE,(20)\mathbf{n}_{kj}=\mathbf{n}_{kj}+\frac{1}{3}\mathbf{n}_{k}^{E}, \tag*{(20)}

if the edge {j,k}\{j,k\} is oriented from kk to jj (i.e., if j>kj>k), perform the same for all three edges within an element, and move onto the next element.

If an edge is a boundary edge, e.g., the edge {j,k}\{j,k\} has only E1E_1 in Figure 3, then the term 12nr\frac{1}{2}\mathbf{n}_r in Equation (3.11) needs to be added. This boundary correction can be implemented easily by making a loop over boundary edges, B=1,2,3,⋯ ,NBB=1,2,3,\cdots,N_B, where NBN_B is the number of boundary edges and performing the following correction for each boundary edge BB with two ends nodes jj and kk (see Figure 4(a)),

Figure 3. Lumped directed-area vector contributions from two triangles to the edge {j,k}\{j,k\}.

Boundary edge visited in a boundary edge loop and boundary triangle visited in a boundary element loop

Figure 4. Boundary elements in two and three dimensions. Note that the directed-area vector nB\mathbf{n}_B of a boundary element is pointing outward from the interior of a domain in both figures.

njk=njk+16nB,(21)\mathbf{n}_{jk}=\mathbf{n}_{jk}+\frac{1}{6}\mathbf{n}_B, \tag*{(21)}

where nB\mathbf{n}_B is the outward directed-area vector of the boundary edge {j,k}\{j,k\}. Note that this boundary correction is independent of the orientation of the edge {j,k}\{j,k\}, i.e., we add the same 16nB\frac{1}{6}\mathbf{n}_B:

nkj=nkj+16nB,(22)\mathbf{n}_{kj}=\mathbf{n}_{kj}+\frac{1}{6}\mathbf{n}_B, \tag*{(22)}

even if the edge {j,k}\{j,k\} is actually oriented from kk to jj. To see this, we consider Figure 2(a) and assume the edge {j,k}\{j,k\} is a boundary edge. Summing over the outward directed-area vectors of the three faces of the triangle {m,r,k}\{m,r,k\} and also of the triangle {m,r,j}\{m,r,j\}, we obtain

3(−njkE)+njE+12nr=0,(23)3(-\mathbf{n}_{jk}^{E})+\mathbf{n}_{j}^{E}+\frac{1}{2}\mathbf{n}_{r}=\mathbf{0}, \tag*{(23)}
3(−nkjE)+nkE+12nr=0,(24)3(-\mathbf{n}_{kj}^{E})+\mathbf{n}_{k}^{E}+\frac{1}{2}\mathbf{n}_{r}=\mathbf{0}, \tag*{(24)}

respectively, where nkjE=−njkE\mathbf{n}_{kj}^{E}=-\mathbf{n}_{jk}^{E}, and find

njkE=13[njE+12nr],(25)\mathbf{n}_{jk}^{E}=\frac{1}{3}\left[\mathbf{n}_{j}^{E}+\frac{1}{2}\mathbf{n}_{r}\right], \tag*{(25)}
nkjE=13[nkE+12nr].(26)\mathbf{n}_{kj}^{E}=\frac{1}{3}\left[\mathbf{n}_{k}^{E}+\frac{1}{2}\mathbf{n}_{r}\right]. \tag*{(26)}

Now turn to Figure 4(a), and find nr=nB\mathbf{n}_{r}=\mathbf{n}_{B} and njk=njkE\mathbf{n}_{jk}=\mathbf{n}_{jk}^{E} or nkj=nkjE\mathbf{n}_{kj}=\mathbf{n}_{kj}^{E} (there is only one element for the edge). If the edge {j,k}\{j,k\} is oriented from jj to kk, we have njk\mathbf{n}_{jk}, the first term is taken into account in Equation (19), and the required correction is 16nB\frac{1}{6}\mathbf{n}_{B}. On the other hand, if the edge {j,k}\{j,k\} is oriented from kk to jj, we have nkj\mathbf{n}_{kj}, the first term is taken into account in Equation (20), and the required correction is the same 16nB\frac{1}{6}\mathbf{n}_{B}.

Tetrahedral Grid

For a tetrahedral grid, we consider local contributions to a node jj within an element EE. See Figure 2(b). By summing the outward directed-area vectors of the tetrahedron {m,r,ℓ,k}\{m,r,\ell,k\}, we have

6(−njkE,L−njkE,R)+njE+12nℓ+12nr=0,(27)6(-\mathbf{n}_{jk}^{E,L}-\mathbf{n}_{jk}^{E,R})+\mathbf{n}_{j}^{E}+\frac{1}{2}\mathbf{n}_{\ell}+\frac{1}{2}\mathbf{n}_{r}=\mathbf{0}, \tag*{(27)}

where njE\mathbf{n}^{E}_{j} is the outward directed-area vector of the triangular face opposite to the node jj in the element EE, and similarly for nℓE\mathbf{n}^{E}_{\ell} and nrE\mathbf{n}^{E}_{r}. It gives

njkE,L+njkE,R=16[njE+12(nℓE+nrE)],(28)\mathbf{n}^{E,L}_{jk}+\mathbf{n}^{E,R}_{jk}=\frac{1}{6}\left[\mathbf{n}^{E}_{j}+\frac{1}{2}\left(\mathbf{n}^{E}_{\ell}+\mathbf{n}^{E}_{r}\right)\right], \tag*{(28)}

which is the total local contribution to the lumped directed-area vector njk\mathbf{n}_{jk} (the edge {j,k}\{j,k\} is assumed to be oriented from jj to kk). Note that the dual face {m,R,E,L}\{m,R,E,L\} is planar, the geometric centroid EE is located halfway between mm and the midpoint of the edge {r,ℓ}\{r,\ell\}, and it leads to 6(−njkE,L−njkE,R)6(-\mathbf{n}^{E,L}_{jk}-\mathbf{n}^{E,R}_{jk}) as the outward directed-area vector of the triangle {m,r,ℓ}\{m,r,\ell\}. Summing the local contributions from all tetrahedra sharing the edge {j,k}\{j,k\}, we obtain

njk=∑E∈{Ejk}16[njE+12(nℓE+nrE)]=16∑E∈{Ejk}njE,(29)\mathbf{n}_{jk}=\sum_{E\in\{E_{jk}\}}\frac{1}{6}\left[\mathbf{n}^{E}_{j}+\frac{1}{2}\left(\mathbf{n}^{E}_{\ell}+\mathbf{n}^{E}_{r}\right)\right]=\frac{1}{6}\sum_{E\in\{E_{jk}\}}\mathbf{n}^{E}_{j}, \tag*{(29)}

where {Ejk}\{E_{jk}\} denotes the set of elements sharing the edge {j,k}\{j,k\}. Note that we consider interior edges here (i.e., there is always an adjacent tetrahedron to the face opposite to the node ℓ\ell and the same for the node rr), and therefore, the term 12(nℓE+nrE)\frac{1}{2}(\mathbf{n}^{E}_{\ell}+\mathbf{n}^{E}_{r}) has canceled out.

As in the triangular-grid case, we implement this formula in an element loop, adding 2njE2\mathbf{n}^{E}_{j} to njk\mathbf{n}_{jk} if the edge is oriented from jj to kk (i.e., if j<kj<k):

njk=njk+(ΔyrkΔzℓk−ΔzrkΔyℓk,ΔzrkΔxℓk−ΔxrkΔzℓk,ΔxrkΔyℓk−ΔyrkΔxℓk),(30)\mathbf{n}_{jk}=\mathbf{n}_{jk}+\left(\Delta y_{rk}\Delta z_{\ell k}-\Delta z_{rk}\Delta y_{\ell k},\Delta z_{rk}\Delta x_{\ell k}-\Delta x_{rk}\Delta z_{\ell k},\Delta x_{rk}\Delta y_{\ell k}-\Delta y_{rk}\Delta x_{\ell k}\right), \tag*{(30)}

or adding 2nkE2\mathbf{n}^{E}_{k} to nkj\mathbf{n}_{kj} if the edge is oriented from kk to jj (i.e., if j>kj>k):

nkj=nkj+(ΔyrjΔzℓj−ΔzrjΔyℓj,ΔzrjΔxℓj−ΔxrjΔzℓj,ΔxrjΔyℓj−ΔyrjΔxℓj),(31)\mathbf{n}_{kj}=\mathbf{n}_{kj}+\left(\Delta y_{rj}\Delta z_{\ell j}-\Delta z_{rj}\Delta y_{\ell j},\Delta z_{rj}\Delta x_{\ell j}-\Delta x_{rj}\Delta z_{\ell j},\Delta x_{rj}\Delta y_{\ell j}-\Delta y_{rj}\Delta x_{\ell j}\right), \tag*{(31)}

and doing the same for the other five edges in an element EE, followed by a subsequent loop over edges, where we apply the factor 1/121/12:

njk=112njk,(32)\mathbf{n}_{jk}=\frac{1}{12}\mathbf{n}_{jk}, \tag*{(32)}

where the factor 1/121/12 is the product of 1/61/6 in the formula (29) and 1/21/2 to cancel 22 of 2njE2\mathbf{n}^{E}_{j} or 2nkE2\mathbf{n}^{E}_{k}.

If the edge {j,k}\{j,k\} is a boundary edge, the term 12(nℓE+nrE)\frac{1}{2}(\mathbf{n}^{E}_{\ell}+\mathbf{n}^{E}_{r}) does not cancel out and needs to be added. Similarly to the triangular-grid case, we can add this contribution by looping over boundary elements, B=1,2,3,⋯ ,NBB=1,2,3,\cdots,N_{B}, where NBN_{B} is the number of boundary elements, and performing the following correction for each boundary triangle BB with nodes j,r,ℓj,r,\ell (see Figure 4(a)),

njr=njr+nB,nrℓ=nrℓ+nB,nℓj=nℓj+nB,(33)\mathbf{n}_{jr}=\mathbf{n}_{jr}+\mathbf{n}_{B},\quad\mathbf{n}_{r\ell}=\mathbf{n}_{r\ell}+\mathbf{n}_{B},\quad\mathbf{n}_{\ell j}=\mathbf{n}_{\ell j}+\mathbf{n}_{B}, \tag*{(33)}

where njr\mathbf{n}_{jr}, nrℓ\mathbf{n}_{r\ell}, and nℓj\mathbf{n}_{\ell j} are the lumped directed-area vectors of the edges {j,r}\{j,r\}, {k,ℓ}\{k,\ell\}, and {ℓ,j}\{\ell,j\}, respectively, and nB\mathbf{n}_{B} is the outward directed-area of the boundary face BB:

nB=12(ΔyrjΔzℓj−ΔzrjΔyℓj,ΔzrjΔxℓj−ΔxrjΔzℓj,ΔxrjΔyℓj−ΔyrjΔxℓj).(34)\mathbf{n}_{B}=\frac{1}{2}\left(\Delta y_{rj}\Delta z_{\ell j}-\Delta z_{rj}\Delta y_{\ell j},\Delta z_{rj}\Delta x_{\ell j}-\Delta x_{rj}\Delta z_{\ell j},\Delta x_{rj}\Delta y_{\ell j}-\Delta y_{rj}\Delta x_{\ell j}\right). \tag*{(34)}

Note, as in the two-dimensional case, that the boundary correction (3.29) is independent of the edge orientation, and thus njr\mathbf{n}_{jr} may actually be nrj\mathbf{n}_{rj} directed from rr to jj, for example.

General Form and Boundary Closure

The two- and three-dimensional formulas can be written in the following general form:

njk=2D(D+1)∑E∈{Ejk}njE,(35)\mathbf{n}_{jk}=\frac{2}{D(D+1)}\sum_{E\in\{E_{jk}\}}\mathbf{n}^{E}_{j}, \tag*{(35)}

where D=2D = 2 for a triangular grid and D=3D = 3 for a tetrahedral grid, with a boundary correction:

njk=njk+2D(D+1)12nB=njk+1D(D+1)nB,(36)\mathbf{n}_{jk}=\mathbf{n}_{jk}+\frac{2}{D(D+1)}\frac{1}{2}\mathbf{n}_{B}=\mathbf{n}_{jk}+\frac{1}{D(D+1)}\mathbf{n}_{B}, \tag*{(36)}

for all edges of a boundary element BB (1 edge in a triangular grid and 3 edges in a tetrahedral grid), for B=1,2,3,⋯ ,NBB = 1,2,3,\cdots,N_{B}, where nB\mathbf{n}_{B} is the outward directed-area vector of a boundary element BB. Here is an important observation: these formulas allow us to compute the lumped directed-area vector njk\mathbf{n}_{jk} without actually forming the dual faces: it only requires the directed-area vector of the face opposite to the node jj for each element E∈{Ejk}E \in\{E_{jk}\}, as illustrated in Figure 5, and outward directed-area vectors of each boundary element. Therefore, there is no need at all to form the median dual faces and control volumes (which requires edge midpoints, face centroids, element centroids) in the implementation of the edge-based discretization. This is the main reason that the proposed algorithm is more efficient and significantly simpler to implement than the traditional algorithm, especially for tetrahedral grids.

Figure 5. Directed-area vectors needed to compute njk\mathbf{n}_{jk} oriented from jj to kk.

It is always good to verify the implementation of an algorithm in a code. One simple verification for the lumped directed-area vectors is to confirm that the sum of the lumped directed-area vectors is zero at every node, which can be performed as follows: set aj=0\mathbf{a}_{j}=0 at all nodes (j=1,2,3,⋯ ,Nvj=1,2,3,\cdots,N_{v}), and accumulate the lumped directed-area vectors in a loop over edges,

aj=aj+njk,ak=ak−njk,(37)\mathbf{a}_{j}=\mathbf{a}_{j}+\mathbf{n}_{jk},\qquad\mathbf{a}_{k}=\mathbf{a}_{k}-\mathbf{n}_{jk}, \tag*{(37)}

where the edge {j,k}\{j,k\} is assumed to be oriented from jj to kk. At the end of the process, we must have aj=0\mathbf{a}_{j}=0 at all interior nodes. At boundary nodes, aj≠0\mathbf{a}_{j}\ne0 at this point, but we must have zero sums at boundary nodes as well in order to correctly discretize a conservation law at boundary nodes: the flux balance must be zero if the flux is constant. The edge-based discretization (2) actually needs to be closed at boundary elements with an accuracy-preserving boundary flux quadrature formula as discussed in Ref. [31] for second-order accuracy and Ref. [32] for third-order accuracy. For verification of njk\mathbf{n}_{jk}, it suffices to add outward directed-area vectors corresponding to dual faces at boundary elements, each of which is precisely 1/D1/D of the outward directed-area vector of a boundary element: 12nB=12(yj−yk,xk−xj)\frac{1}{2}\mathbf{n}_{B}=\frac{1}{2}(y_{j}-y_{k},x_{k}-x_{j}) as illustrated in Figure 6(a) and 13nB=16(ΔyrjΔzℓj−ΔzrjΔyℓj,ΔxrjΔzℓj−ΔzrjΔxℓj,ΔxrjΔyℓj−ΔyrjΔxℓj)\frac{1}{3}\mathbf{n}_{B}=\frac{1}{6}(\Delta y_{rj}\Delta z_{\ell j}-\Delta z_{rj}\Delta y_{\ell j},\Delta x_{rj}\Delta z_{\ell j}-\Delta z_{rj}\Delta x_{\ell j},\Delta x_{rj}\Delta y_{\ell j}-\Delta y_{rj}\Delta x_{\ell j}) as illustrated in Figure 6(b). Therefore, for each node iBi_{B} of a boundary element BB, B=1,2,3,⋯ ,NBB=1,2,3,\cdots,N_{B}, we perform the following:

Figure 6. Outward directed-area vectors at boundary elements in two and three dimensions. In both cases, nB\mathbf{n}_B is pointing outward from the interior domain. The shaded area is the median dual volume around the node jj in the triangular grid (left); the shaded area is a boundary face of the median dual volume around the node jj in the tetrahedral grid case (right).

aiB=aiB+1DnB,(38)\mathbf{a}_{i_{B}}=\mathbf{a}_{i_{B}}+\frac{1}{D}\mathbf{n}_{B}, \tag*{(38)}

where iB=ji_B=j and kk in two dimensions (see Figure 6(a)) and iB=ji_B=j, rr, and ℓ\ell in three dimensions (see Figure 6(b)). At the end of this loop, we must have aj=0\mathbf{a}_j=\mathbf{0} at all boundary nodes.

Complexity and Discussion

It is not simple to precisely measure the relative efficiency of the two algorithms as it depends on various factors, e.g., memory access, compilers, code optimizations, and architectures. However, it is often helpful to provide a complexity analysis based on the number of additions and multiplications required in each algorithm and compare them, ignoring all other factors (subtractions are taken as additions, and divisions of constant values are assumed to be implemented as multiplications). For simplicity, we ignore boundary effects (i.e., assuming large grids) and focus on interior edges and nodes. Later, we will present comparison of actual computing times and show that the actual speed-up factors are not too far from those indicated by the complexity analysis.

Triangular Grid

For a triangular grid, we first consider the traditional algorithm described in § 3.1.1. Here, we first need 2 additions and 2 multiplications for computing the edge midpoint coordinates. Then, it takes 2 additions for computing njkE\mathbf{n}_{jk}^{E} and 2 additions in adding the dual-face contribution njkE\mathbf{n}_{jk}^{E} to njk\mathbf{n}_{jk} for an edge of each triangle. The same needs to be done for 3 edges in an element, leading to the total of 18 additions and 6 multiplications. We also need to compute the geometric centroid of an element: 4 additions and 2 multiplications (division by 3) per element. Hence, in total, it requires 22 additions and 8 multiplications per element. For a given grid, therefore, it will require 22NE22N_E additions and 8NE8N_E multiplications, where NEN_E is the total number of triangles.

On the other hand, the proposed algorithm described in § 3.2.1 requires 2 additions and 2 multiplications for computing njE/3\mathbf{n}_j^E/3 and 2 additions for adding it to njk\mathbf{n}_{jk}. Assuming we compute njE\mathbf{n}_j^E for each edge of a triangular element, we find it will require 12 additions and 6 multiplications per element, resulting in 12NE12N_E additions and 6NE6N_E multiplications in total, which is less than 22NE22N_E additions and 8NE8N_E multiplications of the typical algorithm.

Results are summarized in Table 1. It indicates that the proposed algorithm can be more efficient, although only slightly, by a factor 8/6≈1.38/6 \approx1.3 at best in two dimensions if the cost of multiplications is dominant.

Traditional algorithmProposed algorithm
AdditionsMultiplicationsAdditionsMultiplications
Triangular grid22NE22N_E8NE8N_E12NE12N_E6NE6N_E
Tetrahedral grid205NE205N_E129.5NE129.5N_E72NE72N_E39.5NE39.5N_E

Table 1. Complexity comparison for lumped directed-area vector computations in a given grid by traditional and proposed algorithms. NEN_E is the total number of triangular/tetrahedral elements in a given grid.

Remark: Note that the factor 1/31/3 may be applied afterwards in an edge loop after summing njE\mathbf{n}_j^E as in the tetrahedral case, but it does not reduce the total cost because the total of 2Ne2N_e multiplications (NeN_e is the number of edges in a grid) is roughly equal to 6NE6N_E multiplications because we have Ne≈3NEN_e \approx3N_E in a triangular grid.

Tetrahedral Grid

We first consider the traditional algorithm described in § 3.1.2. This particular implementation requires, at each edge of an element within a loop over elements, 3 additions and 3 multiplications for computing (xm,ym,zm)(x_m,y_m,z_m), 6 additions and 3 multiplications for computing (xL,yL,zL)(x_L,y_L,z_L), 6 additions and 3 multiplications for computing (xR,yR,zR)(x_R,y_R,z_R), 6 additions and 6 multiplications for computing njkE,Ln_{jk}^{E,L} (the factor 1/2 ignored here), 6 additions and 6 multiplications for computing njkE,Rn_{jk}^{E,R} (the factor 1/2 ignored here), 3 additions for adding them, and 3 additions for adding the result to njkn_{jk}. They add up to 33 additions and 21 multiplications. All these are required for the total of 6 edges in each element, resulting in 196 additions and 126 multiplications. For each element, we also need to compute the element centroid (xE,yE,zE)(x_E,y_E,z_E), which requires 9 additions and 3 multiplications. Therefore, at each element, it requires 205 additions and 129 multiplications. Finally, in total for a tetrahedral grid, it will require 205NE205N_E additions and 129NE+3Ne129N_E+3N_e multiplications, where 3Ne3N_e multiplications is the cost of applying the factor 1/2 in an edge loop, and NEN_E and NeN_e are the numbers of tetrahedra and edges in a grid, respectively. For a tetrahedral grid, we typically have Ne≈7NvN_e \approx7N_v and NE≈6NvN_E \approx6N_v, where NvN_v is the total number of nodes in a grid, and therefore Ne≈7/6NEN_e \approx7/6N_E. Hence, we have 126NE+3Ne=129.5NE126N_E+3N_e=129.5N_E multiplications.

On the other hand, the proposed algorithm described in § 3.2.2 will require, at each edge of an element within a loop over elements, 9 additions and 6 multiplications for computing 2njE2n_j^E, and 3 additions for adding 2njE2n_j^E to njkn_{jk} (see Equation (30)). Assuming that we compute njEn_j^E for each edge of a tetrahedral element (6 edges in total), we find it will require 72 additions and 36 multiplications per element. Therefore, in total, it will cost 72NE72N_E additions and 36NE36N_E multiplications, with 3Ne≈3.5NE3N_e \approx3.5N_E multiplications for applying the factor 1/12 in the subsequent edge loop as in Equation (32). This algorithm is significantly cheaper than the traditional algorithm of 205NE205N_E additions and 129.5NE129.5N_E multiplications.

Results are summarized in Table 1. It indicates approximately a factor 3 speed-up; actual numerical results show a factor between 2 and 3.

Remark: The complexity could be reduced further. In three dimensions, the vector njkEn_{jk}^{E} computed for the edge {j,k}\{j,k\} can be used also for {j,ℓ}\{j,\ell\} and {j,r}\{j,r\} if these two edges are oriented from jj to ℓ\ell and rr, respectively. If in addition, the edges {k,ℓ},{k,r}\{k,\ell\},\{k,r\} are oriented from kk to ℓ\ell and rr, respectively, we can use njkEn_{jk}^{E} for both. Then, we are left with the edge {ℓ,r}\{\ell,r\}, which will require nℓEn_{\ell}^{E} or nrEn_{r}^{E}. Hence, it will require three directed-area vectors per element while the estimate in Table 1 assumes one directed-area computation per edge, thus six in total per element. It is difficult to estimate the true cost accurately because it depends on the edge orientations (it may require extra if-statements or extra memory). This implementation is not considered in this paper.

Computations of Dual Volumes

There are two approaches to computing dual volumes. One is based on a loop over edges and the other is based on a loop over elements. These algorithms are already known, and both do not require the construction of median dual control volumes. Here, we provide their derivations and a complexity analysis for the sake of completeness.

Edge-Based Algorithms

An edge-based formula for a dual volume computation can be derived by the divergence theorem. Consider the integration of the divergence of x\mathbf{x} over a median dual volume around a node jj in a triangular or tetrahedral grid, which can be evaluated as the surface integral:

∫Vjdiv⁡x=∮∂Vjx⋅n^ dS,(39)\int_{V_j} \operatorname{div}\mathbf{x} = \oint_{\partial V_j} \mathbf{x} \cdot\hat{\mathbf{n}}\,dS, \tag*{(39)}

where n^\hat{\mathbf{n}} denotes the unit outward normal vector of the infinitesimal surface area dSdS, or

∫Vjdiv⁡x=∮∂Vj(x−xj)⋅n^ dS,(40)\int_{V_j} \operatorname{div}\mathbf{x} = \oint_{\partial V_j} (\mathbf{x}-\mathbf{x}_j) \cdot\hat{\mathbf{n}}\,dS, \tag*{(40)}

since ∮∂Vjxj⋅n^ dS=xj⋅∮∂Vjn^ dS=0\oint_{\partial V_j}\mathbf{x}_j \cdot\hat{\mathbf{n}}\,dS = \mathbf{x}_j \cdot\oint_{\partial V_j}\hat{\mathbf{n}}\,dS = 0. Then, the left hand side of Equation (40) simplifies to DVjDV_j (e.g., div⁡x=∂xx+∂yy+∂zz=1+1+1=3\operatorname{div}\mathbf{x} = \partial_x x + \partial_y y + \partial_z z = 1 + 1 + 1 = 3 in three dimensions) and the right hand side can be evaluated exactly by the edge-based discretization:

DVj=∑k∈{kj}Φjk∣njk∣,(41)DV_j = \sum_{k\in\{k_j\}} \Phi_{jk}|\mathbf{n}_{jk}|, \tag*{(41)}

where the numerical flux Φjk\Phi_{jk} is given by the averaged flux,

Φjk=(xj−xj)+(xk−xj)2⋅n^jk=xk−xj2⋅n^jk.(42)\Phi_{jk} = \frac{(\mathbf{x}_j-\mathbf{x}_j)+(\mathbf{x}_k-\mathbf{x}_j)}{2}\cdot\hat{\mathbf{n}}_{jk} = \frac{\mathbf{x}_k-\mathbf{x}_j}{2}\cdot\hat{\mathbf{n}}_{jk}. \tag*{(42)}

Or we can write simply,

DVj=∑k∈{kj}xk−xj2⋅njk,(43)DV_j = \sum_{k\in\{k_j\}} \frac{\mathbf{x}_k-\mathbf{x}_j}{2}\cdot\mathbf{n}_{jk}, \tag*{(43)}

which gives

Vj=12D∑k∈{kj}(xk−xj)⋅njk.(44)V_j = \frac{1}{2D}\sum_{k\in\{k_j\}}(\mathbf{x}_k-\mathbf{x}_j)\cdot\mathbf{n}_{jk}. \tag*{(44)}

This can be implemented in a loop over edges, distributing the dot product to the two end nodes at each edge,

Vj=Vj+(xk−xj)⋅njk,Vk=Vk+(xk−xj)⋅njk,(45)V_j = V_j + (\mathbf{x}_k-\mathbf{x}_j)\cdot\mathbf{n}_{jk}, \qquad V_k = V_k + (\mathbf{x}_k-\mathbf{x}_j)\cdot\mathbf{n}_{jk}, \tag*{(45)}

and then apply the factor 1/(2D)1/(2D) in a subsequent loop over nodes:

Vj=12DVj,for j=1,2,3,⋯ ,Nv.(46)V_j = \frac{1}{2D}V_j,\quad\text{for }j=1,2,3,\cdots,N_v. \tag*{(46)}

Element-Based Algorithms

Alternatively, we can compute dual volumes in a loop over elements. In fact, the dual volume contribution from a simplex element to a node is exactly 1/(D+1)1/(D+1) of the element volume for D=2D=2 and D=3D=3. For a triangular element as illustrated in Figure 7(a), we apply the divergence theorem to the dual volume V1EV_1^E (shaded area) contributing to the node 1:

Figure 7. (a) Triangular element. (b) Tetrahedral element. Figure 7: Median dual volume contributions to a node 1 within an element.

∫V1Ediv⁡x=∮∂V1E(x−x1)⋅n^ dS.(47)\int_{V_1^E}\operatorname{div}\mathbf{x} = \oint_{\partial V_1^E}(\mathbf{x}-\mathbf{x}_1)\cdot\hat{\mathbf{n}}\,dS. \tag*{(47)}

The left hand side is 2V1E2V_1^E because div⁡x=∂xx+∂yy=1+1=2\operatorname{div}\mathbf{x} = \partial_x x + \partial_y y = 1 + 1 = 2, and the surface integral can be evaluated exactly by using the edge-based quadrature formula derived in Appendix B of Ref. [31]:

2V1E=(x1−x1)+(x2−x1)2⋅n12+(x1−x1)+(x3−x1)2⋅n13+56(x1−x1)+16(x3−x1)⋅nL+56(x1−x1)+16(x2−x1)⋅nR,(48)2V_1^E = \frac{(\mathbf{x}_1-\mathbf{x}_1)+(\mathbf{x}_2-\mathbf{x}_1)}{2}\cdot\mathbf{n}_{12}+\frac{(\mathbf{x}_1-\mathbf{x}_1)+(\mathbf{x}_3-\mathbf{x}_1)}{2}\cdot\mathbf{n}_{13} +\frac{5}{6}(\mathbf{x}_1-\mathbf{x}_1)+\frac{1}{6}(\mathbf{x}_3-\mathbf{x}_1)\cdot\mathbf{n}_{L}+\frac{5}{6}(\mathbf{x}_1-\mathbf{x}_1)+\frac{1}{6}(\mathbf{x}_2-\mathbf{x}_1)\cdot\mathbf{n}_{R}, \tag*{(48)}

where nL=n2/2\mathbf{n}_{L}=\mathbf{n}_2/2 and nR=n3/2\mathbf{n}_{R}=\mathbf{n}_3/2. But the last two terms vanish by orthogonality, and we are left with

2V1E=(x2−x1)2⋅n12+(x3−x1)2⋅n13.(49)2V_1^E=\frac{(\mathbf{x}_2-\mathbf{x}_1)}{2}\cdot\mathbf{n}_{12}+\frac{(\mathbf{x}_3-\mathbf{x}_1)}{2}\cdot\mathbf{n}_{13}. \tag*{(49)}

Furthermore, by the formula (15), we have

n12=13[n1E+12n3E],n13=13[n1E+12n2E],(50)\mathbf{n}_{12}=\frac{1}{3}\left[\mathbf{n}_1^E+\frac{1}{2}\mathbf{n}_3^E\right],\qquad\mathbf{n}_{13}=\frac{1}{3}\left[\mathbf{n}_1^E+\frac{1}{2}\mathbf{n}_2^E\right], \tag*{(50)}

and substitute these into Equation (49),

2V1E=(x2−x1)6⋅n1E+(x3−x1)6⋅n1E=13VE+13VE,(51)\begin{aligned} 2V_1^E&=\frac{(\mathbf{x}_2-\mathbf{x}_1)}{6}\cdot\mathbf{n}_1^E+\frac{(\mathbf{x}_3-\mathbf{x}_1)}{6}\cdot\mathbf{n}_1^E\\ &=\frac{1}{3}V_E+\frac{1}{3}V_E, \tag*{(51)} \end{aligned}

where we have used the fact (x2−x1)⋅n3=(x3−x1)⋅n2=0(\mathbf{x}_2-\mathbf{x}_1)\cdot\mathbf{n}_3=(\mathbf{x}_3-\mathbf{x}_1)\cdot\mathbf{n}_2=0, and VE=(x2−x1)2⋅n1E=(x3−x1)2⋅n1EV_E=\frac{(\mathbf{x}_2-\mathbf{x}_1)}{2}\cdot\mathbf{n}_1^E=\frac{(\mathbf{x}_3-\mathbf{x}_1)}{2}\cdot\mathbf{n}_1^E is the volume (area) of the element EE, thus leading to

V1E=13VE.(52)V_1^E=\frac{1}{3}V_E. \tag*{(52)}

Similarly, for a tetrahedral element as illustrated in Figure 7(b), we apply the divergence theorem to the medial dual volume V1EV_1^E (shaded volume):

∫V1Ediv⁡x=∮∂V1E(x−x1)⋅n^ dS.(53)\int_{V_1^E} \operatorname{div}\mathbf{x} = \oint_{\partial V_1^E} (\mathbf{x}-\mathbf{x}_1)\cdot\hat{\mathbf{n}}\,\mathrm{d}S. \tag*{(53)}

The left hand side is 3V1E3V_1^E because div⁡x=∂xx+∂yy+∂zz=1+1+1=3\operatorname{div}\mathbf{x}=\partial_x x+\partial_y y+\partial_z z=1+1+1=3, and the surface integral can be evaluated exactly by using the edge-based quadrature formula derived in Appendix B of Ref. [31]:

3V1E=(x1−x1)+(x2−x1)2⋅n12+(x1−x1)+(x3−x1)2⋅n13+(x1−x1)+(x4−x1)2⋅n14+[68(x1−x1)+18(x3−x1)+18(x4−x1)]⋅nL+[68(x1−x1)+18(x4−x1)+18(x2−x1)]⋅nR+[68(x1−x1)+18(x2−x1)+18(x3−x1)]⋅nB,(54)\begin{aligned} 3V_1^E={}&\frac{(\mathbf{x}_1-\mathbf{x}_1)+(\mathbf{x}_2-\mathbf{x}_1)}{2}\cdot\mathbf{n}_{12} +\frac{(\mathbf{x}_1-\mathbf{x}_1)+(\mathbf{x}_3-\mathbf{x}_1)}{2}\cdot\mathbf{n}_{13} +\frac{(\mathbf{x}_1-\mathbf{x}_1)+(\mathbf{x}_4-\mathbf{x}_1)}{2}\cdot\mathbf{n}_{14}\\ &+\left[\frac{6}{8}(\mathbf{x}_1-\mathbf{x}_1)+\frac{1}{8}(\mathbf{x}_3-\mathbf{x}_1)+\frac{1}{8}(\mathbf{x}_4-\mathbf{x}_1)\right]\cdot\mathbf{n}_{L} +\left[\frac{6}{8}(\mathbf{x}_1-\mathbf{x}_1)+\frac{1}{8}(\mathbf{x}_4-\mathbf{x}_1)+\frac{1}{8}(\mathbf{x}_2-\mathbf{x}_1)\right]\cdot\mathbf{n}_{R}\\ &+\left[\frac{6}{8}(\mathbf{x}_1-\mathbf{x}_1)+\frac{1}{8}(\mathbf{x}_2-\mathbf{x}_1)+\frac{1}{8}(\mathbf{x}_3-\mathbf{x}_1)\right]\cdot\mathbf{n}_{B}, \tag*{(54)} \end{aligned}

but the last three terms vanish by orthogonality and we are left with

3V1E=x2−x12⋅n12+x3−x12⋅n13+x4−x12⋅n14.(55)3V_1^E=\frac{\mathbf{x}_2-\mathbf{x}_1}{2}\cdot\mathbf{n}_{12} +\frac{\mathbf{x}_3-\mathbf{x}_1}{2}\cdot\mathbf{n}_{13} +\frac{\mathbf{x}_4-\mathbf{x}_1}{2}\cdot\mathbf{n}_{14}. \tag*{(55)}

By the formula (3.24), we have

n12=16[n1E+12(nR+nB)],n13=16[n1E+12(nB+nL)],n14=16[n1E+12(nR+nL)].(56)\mathbf{n}_{12}=\frac{1}{6}\left[\mathbf{n}_1^E+\frac{1}{2}(\mathbf{n}_{R}+\mathbf{n}_{B})\right],\qquad \mathbf{n}_{13}=\frac{1}{6}\left[\mathbf{n}_1^E+\frac{1}{2}(\mathbf{n}_{B}+\mathbf{n}_{L})\right],\qquad \mathbf{n}_{14}=\frac{1}{6}\left[\mathbf{n}_1^E+\frac{1}{2}(\mathbf{n}_{R}+\mathbf{n}_{L})\right]. \tag*{(56)}

Substituting them in Equation (4.17), we obtain

3V1E=x2−x112⋅n1E+x3−x112⋅n1E+x4−x112⋅n1E,(57)3V_1^E=\frac{\mathbf{x}_2-\mathbf{x}_1}{12}\cdot\mathbf{n}_1^E +\frac{\mathbf{x}_3-\mathbf{x}_1}{12}\cdot\mathbf{n}_1^E +\frac{\mathbf{x}_4-\mathbf{x}_1}{12}\cdot\mathbf{n}_1^E, \tag*{(57)}

where all the terms involving nL\mathbf{n}_{L}, nR\mathbf{n}_{R}, and nB\mathbf{n}_{B} have vanished by orthogonality. It gives

3V1E=14VE+14VE+14VE,(58)3V_1^E=\frac{1}{4}V_E+\frac{1}{4}V_E+\frac{1}{4}V_E, \tag*{(58)}

where VE=(xi−x1)3⋅n1EV_E=\frac{(\mathbf{x}_i-\mathbf{x}_1)}{3}\cdot\mathbf{n}_1^E, i=1,2,3i=1,2,3, is the volume of the element EE, and thus

V1E=14VE.(59)V_1^E=\frac{1}{4}V_E. \tag*{(59)}

Therefore, the dual volume contribution from an element to a node is exactly 1/(D+1)1/(D+1) of the element volume, where D=2D=2 for a triangular grid and D=3D=3 for a tetrahedral grid. Then, we can compute the dual volumes as follows: within a loop over elements, distribute the contribution to a node ii of an element EE as

Vi=Vi+1D+1VE,i∈{iE},for E=1,2,3,…,NE,(60)V_i=V_i+\frac{1}{D+1}V_E,\qquad i\in\{i_E\},\quad\text{for }E=1,2,3,\ldots,N_E, \tag*{(60)}

where {iE}\{i_E\} is a set of nodes of an element EE (3 nodes for a triangle and 4 nodes for a tetrahedron), and VEV_E is the volume of the element EE (area in two dimensions). Or, in order to reduce the number of multiplications, we may apply the factor 1D+1\frac{1}{D+1} in a separate loop over nodes after accumulating VEV_E: accumulate local contributions,

Vi=Vi+VE,i∈{iE},for E=1,2,3,…,NE,(61)V_i=V_i+V_E,\qquad i\in\{i_E\},\quad\text{for }E=1,2,3,\ldots,N_E, \tag*{(61)}

for all elements, and then apply the factor 1D+1\frac{1}{D+1} in a loop over nodes,

Vj=1D+1Vj,for j=1,2,3,…,Nv.(62)V_j=\frac{1}{D+1}V_j,\qquad\text{for }j=1,2,3,\ldots,N_v. \tag*{(62)}

Complexity and Discussion

As before, we provide a complexity analysis based on the number of additions and multiplications required in each algorithm and compare them, ignoring all other factors. The element-based algorithm in § 4.2 requires 5 additions and 2 multiplications for computing VEV_E (1 cross product) in two dimensions, and 12 additions and 9 multiplications in three dimensions. Also, one multiplication per node, thus NvN_v multiplications in total; or approximately 0.5NE0.5N_E multiplications in two dimensions since NE≈2NvN_E \approx2N_v in a triangular grid, and 0.167NE0.167N_E (or roughly 0.2NE0.2N_E) multiplications in three dimensions since NE≈6NvN_E \approx6N_v in a tetrahedral grid. Therefore, for a given grid, it requires the total of 5NE5N_E additions and 2.5NE2.5N_E multiplications in two dimensions, and 12NE12N_E additions and 9.2NE9.2N_E multiplications in three dimensions.

On the other hand, the edge-based algorithm in § 4.1 requires 3 additions and 2 multiplications per edge in two dimensions, and 5 additions and 3 multiplications per edge in three dimensions. Also, one multiplication per node, thus NvN_v multiplications in total. Therefore, it requires the total of 3Ne3N_e additions and 2Ne+Nv≈2Ne+0.5NE2N_e+N_v \approx2N_e+0.5N_E multiplications in two dimensions, and 5Ne5N_e additions and 3Ne+Nv≈2Ne+0.2NE3N_e+N_v \approx2N_e+0.2N_E multiplications in three dimensions. Since we have Ne≈3/2NEN_e \approx3/2N_E in two dimensions and Ne≈7/6NEN_e \approx7/6N_E for large grids, these estimates can be expressed approximately as 4.5NE4.5N_E additions and 3.5NE3.5N_E multiplications in two dimensions, and 5.8NE5.8N_E additions and 3.7NE3.7N_E multiplications in three dimensions.

The results are summarized in Table 2. As can be seen, the edge-based algorithm is not necessarily more efficient than the element-based algorithm in two dimensions. However, the edge-based algorithm is expected to be more efficient than the element-based algorithm in three dimensions, at least by a factor of 2.

Element-based algorithmEdge-based algorithm
AdditionsMultiplicationsAdditionsMultiplications
Triangular grid5NE5N_E2.5NE2.5N_E4.5NE4.5N_E3.5NE3.5N_E
Tetrahedral grid12NE12N_E9.2NE9.2N_E5.8NE5.8N_E3.7NE3.7N_E

Table 2. Complexity comparison for median dual volume computations in a given grid by element-based and edge-based algorithms. NEN_E is the total number of triangular/tetrahedral elements in the grid.

One way to verify the dual volume data is to compute the sum of the dual volumes at all nodes and confirm that it is equal to the volume of an entire domain covered by a grid. This is typically performed by using a grid in a unit square in two dimensions and a unit cube in three dimensions: the sum of the dual volumes must be 1.

Note that there is no need to form median dual control volumes in both algorithms. As the lumped directed-area vectors can be computed also without forming the median dual control volumes, there will be no need at all to form median dual control volumes in a code. It greatly simplifies the implementation of the edge-based discretization.

Results

We implemented the proposed algorithms in two- and three-dimensional edge-based solvers, which are both serial codes, and verified their implementations by performing the verification tests mentioned earlier (results are not shown). Then, we tested the proposed algorithms by computing the lumped directed-area vectors and the dual volumes for a triangular grid in a unit square domain with 65,536 nodes and 130,050 triangles, and for a tetrahedral grid in a unit cube domain with 16,974,593 nodes and 100,669,296 tetrahedra. CPU times are measured in seconds for each computation, the computations are repeated 10 times, and CPU times are averaged over 10 executions. Results are summarized in Table 3.

Conventional algorithmProposed algorithm
njk\mathbf{n}_{jk}VjV_jnjk\mathbf{n}_{jk}VjV_j
Triangular grid4.09e-03 (1.12)7.25e-04 (0.81)3.85e-039.56e-04
Tetrahedral grid29.22 (2.16)2.38 (1.89)13.51.26

Table 3. CPU time (seconds) required to compute the lumped directed-area vectors, njk\mathbf{n}_{jk}, and median dual volumes, VjV_j, for a triangular grid with 65,536 nodes and 130,050 triangles and a tetrahedral grid with 16,974,593 nodes and 100,663,296 tetrahedra. Numbers in parentheses indicate the ratio to the corresponding time in the traditional algorithm (e.g., 2.16 = 29.22/13.5). CPU times are averaged over 10 executions.

For a triangular grid, the proposed algorithm is only slightly faster than the traditional algorithm by a factor 1.12, and actually the edge-based dual volume computation took longer than the element-based computation. These results are not far from the complexity analysis results, which roughly imply a factor 1.3 or less for the computation of njkn_{jk} (see Table 1) and the edge-based algorithm is expected to be slightly more expensive than the element-based algorithm for the computation of VjV_j (see Table 2). Therefore, as far as the dual volume computation is concerned, the element-based algorithm may be preferred for a triangular grid.

On the other hand, for a tetrahedral grid, the proposed algorithm provides a factor 2.16 speed-up for the computation of njk\mathbf{n}_{jk} and 1.89 for the computation of VjV_j. Again, these results are not far from the complexity analysis results, which roughly indicate a factor 3 for the computation of njk\mathbf{n}_{jk} (see Table 1) and 2 for the computation of VjV_j (see Table 2). For time-accurate simulations with deforming grids, the grid metrics need to be recomputed at every physical time step, and the proposed algorithm can provide a significant speed-up. For example, over 1,000 time steps, the traditional algorithm would take 29.22×1,000=29,22029.22 \times1{,}000 = 29{,}220 seconds (≈8\approx8 hours) for the grid metric computation, and the proposed algorithm would take 13.5×1,000=13,50013.5 \times1{,}000 = 13{,}500 seconds (≈3.75\approx3.75 hours).

There can be various factors contributing to the difference between the complexity analysis results and actual CPU time measurements. Especially, these computations are not so heavy and thus, for example, even an integer increment of a loop may have a significant contribution to the total CPU time. Further detailed studies on computing time is beyond the scope of this paper. The objective of this paper is to show that these computations can be performed without forming median dual control volumes and the proposed algorithm for the directed-area vectors is simpler and more efficient than a traditional algorithm.

Concluding Remarks

We have shown that the lumped directed-area vectors and the dual volumes required to implement the edge-based discretization can be computed without explicitly forming median dual control volumes and the resulting algorithms for computing the lumped directed-area vectors can be more efficient than a traditional algorithm. Numerical results show that the speed-up factor can be 1.12 for a triangular grid and 2.16 for a tetrahedral grid. More importantly, the proposed algorithm is expected to dramatically simplify the implementation of the edge-based discretization in four and higher dimensions as it does not require the construction of median dual volumes.

Future work includes applications to practical CFD codes, especially for time-dependent simulations with deforming grids. Extensions to mixed-element grids might be possible but the edge-based discretization loses second-order accuracy unless it satisfies certain regularity conditions [31, 33] or a flux correction technique [34] is incorporated. Extensions to another dual control volume defined with the face-area-weighted centroid [35] instead of the geometric centroid, if possible, would be useful because it is known to reduce effects of grid skewness and improve accuracy and efficiency of an edge-based solver as demonstrated in Ref. [35]. Finally, extensions to four dimensions are currently underway, and will be reported in a separate paper.

Acknowledgments

The author gratefully acknowledges support from the U.S. Army Research Office under the contract/grant number W911NF-19-1-0429.

References

  1. [1]T. J. Barth. Numerical aspects of computing viscous high Reynolds number flows on unstructured meshes. AIAA Paper 91-0721, 1991.DOI
  2. [2]R. T. Biedron, J.-R. Carlson, J. M. Derlaga, P. A. Gnoffo, D. P. Hammond, W. T. Jones, B. Kleb, E. M. Lee-Rausch, E. J. Nielsen, M. A. Park, C. L. Rumsey, J. L. Thomas, and W. A. Wood. FUN3D manual: 12.9. NASA-TM–2016–219012, February 2016.
  3. [3]Y. Nakashima, N. Watanabe, and H. Nishikawa. Development of an effective implicit solver for general-purpose unstructured CFD software. In The 28th Computational Fluid Dynamics Symposium, C08-1, Tokyo, Japan, 2014.
  4. [4]N. Kroll, M. Abu-Zurayk, D. Dimitrov, T. Franz, T. Führer, T. Gerhold, S. Görtz, R. Heinrich, C. Ilic, J. Jepsen, J. Jägersküpper, M. Kruse, A. Krumbein, S. Langer, D. Liu, R. Liepelt, L. Reimer, M. Ritter, A. Schwöppe, J. Scherer, F. Spiering, R. Thormann, V. Togiti, D. Vollmer, and J.-H. Wendisch. Dlr project digital-x: Towards virtual aircraft design and flight testing based on high-fidelity methods. CEAS Aeronautical Journal, 7(1):3–27, March 2016.DOI
  5. [5]D. J. Mavriplis and M. Long. NSU3D results for the fourth AIAA drag prediction workshop. AIAA Paper 2010-4363, 2010.
  6. [6]H. Luo, J. D. Baum, and R. Löhner. High-reynolds number viscous flow computations using an unstructured-grid method. In 42nd AIAA Aerospace Sciences Meeting, AIAA Paper 2004-1103, Reno, NV, 2004.
  7. [7]T. Kozubskaya, I. Abalakin, A. Dervieux, and H. Ouvrard. Accuracy improvement for finite-volume vertex-centered schemes solving aeroacoustics problems on unstructured meshes. In 16th AIAA/CEAS Aeroacoustics Conference, AIAA Paper 2010-3933, 2010.DOI
  8. [8]A. Haselbach and J. Blazek. Accurate and efficient discretization of Navier-Stokes equations on mixed grids. AIAA J., 38(11):2094–2102, 2000.
  9. [9]T. Smith, C. Ober, and A. Lorber. SIERRA/Premo-A new general purpose compressible flow simulation code. In 32nd AIAA Fluid Dynamics Conference and Exhibit, AIAA Paper 2002-3292, St. Louis, MO, 2002.DOI
  10. [10]P. Eliasson. EDGE, a Navier-Stokes solver, for unstructured grids. Technical Report FOI-R-0298-SE, Swedish Defence Research Agency, December 2001.
  11. [11]L. Fezoui and B. Stouffle. A class of implicit upwind schemes for Euler simulations with unstructured meshes. J. Comput. Phys., 84:174–206, 1989.DOI
  12. [12]S. Gao, W. G. Habashi, M. Fossati, D. Isola, and G. S. Baruzzi. Finite-element formulation of a Jacobian-free solver for supersonic viscous flows on hybrid grids. In 55th AIAA Aerospace Sciences Meeting, AIAA Paper 2017-0085, Grapevine, Texas, 2017.DOI
  13. [13]H. Nishikawa. Economically high-order unstructured-grid methods: Clarification and efficient FSR schemes. Int. J. Numer. Meth. Fluids, 93:3187–3214, 2021.DOI
  14. [14]A. Katz and V. Sankaran. Mesh quality effects on the accuracy of CFD solutions on unstructured meshes. J. Comput. Phys., 230:7670–7686, 2011.
  15. [15]A. Katz and V. Sankaran. An efficient correction method to obtain a formally third-order accurate flow solver for node-centered unstructured grids. J. Sci. Comput., 51:375–393, 2012.DOI
  16. [16]B. Diskin and J. L. Thomas. Effects of mesh regularity on accuracy of finite-volume schemes. In 50th AIAA Aerospace Sciences Meeting, AIAA Paper 2012-0609, Nashville, Tennessee, 2012.DOI
  17. [17]Y. Liu and H. Nishikawa. Third-order inviscid and second-order hyperbolic Navier-Stokes solvers for three-dimensional inviscid and viscous flows. In 46th AIAA Fluid Dynamics Conference, AIAA Paper 2016-3969, Washington, D.C., 2016.DOI
  18. [18]H. Nishikawa and Y. Liu. Hyperbolic Navier-Stokes method for high-Reynolds-number boundary-layer flows. In 55th AIAA Aerospace Sciences Meeting, AIAA Paper 2017-0081, Grapevine, Texas, 2017.DOI
  19. [19]H. Nishikawa. Accuracy-preserving boundary flux quadrature for finite-volume discretization on unstructured grids. J. Comput. Phys., 281:518–555, 2015.DOI
  20. [20]H. Nishikawa and Y. Liu. Accuracy-preserving source term quadrature for third-order edge-based discretization. J. Comput. Phys., 344:595–622, 2017.DOI
  21. [21]W. L. Kleb, M. A. Park, W. A. Wood, K. L. Bibb, K. B. Thompson, and R. J. Gomez. Sketch-to-solution: An exploration of viscous CFD with automatic grids. In 24th AIAA Computational Fluid Dynamics Conference, AIAA Paper 2019-2948, Dallas, TX, 2019.DOI
  22. [22]K. B. Thompson, H. Nishikawa, and E. Padway. Economical third-order methods for accurate surface heating predictions on simplex element meshes. In AIAA SciTech 2023 Forum, AIAA Paper 2023-2629, National Harbor, MD & Online, 2023.DOI
  23. [23]M. Behr. Simplex space-time meshes in finite element simulations. Int. J. Numer. Meth. Fluids, 57:1421–1434, 2008.DOI
  24. [24]A. Corrigan, A. Kercher, and D. Kessler. The moving discontinuous Galerkin method with interface condition enforcement for unsteady three-dimensional flows. In AIAA Scitech 2019 Forum, AIAA Paper 2019-0642, San Diego, CA, 2019.DOI
  25. [25]P. C. Caplan, R. Haimes, D. L. Darmofal, and M. C. Galbraith. Four-dimensional anisotropic mesh adaptation. Computer-Aided Design, 129, 2020.DOI
  26. [26]C. V Frontin, G. S. Walters, F. D Witherden, C. W Lee, D. M. Williams, and D. L. Darmofal. Foundations of space-time finite element methods: Polytopes, interpolation, and integrations. Appl. Numer. Math., 166:92–113, 2021.arxiv.org/abs/2012.08701
  27. [27]T. McCaughtry, R. Watson, M. Gerun, and S. in Kim. A space-time flux reconstruction approach for unsteady 3D parabolic equations with enhanced convergence acceleration. In AIAA Aviation 2022 Forum, AIAA Paper 2022-4157, Chicago, IL, 2022.DOI
  28. [28]C. O. E. Burg. Higher order variable extrapolation for unstructured finite volume RANS flow solvers. In 17th AIAA Computational Fluid Dynamics Conference, AIAA Paper 2005-4999, Orlando, FL, 2005.DOI
  29. [29]E. Padway and H. Nishikawa. Resolving confusion over third-order accuracy of U-MUSCL. AIAA J., 60(3):1415–1439, March 2022.
  30. [30]C. Debiez and A. Dervieux. Mixed-element-volume MUSCL methods with weak viscosity for steady and unsteady flow calculations. Comput. Fluids, 29:89–118, 2000.DOI
  31. [31]H. Nishikawa. Beyond interface gradient: A general principle for constructing diffusion schemes. In 40th AIAA Fluid Dynamics Conference and Exhibit, AIAA Paper 2010-5093, Chicago, IL, 2010.DOI
  32. [32]H. Nishikawa. Accuracy-preserving boundary flux quadrature for finite-volume discretization on unstructured grids. J. Comput. Phys., 281:518–555, 2015.DOI
  33. [33]B. Diskin and J. L. Thomas. Accuracy analysis for mixed-element finite-volume discretization schemes. NIA Report No. 2007-08, 2007.
  34. [34]H. Nishikawa. A flux correction for finite-volume discretizations: Achieving second-order accuracy on arbitrary polyhedral grids. J. Comput. Phys., 468:111481, 2022.DOI
  35. [35]H. Nishikawa. A face-area-weighted centroid formula for reducing grid skewness and improving convergence of edge-based solver on highly-skewed simplex grids. In AIAA Scitech 2020 Forum, AIAA Paper 2020-1786, Orlando, FL, 2020.DOI

Paper details

vlnc:W_s3q3m298
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents