Approximate complex polynomial evaluation in near constant work per point


Journal Article

The polynomial at a large number of m≥n of points on the complex plane given the n complex coefficients of a degree n - 1 complex polynomial is evaluated. This problem is required by many algebraic computations and is considered in most basic algorithm texts. An arithmetic model for computation is assumed, where an arithmetic operation can be executed on each step, and is computed exactly. An approximation algorithm is provided for complex polynomial evaluation that cost near constant amortized work per point.

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • January 1, 1997

Published In

Start / End Page

  • 30 - 39

International Standard Serial Number (ISSN)

  • 0734-9025

Citation Source

  • Scopus