Interpolating Polynomials from Their Values
CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Numerical Mathematics