zbMATH — the first resource for mathematics

Randomized interpolation and approximation of sparse polynomials. (English) Zbl 0826.65005
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.

65D05 Numerical interpolation
41A10 Approximation by polynomials
Full Text: DOI