Edge-Based Discretization Computes Grid Metrics Without Forming Dual Control Volumes

Computational fluid dynamics solvers relying on node-centered edge-based discretization can now compute essential geometric metrics on arbitrary simplex-element grids without explicitly constructing median dual control volumes around mesh nodes. In a study published in Advances in Aerodynamics, researcher Hiroaki Nishikawa demonstrates that lumped directed-area vectors at interior mesh edges and median dual control volumes at nodes can be evaluated directly from element face vectors and element volumes. The formulation applies to two-dimensional triangular grids and three-dimensional tetrahedral grids. By eliminating the necessity of geometrically stitching together element centroids, edge midpoints, and face centroids to form median dual control cells, the proposed approach streamlines solver code architectures while accelerating metric generation. Crucially, the mathematical reformulation provides a viable pathway toward extending edge-based finite-volume schemes into four dimensions and beyond, where explicitly forming high-dimensional median dual control volumes in simplex elements such as pentatopes has historically posed severe geometric difficulties.

Node-centered edge-based discretization has become a cornerstone of contemporary unstructured-grid computational fluid dynamics solvers because of its computational efficiency and compact algorithmic structure. In standard second-order accurate schemes, point-valued solutions are stored at mesh nodes, and residual evaluations are executed through an efficient single loop over mesh edges. At each edge, numerical fluxes are computed using only the state solutions and reconstructed gradients from the two connecting end nodes, avoiding wide stencils. Furthermore, previous studies demonstrated that this edge-based formulation can attain third-order spatial accuracy with a single numerical flux per edge on arbitrary simplex-element meshes without demanding high-order curved meshes or second-derivative computations. These favorable properties make edge-based methods particularly attractive for automated fluid dynamics simulations involving anisotropic viscous grid adaptation. However, implementing these schemes requires precomputing two fundamental geometric metrics for a given mesh: the lumped directed-area vectors associated with every edge and the dual volumes associated with every node, which traditionally required tedious median dual geometric constructions.

Under the conventional geometric paradigm, computing these two grid metrics demands an element-by-element reconstruction of partial median dual control volumes. In two-dimensional triangular elements, engineers must compute the edge midpoint coordinates and element centroids, connecting them to construct planar median dual interfaces whose outward area vectors accumulate into edge-based directed-area arrays. In three dimensions, the construction becomes significantly more complex because each tetrahedral element contributes two internal triangular dual faces per edge. To evaluate their contributions, traditional algorithms must calculate the edge midpoint, the element centroid, and the centroids of both adjacent triangular faces, followed by cross products to establish the two dual-face area vectors. This traditional element loop accumulates local contributions to edges and nodes, requiring extensive floating-point calculations and intermediate geometric bookkeeping. While manageable in two and three spatial dimensions, the process becomes extraordinarily complex in four dimensions, where constructing a median dual control volume inside a four-dimensional simplex element has remained a major conceptual barrier.

The central mathematical insight presented in the new algorithm is that directed-area vectors of median dual faces can be expressed entirely in terms of the outward directed-area vectors of the primary simplex-element faces. When examining a simplex element sharing an interior edge, expressing median dual face vectors via element face vectors introduces auxiliary vector components along internal element dividing faces. Remarkably, when these local expressions are summed across all simplex elements that share a given interior edge, the auxiliary internal vectors on adjoining side faces completely cancel out. For any interior edge connecting node j and node k in a D-dimensional simplex grid, the net lumped directed-area vector simplifies to a compact summation: the factor two divided by D times the quantity D plus one, multiplied by the sum of outward face directed-area vectors opposite to node j across all elements sharing that edge. Consequently, practitioners can evaluate lumped directed-area vectors directly from standard outward element face vectors without constructing internal median dual surfaces.

At computational domain boundaries, the internal vector cancellation is incomplete because boundary edges do not possess a complete ring of surrounding elements. The study resolves this boundary closure by deriving an explicit, orientation-independent correction formula executed in a subsequent loop over boundary elements. In two dimensions, boundary edges require an additional term equal to one-sixth of the boundary edge’s outward directed-area vector. In three dimensions, each boundary triangular face contributes one-twelfth of its outward directed-area vector to its three constituent boundary edges. In general D-dimensional space, the boundary correction is precisely the boundary element’s outward directed-area vector divided by the product of D and D plus one. Because the mathematical derivation shows that this additive boundary contribution is strictly independent of whether an edge is indexed from the lower node number to the higher node number or vice versa, the boundary closure implementation is computationally straightforward and avoids conditional branching or sign adjustments.

To complement the edge metric formulation, the paper presents two alternative approaches for evaluating median dual volumes at nodes without constructing median dual control cells. The first technique leverages the divergence theorem applied to the identity position vector over the dual control volume. This converts the volume integral into a closed surface integral that evaluates exactly via edge-based numerical flux quadratures. The resulting formula allows node dual volumes to be accumulated in a single loop over edges, distributing vector dot products between edge displacement vectors and lumped directed-area vectors to both end nodes, followed by scaling by one over two D in a node loop. The second technique employs an element-based loop, using the proven geometric property that the median dual volume contribution of any D-dimensional simplex element to each of its constituent nodes is identically equal to one divided by D plus one of the total element volume. Applying the divergence theorem confirms that triangular elements distribute one-third of their area to each node, while tetrahedra distribute one-fourth of their volume to each vertex.

Theoretical complexity analyses based on floating-point operation counts illustrate the significant efficiency advantages of the new formulation over traditional algorithms, especially in three dimensions. For interior edges on triangular meshes, the traditional algorithm demands twenty-two additions and eight multiplications per triangle to determine edge midpoints, centroids, and dual-face components, whereas the proposed element-face formulation requires only twelve additions and six multiplications per triangle. This yields a theoretical multiplication speed-up factor of approximately 1.3 in two dimensions. In three-dimensional tetrahedral grids, the contrast is far more pronounced: the traditional procedure consumes two hundred five additions and approximately 129.5 multiplications per tetrahedron when accounting for centroid, dual-face cross products, and edge scalings. In contrast, the proposed method requires only seventy-two additions and 39.5 multiplications per tetrahedron, projecting an approximate three-fold computational speed-up for evaluating three-dimensional lumped directed-area vectors on large tetrahedral meshes.

To validate the theoretical findings, the researcher implemented both traditional and proposed algorithms in serial research solvers written for two- and three-dimensional configurations, executing benchmark tests on structured-topology simplex domains. Computational experiments evaluated metric calculations on a two-dimensional triangular grid containing 65,536 nodes and 130,050 triangles within a unit square, alongside a massive three-dimensional tetrahedral grid comprising 16,974,593 nodes and 100,663,296 tetrahedra within a unit cube. CPU times were measured in seconds and averaged across ten consecutive runs. In the two-dimensional triangular benchmark, the proposed formulation achieved a modest speed-up factor of 1.12 over the traditional dual-face method. Furthermore, evaluating dual volumes via the edge-based divergence approach required slightly more CPU time than the simple element-based volume distribution, confirming the complexity prediction that element-based volume accumulation remains computationally superior on two-dimensional triangular meshes.

In three-dimensional tetrahedral testing, the proposed algorithms delivered substantial performance enhancements that closely matched theoretical complexity predictions. For the hundred-million-element tetrahedral grid, computing the lumped directed-area vectors with the traditional dual-control-volume algorithm required 29.22 seconds per execution, whereas the proposed face-vector formulation reduced execution time to 13.50 seconds, representing an empirical speed-up factor of 2.16. For dual volume calculations, the edge-based formulation outpaced element-based accumulation, demonstrating an empirical speed-up factor of 1.89. The author highlighted that while grid metric initialization represents only a minor fraction of overall runtime in steady-state aerodynamic calculations, these computational gains become highly impactful in time-dependent simulations featuring dynamic deforming meshes or aggressive anisotropic mesh adaptation. For instance, across a one-thousand-time-step unsteady simulation requiring metric recomputation at every physical step, the traditional approach would accumulate 29,220 seconds of metric calculation time, whereas the proposed algorithm requires only 13,500 seconds, saving over four hours of execution time.

The study also emphasizes rigorous verification protocols to ensure correctness when embedding these formulations into computational fluid dynamics codebases. To verify lumped directed-area vectors, solvers can accumulate the vectors across all edges into node-based vector arrays; interior nodes must sum precisely to zero, reflecting closed-contour equilibrium. At boundary nodes, adding outward boundary face vectors scaled by one over D restores a net zero vector sum, guaranteeing exact conservation under uniform free-stream conditions. Similarly, dual volumes are verified by confirming that the sum of all nodal dual volumes reproduces the exact total domain volume. Looking forward, the author notes that extending the formulation to four-dimensional space-time pentatope elements is actively underway, while future investigations will explore implementations in production-grade parallel CFD solvers, mixed-element meshes requiring accuracy-preserving flux corrections, and alternative dual formulations utilizing face-area-weighted centroids to mitigate grid skewness.

Subject of Research: Edge-based discretization algorithms for computational fluid dynamics without forming median dual control volumes

Article Title: An efficient implementation of edge-based discretization without forming dual control volumes

Article References: Nishikawa, H. (2025). An efficient implementation of edge-based discretization without forming dual control volumes. Advances in Aerodynamics, 7(1), Article 11. https://doi.org/10.1186/s42774-025-00219-2

Image Credits: AI Generated

DOI: 10.1186/s42774-025-00219-2

Keywords: computational fluid dynamics, edge-based discretization, median dual control volumes, lumped directed-area vectors, dual volumes, tetrahedral grids, triangular grids, simplex elements, divergence theorem, aerodynamic simulations, finite volume methods, space-time simulations, grid metric computation, deforming grids, mesh adaptation, boundary closure, upwind flux