Computational aspects of polynomial interpolation in several variables

Abstract:

The pair $\langle \Theta ,P\rangle$ of a point set $\Theta \subset {\mathbb {R}^d}$ and a polynomial space P on ${\mathbb {R}^d}$ is correct if the restriction map $P \to {\mathbb {R}^\Theta }:p \mapsto {p_{|\Theta }}$ is invertible, i.e., if there is, for any f defined on $\Theta$, a unique $p \in P$ which matches f on $\Theta$. We discuss here a particular assignment $\Theta \mapsto {\Pi _\Theta }$, introduced by us previously, for which $\langle \Theta ,{\Pi _\Theta }\rangle$ is always correct, and provide an algorithm for the construction of a basis for ${\Pi _\Theta }$, which is related to Gauss elimination applied to the Vandermonde matrix ${({\vartheta ^\alpha })_{\vartheta \in \Theta ,\alpha \in \mathbb {Z}_ + ^d}}$ for $\Theta$. We also discuss some attractive properties of the above assignment and algorithmic details, and present some bivariate examples.