Sparse Polynomial Interpolation in Non-standard Bases

In this paper, we consider the problem of interpolating univariate polynomials over a field of characteristic zero that are sparse in (a) the Pochhammer basis or, (b) the Chebyshev basis. The polynomials are assumed to be given by black boxes, i.e., one can obtain the value of a polynomial at any point by querying its black box. We describe efficient new algorithms for these problems. Our algorithms may be regarded as generalizations of Ben-Or and Tiwari's (1988) algorithm (based on the BCH decoding algorithm) for interpolating polynomials that are sparse in the standard basis. The arithmetic complexity of the algorithms is O(t 2 + t log d) which is also the complexity of the univariate version of the Ben-Or and Tiwari algorithm. That algorithm and those presented here also share the requirement of 2t evaluation points. Key words: polynomial interpolation, sparsity, Chebyshev polynomial, Pochhamer basis, BCH codes. AMS(MOS) subject classifications: 68Q40, 12Y05, 41A05. Abbreviated..