Volume 42, pp. 41-63, 2014.

Approximating optimal point configurations for multivariate polynomial interpolation

Marc van Barel, Matthias Humet, and Laurent Sorber


Efficient and effective algorithms are designed to compute the coordinates of nearly optimal points for multivariate polynomial interpolation on a general geometry. “Nearly optimal” refers to the property that the set of points has a Lebesgue constant near to the minimal Lebesgue constant with respect to multivariate polynomial interpolation on a finite region. The proposed algorithms range from cheap ones that produce point configurations with a reasonably low Lebesgue constant, to more expensive ones that can find point configurations for several two-dimensional shapes which have the lowest Lebesgue constant in comparison to currently known results.

Full Text (PDF) [1 MB]

Key words

(nearly) optimal points, multivariate polynomial interpolation, Lebesgue constant, greedy add and update algorithms, weighted least squares, Vandermonde matrix, orthonormal basis

AMS subject classifications

41A10, 65D05, 65D15, 65E05

< Back