Accelerating Multivariate Newton Interpolation in Downward Closed Polynomial Spaces
For researchers in numerical analysis and approximation theory, this provides a faster algorithm for multivariate Newton interpolation in downward closed spaces, which is an incremental improvement over existing methods.
The paper introduces the fast Newton transform (FNT), a multivariate Newton interpolation algorithm for downward closed polynomial spaces that achieves O(m ̅n |A|) time complexity, improving on the quadratic O(|A|^2) of the classic divided difference scheme and the tensorial cost, while maintaining approximation rates of tensor product interpolation with fewer degrees of freedom.
We introduce the fast Newton transform (FNT), a multivariate Newton interpolation algorithm for downward closed polynomial spaces in quasi-tensorial grids. The FNT computes the Newton coefficients directly, without relying on embeddings into enclosing tensor-product spaces. For a downward closed index set $A \subset \mathbb N_0^m$, the FNT achieves a time complexity of $\mathcal O(m \overline n |A|)$, where $\overline n$ is the mean of the coordinate-wise maximal polynomial degrees $n_1, \ldots, n_m$ across the $m$ spatial dimensions. In the univariate case, the FNT renders the classic Newton divided difference scheme (DDS). In the multivariate case, however, it improves on the quadratic complexity $\mathcal O(|A|^2)$ of the DDS and on the cost $\mathcal{O}(m \overline n (n_1+1) \cdots (n_m+1))$ of the tensorial interpolation. For sufficiently regular functions, Newton interpolation in Euclidean-degree downward closed polynomial spaces is known to deliver approximation rates equal to those of the tensor product interpolation. Thus, the acceleration power of the FNT comes from requiring substantially fewer degrees of freedom while reaching the same approximation quality as the tensorial interpolation. The inverse transformation has the same time complexity and enables fast evaluation and differentiation of Newton interpolants in quasi-tensorial grids.