Approximate complex polynomial evaluation in near constant work per point


Journal Article

The n complex coefficients of a degree n-1 complex polynomial are given and this polynomial is evaluated at a large number m≥n of points on the complex plane. This problem is required by many algebraic computations and so is considered in most basic algorithm texts. An arithmetic model of computation is assumed. Approximation algorithms for complex polynomial evaluation that cost, in many cases, near constant amortized work per point are presented.

Full Text

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • January 1, 1999

Published In

Volume / Issue

  • 28 / 6

Start / End Page

  • 2059 - 2089

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/S0097539797324291

Citation Source

  • Scopus