A Quadratic-Time Algorithm for General Multivariate Polynomial Interpolation

A Quadratic-Time Algorithm for General Multivariate Polynomial Interpolation

For $m,n \in \mathbb{N}$, $m\geq 1$ and a given function $f : \mathbb{R}^m\longrightarrow \mathbb{R}$ the polynomial interpolation problem (PIP) is to determine a \emph{generic node set} $P \subseteq \mathbb{R}^m$ and the coefficients of the uniquely defined polynomial $Q\in\mathbb{R}[x_1,\dots,x_m]$ in $m$ variables of degree $\mathrm{deg}(Q)\leq n \in \mathbb{N}$ that fits $f$ on $P$, i.e., $Q(p) = f(p)$, $\forall\, p \in P$. We here show that in general, i.e., for arbitrary $m,n \in \mathbb{N}$, $m \geq 1$, there exists an algorithm that determines $P$ and computes the $N(\mbox{m,n})=\#P$ coefficients of $Q$ in $\mathcal{O}\big(N(\mbox{m,n})^2\big)$ time using $\mathcal{O}\big(\mbox{m}N(\mbox{m,n})\big)$ storage, without inverting the occurring Vandermonde matrix. We provide such an algorithm, termed PIP-SOLVER, based on a recursive decomposition of the problem and prove its correctness. Since the present approach solves the PIP without matrix inversion, it is computationally more efficient and numerically more robust than previous approaches. We demonstrate this in numerical experiments and compare with previous approaches based on matrix inversion and linear systems solving.

对于\(m,n\in\mathbb{N}\)，\(m\geq1\)以及给定的函数\(f:\mathbb{R}^m\longrightarrow\mathbb{R}\)，多项式插值问题（PIP）是确定一个\(\emph{一般节点集}\) \(P\subseteq\mathbb{R}^m\)以及在\(m\)个变量中次数\(\mathrm{deg}(Q)\leq n\in\mathbb{N}\)的唯一确定的多项式\(Q\in\mathbb{R}[x_1,\dots,x_m]\)的系数，使得\(Q\)在\(P\)上与\(f\)匹配，即\(\forall p\in P\)，\(Q(p)=f(p)\)。在此我们表明，一般而言，即对于任意的\(m,n\in\mathbb{N}\)，\(m\geq1\)，存在一种算法，它能确定\(P\)并在\(\mathcal{O}(N(m,n)^2)\)时间内使用\(\mathcal{O}(mN(m,n))\)的存储空间计算出\(Q\)的\(N(m,n)=\#P\)个系数，且无需对出现的范德蒙矩阵求逆。我们基于对该问题的递归分解提供了这样一种算法，称为PIP - SOLVER，并证明了其正确性。由于当前方法在解决PIP时无需矩阵求逆，所以它在计算上比先前的方法更高效，在数值上更稳健。我们在数值实验中对此进行了演示，并与基于矩阵求逆和线性系统求解的先前方法进行了比较。