A Quadratic-Time Algorithm for General Multivariate Polynomial Interpolation

Authors Michael Hecht, Bevan L. Cheeseman, K. B. Hoffmann, Ivo F. Sbalzarini

Publication date 30 October 2017

Abstract: For

m, n i n m a t h b b N

,

m g e q 1

and a given function

f : m a t h b b R^{m} l o n g r i g h t a r r o w m a t h b b R

the polynomial interpolation problem (PIP) is to determine a emph{generic node set}

P s u b s e t e q m a t h b b R^{m}

and the coefficients of the uniquely defined polynomial

Q i n m a t h b b R [x_{1}, d o t s, x_{m}]

in

m

variables of degree

m a t h r m d e g (Q) l e q n i n m a t h b b N

that fits

f

on

P

, i.e.,

Q (p) = f (p)

,

f o r a l l, p i n P

. We here show that in general, i.e., for arbitrary

m, n i n m a t h b b N

,

m g e q 1

, there exists an algorithm that determines

P

and computes the

coefficients of

Q

in

time using

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.

This page was built for publication: A Quadratic-Time Algorithm for General Multivariate Polynomial Interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6293226)