Paper Info
Title
Sparse multivariate polynomial interpolation via the quotient-difference algorithm
Abstract
To reconstruct a black box multivariate sparse polynomial from its floating point evaluations, the existing algorithms need to know upper bounds for both the number of terms in the polynomial and the partial degree in each of the variables [2]. On the other hand, Rutishauser's quotient-difference algorithm [7, 3], or the qd-algorithm, is an iterative method that can be use to determine the poles of a meromorphic function from its Taylor coefficients. Combining the relation between the qd-algorithm, Prony's method and their connections to the Ben-Or/Tiwari algorithm [6], we present a new algorithm for reconstructing sparse multivariate polynomials in floating point arithmetic, in which neither the number of terms nor any partial degrees are required in the input [1]. For example, consider the bivariate black box polynomial function, f(x1,x2) = 1/3x6/1+4x4/2--2.1x4/1--4x2/2+x1x2+4x2/1, termed the six-hump camel back function. Evaluate f (x1 , x2 ) at the non-equidistant s-th powers of (1/3, 1/5), in which 3 and 5 are relatively prime, and proceed with the qd-algorithm on the data f (1/3, 1/5), f (1/32, 1/52), f (1/33, 1/53), ....The magnitude of the values in the first five e-columns drops from 10--2 to machine precision, while all values in the sixth e-column are of the order of machine precision. We conclude that the number of terms is 6 and obtain the multi-indices in the support directly from the q-values: 1/q1(S) → 9 = 32. 1/q2(S) → 25 = 52. 1/q3(S) → 625 = 54. 1/q2(S) → 15 = 3151. 1/q1(S) → 81 = 34. 1/q1(S) → 729 = 36. After all six multi-indices in f are known, the coefficients in f can be recovered by a linear system formed by (at least six) evaluations of f. The convergence to zero of some e-columns in the qd-algorithm can be interpreted in an analogous way as the zero discrepancies in the early termination strategy [5, 4]. This is illustrated in Maple. Our sparse interpolation can be extended to polynomials represented in certain non-standard bases [4]. We show an extension to sparse interpolation of polynomials in the Pochhammer basis and present our current research on sparse polynomial interpolation in the Chebyshev basis, both in floating point arithmetic.
Year
DOI
Venue
2008
10.1145/1504347.1504363
ACM Comm. Computer Algebra
Keywords
Field
DocType
black box multivariate sparse,machine precision,bivariate black box polynomial,existing algorithm,floating point arithmetic,sparse multivariate polynomial,quotient-difference algorithm,tiwari algorithm,sparse interpolation,partial degree,sparse multivariate polynomial interpolation,sparse polynomial interpolation,iteration method,linear system,floating point,meromorphic function,polynomial interpolation,upper bound
Discrete mathematics,Combinatorics,Zero of a function,Polynomial,Minimal polynomial (field theory),Floating point,Quotient,Interpolation,Algorithm,Machine epsilon,Coprime integers,Mathematics
Journal
Volume
Issue
Citations 
42
3
0
PageRank 
References 
Authors
0.34
5
2
Name
Order
Citations
PageRank
Annie Cuyt116141.48
Wen-shin Lee218215.67