Fast Barycentric-Based Evaluation Over Spectral/hp Elements

Edward Laughton, Vidhi Zala, Akil Narayan, Robert M. Kirby, David Moxey

Introduction

High-order spectral/hp finite element methods are renowned for their ability to achieve exponential convergence and high accuracy in complex simulations, particularly in computational fluid dynamics (CFD). These methods represent solutions as high-degree polynomials within discrete geometric elements. While efficient at fixed quadrature points, these methods often struggle with tasks requiring solution evaluation at arbitrary, changing locations—such as particle tracking, streamline generation, or data transfer across nonconformal moving meshes.

The Bottleneck of Dynamic Evaluation

In standard spectral/hp implementations, evaluating a solution at an arbitrary point typically involves constructing a Lagrangian interpolation matrix. For a fixed point, this matrix can be pre-calculated and cached, making subsequent evaluations a simple matrix-vector multiplication. However, in dynamic scenarios where the evaluation point moves at every timestep, the interpolation matrix must be recalculated from scratch.

This recalculation carries a computational and storage complexity of $\mathcal{O}(k^2)$, where $k$ is the polynomial degree. As researchers push toward higher-order simulations to capture finer physical details, this $\mathcal{O}(k^2)$ scaling becomes a significant bottleneck, often dominating the total simulation time in dynamic applications.

Methodology: Barycentric Interpolation and Transformations

To address this scaling issue, this research introduces a fast evaluation framework based on barycentric Lagrange interpolation. Barycentric interpolation is a mathematically equivalent but computationally superior form of the Lagrange polynomial. Its primary advantage is a complexity of $\mathcal{O}(k)$ for evaluation, and it is famously stable even for very high-degree polynomials.

Tensorization and Duffy Transformations

The challenge lies in extending 1D barycentric formulas to the diverse 2D and 3D shapes used in finite element meshes. The authors employ two primary strategies:

  1. Tensorization: For "box-like" elements (quadrilaterals and hexahedra), the 1D barycentric formula is applied iteratively across each spatial dimension.
  2. Duffy Transformations: For simplicial shapes like triangles, tetrahedra, prisms, and pyramids, the authors utilize Duffy transformations. This technique maps these complex geometries into a standard coordinate system (squares or cubes) by mathematically "collapsing" certain edges or faces, allowing the tensor-based barycentric approach to be applied.

Derivative Synergy

Beyond simple value evaluation, many simulations require spatial derivatives (gradients). The authors extended their barycentric framework to compute first and second derivatives. Because the derivative formulas share many intermediate terms with the value evaluation, they can be computed simultaneously with minimal additional overhead, further increasing efficiency.

Performance and Real-World Impact

The algorithms were implemented in the Nektar++ spectral/hp element library and tested against standard Lagrangian methods across various element types and polynomial orders (up to $k=20$).

Key Benchmarks

  • Dynamic Speedup: For scenarios where evaluation points move, the barycentric method achieved a minimum speedup of $7\times$ compared to standard matrix recalculation.
  • Derivative Efficiency: When calculating both values and first derivatives, the barycentric method was found to be up to 35% faster than even the cached matrix method for certain element types.
  • Storage: The barycentric approach reduces storage requirements from $\mathcal{O}(k^2)$ to $\mathcal{O}(k)$, as it only needs to store weights associated with the fixed nodal points.

Application: Nonconformal Moving Meshes

The practical utility of this method was demonstrated in a 2D scalar transport simulation involving a nonconformal interface between moving meshes. By utilizing the fast barycentric evaluation for data transfer at the interface, the specific routine for point-finding ran $6\times$ faster. This optimization led to a dramatic reduction in total simulation time, dropping from 216 seconds to just 48 seconds—a 75% overall improvement.

Conclusion

The transition to barycentric-based evaluation represents a significant step forward for high-order finite element methods. By reducing the complexity of dynamic evaluations from $\mathcal{O}(k^2)$ to $\mathcal{O}(k)$, this framework enables more complex, high-fidelity simulations of moving interfaces and particle-laden flows that were previously computationally prohibitive. While standard cached matrices remain slightly faster for strictly static points, the barycentric method's versatility and performance in dynamic contexts make it a vital tool for modern computational physics.

Summary updated

BibTeX
@article{laughton2022fast,
  author = {Edward Laughton and Vidhi Zala and Akil Narayan and Robert M. Kirby and David Moxey},
  title = {{Fast Barycentric-Based Evaluation Over Spectral/hp Elements}},
  journal = {J. Sci. Comput.},
  year = {2022},
  doi = {10.1007/s10915-021-01750-2},
}
Figure