The Notion of Unisolvence#
The pioneering works of[1][2][3] gave constructions of nodes \(P_A\) that turn out to be unisolvent for downward closed multi-index sets \(A= A_{m,n,1}\) or \(A =A_{m,n,\infty}\) given by \(l_1\)- or \(l_\infty\)-degree.
For multi-index sets \(A_{m,n,p}\), \(1\leq p \leq \infty\) and interpolation nodes \(P_A=\{p_{\alpha}\}_{\alpha\in A} \subseteq \Omega =[-1,1]^m\) a set \(\{q_{\alpha}\}_{\alpha \in A}\) of multivariate polynomials (e.g., \(q_{\alpha}(x) = x^\alpha:=x_1^{\alpha_1}\cdots x_m^{\alpha_m}\)), generating the polynomial space \(\Pi_A = \left<q_{\alpha} : \alpha \in A \right>\) the multivariate Vandermonde matrix is given by
For \(q_{\alpha}(x) = x^\alpha\), this results in the classic \(V(P_A) = \big (p_{\alpha}^\beta\big)_{\alpha,\beta \in A}\)[4]. If \(V(P_A)\) is (numerically) invertible, then one can interpolate f by solving the linear system of equations
This requires \(\mathcal{O}(|A|^r)\) operations with \(r>2\)[5][6], whereas the present DDS achieves quadratic runtime \(\mathcal{O}(|A|^2)\). Indeed,
yields the unique interpolant of \(f\) in \(P_A\), i.e., \(Q_{f,A}(p)=f(p)\) for all \(p \in P_A\). We therefore call a set of nodes \(P_A\) unisolvent with respect to \(\Pi_A\) if and only if \(V(P_A)\) is invertible, i.e., if and only if its null space \(\ker V(P_A) =0\) is trivial. The condition \(\ker V(P_A) =0\) is equivalent to requiring that there exists no hypersurface \(H = Q^{-1}(0)\) generated by a polynomial \(0\not =Q \in \Pi_A\) with \(P_A \subseteq H\). Indeed, the coefficients \(C\) of such a polynomial would be a non-trivial solution of \(V(P_A)C=0\).
However, even if \(P_A\) is unisolvent, the matrix \(V(P_A)\) rapidly becomes numerically ill-conditioned for higher dimensions or degrees when using the canonical basis \(q_{\alpha}(x) =x^\alpha\), \(\alpha \in A\). While previous approaches addressed this problem by tensorial interpolation[7][8][9], Minterpy is based on the Multidimensional Divided Difference Scheme (DDS) that even for non-tensorial interpolation nodes such as the by default chosen Leja ordered Chebyshev-Lobatto nodes realizes efficient and accurate polynomial interpolation.
References