Fast Barycentric-Based Evaluation Over Spectral/hp Elements

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

Here is a summary of the paper tailored for a technically literate audience.

TL;DR

This paper introduces a fast, barycentric-based interpolation method for evaluating solutions at arbitrary points within high-order spectral/hp finite elements. By generalizing 1D barycentric interpolation to 2D and 3D shapes using coordinate transformations, the authors achieve massive computational speedups for dynamic evaluations. This is especially useful for fluid dynamics simulations involving moving interfaces or particle tracking, cutting total simulation time by up to 75% in real-world scenarios.

What Problem Does This Paper Address?

In high-order finite element methods (like spectral/hp elements), simulations achieve high accuracy by representing solutions as polynomials within discrete geometric elements. During the core simulation, the math is usually evaluated at fixed, pre-determined locations called "quadrature points."

However, many post-processing and dynamic tasks—like drawing streamlines, tracking particles, or stitching together mismatched (nonconformal) moving meshes—require evaluating the solution at arbitrary, changing points.

The standard way to do this uses a Lagrangian interpolation matrix. If the target point is fixed, you compute the matrix once, cache it, and matrix-multiply it when needed. But if the point is constantly moving, you have to recalculate this matrix from scratch every single time. This recalculation has a computational and storage complexity of $\mathcal{O}(k^2)$ (where $k$ is the polynomial degree), creating a massive bottleneck in dynamic simulations.

Methods

The authors tackle this bottleneck by adapting barycentric Lagrange interpolation. While barycentric interpolation is well-known for being fast ($\mathcal{O}(k)$ complexity) and numerically stable in 1D, applying it to complex 2D and 3D finite elements is non-trivial.

Here is how they did it:

  • Tensorization: For standard "box-like" elements (quadrilaterals in 2D, hexahedra in 3D), they use a dimension-by-dimension approach, applying the 1D barycentric formula iteratively across each axis.
  • Duffy Transformations: For complex "simplicial" shapes (triangles, tetrahedra, prisms, pyramids), standard tensor math doesn't work. The authors use Duffy transformations—a mathematical trick that maps complex shapes into standard squares or cubes by "collapsing" coordinates (e.g., treating a triangle as a square where one entire edge is collapsed into a single point).
  • Derivative Synergy: They extended the math to compute first and second spatial derivatives. Because the barycentric derivative formulas share terms with the physical value calculations, they can be computed simultaneously with very little extra overhead.

The algorithms were implemented and optimized in the open-source spectral/hp element library Nektar++.

Datasets

The authors do not use traditional machine learning datasets. Instead, they evaluate their algorithms using:

  • Synthetic Baseline Tests: Polynomial evaluations across various element shapes (1D segments, 2D quads/triangles, 3D hexes/tets) and polynomial orders (2 to 20).
  • Real-World Simulation: A 2D scalar transport (advection) equation using a nonconformal discontinuous Galerkin (DG) setup. This tests the algorithm's performance on transferring data across a dynamically moving mesh interface.

Key Insights and Ideas

  • The "Moving Point" Advantage: If you are evaluating the exact same point repeatedly, standard matrix multiplication is hard to beat. But the moment that point moves (requiring matrix recalculation), the barycentric method vastly outperforms the standard approach because its weights only depend on the fixed nodal configuration, not the arbitrary evaluation point.
  • Storage Efficiency: The barycentric method requires only $\mathcal{O}(k)$ storage for its weights, compared to the $\mathcal{O}(k^2)$ space complexity required to store Lagrangian interpolation matrices.
  • Free Derivatives: Because the barycentric method unifies the evaluation of physical values and their derivatives, calculating both at the same time is highly efficient. It reuses intermediate mathematical terms, saving repeat calculations.

Key Results

  • Massive Dynamic Speedups: In synthetic tests where the evaluation point changes (meaning the standard matrix must be recalculated), the barycentric method achieved a minimum speedup factor of $7\times$ across all element types and polynomial orders.
  • Derivative Performance: When calculating both physical values and first derivatives, the barycentric method actually outperformed the cached (stored) matrix method by up to 35% (averaging 15% faster for quadrilaterals).
  • Real-World Impact: In the advection simulation with a nonconformal interface, the routine responsible for finding points on the interface ran $6\times$ faster using the barycentric method. This reduced the total simulation time for 10,000 timesteps from 216 seconds down to just 48 seconds.

Limitations and Future Work

Limitations: The primary limitation is performance on strictly static points. If the evaluation points never move (e.g., fixed history points tracking a specific coordinate over time), the barycentric method is slightly slower—between 10% and 50% depending on the element type—than simply caching and multiplying a standard Lagrangian matrix.

Future Work: While not explicitly mapped out in a dedicated section, the authors imply that these fast evaluation routines will become a core capability in Nektar++ to accelerate a broader range of post-processing operations, such as streamline integration and isosurface extraction in complex 3D fluid dynamics.

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