Interpolating polynomials from their values
Richard E. Zippel · Journal of Symbolic Computation · 1990
A fundamental technique used by many algorithms in computer algebrais interpolating polynomials from their values. This paper discusses two algorithms for solving this problem for sparse multivariate polynomials, an updated version of a probabilistic one and a new deterministic technique that uses some ideas due to Ben-Or and Tiwari (1988). In addition algorithms are presented for quickly finding points that are not zeroes of sparse multivariate polynomials—the zero avoidance problem.