Bivariate Lagrange interpolation at the Padua points: Computational aspects

The so-called “Padua points” give a simple, geometric and explicit construction of bivariate polynomial interpolation in the square. Moreover, the associated Lebesgue constant has minimal order of growth O(log2(n))O(log2(n)). Here we show four families of Padua points for interpolation at any even or odd degree nn, and we present a stable and efficient implementation of the corresponding Lagrange interpolation formula, based on the representation in a suitable orthogonal basis. We also discuss extension of (non-polynomial) Padua-like interpolation to other domains, such as triangles and ellipses; we give complexity and error estimates, and several numerical tests.