Accession Number:

ADA210102

Title:

Interpolating Polynomials from Their Values

Descriptive Note:

Technical rept.

Corporate Author:

CORNELL UNIV ITHACA NY DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Zippel, Richard

Report Date:

1989-01-01

Pagination or Media Count:

32.0

Abstract:

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.

Descriptors:

• *INTERPOLATION
• *POLYNOMIALS
• PROBLEM SOLVING
• NUMBER THEORY
• ADDITION
• VALUE
• DETERMINANTS(MATHEMATICS)
• MULTIVARIATE ANALYSIS
• ALGORITHMS

Subject Categories:

• Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE