Interpolating Polynomials from Their Values

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1989
Accession Number
ADA210102

Entities

People

  • Richard Zippel

Organizations

  • Cornell University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Coefficients
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Department Of Defense
  • Equations
  • Interpolation
  • Military Research
  • New York
  • Number Theory
  • Numbers
  • Polynomials
  • Probability
  • Real Numbers

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Linear Algebra