2017/10/30 by Michael Hecht, Hecht, M., Bevan L. Cheeseman +5
Computer Science · Mathematics · #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Numerical methods for differential equations #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1710.10846
openalex publication_date 2017/10/30 · openalex created_date 2017/11/10 · openalex updated_date 2026/07/28
For m,n ∈ ℕ, m≥ 1 and a given function f : ℝm\longrightarrow ℝ the polynomial interpolation problem (PIP) is to determine a generic node set P ⊆ ℝm and the coefficients of the uniquely defined polynomial Q∈ℝ[x1,…,xm] in m variables of degree deg(Q)≤ n ∈ ℕ that fits f on P, i.e., Q(p) = f(p), ∀ p ∈ P. We here show that in general, i.e., for arbitrary m,n ∈ ℕ, m ≥ 1, there exists an algorithm that determines P and computes the N(m,n)=#P coefficients of Q in O(N(m,n)2) time using O(mN(m,n)) 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.