Randomized interpolation and approximation of sparse polynomials. (English) Zbl 0826.65005

Mansour, Yishay

SIAM J. Comput. 24, No. 2, 357-368 (1995).

The author describes a randomized algorithm which calculates the coefficients of a polynomial \(P\) of degree \(\leq d\) with integer coefficients \(a_l\) with \(|a_l|\leq L\) which is \(t\)- sparse, i.e., has at most \(t\) non-zero coefficients. The procedure interpolates the values of \(P\) in the \(d\)-th roots of unity \(\omega^k_d\). The running time measured by the number of bit operations performed is bounded by a polynomial in \(t\), \(\log d\) and \(\log L\). The technique extends to multivariate polynomials. An application is the \(L^2\)-approximation of polynomials by sparse polynomials.

Reviewer: R.Wegmann (Garching)

MSC:

65D05	Numerical interpolation
41A10	Approximation by polynomials

Keywords:

randomized interpolation; randomized algorithm; multivariate polynomials; sparse polynomials