Interpolating Polynomials from Their Values

摘要

A fundamental technique used by many algorithms in computer-algebra is 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. Keywords: Number theory; Vandermonde matrix; Dense interpolations. (KR)