Scholars@Duke

Approximate complex polynomial evaluation in near constant work per point

Publication ,  Journal Article
Reif, JH
Published in: SIAM Journal on Computing
January 1, 1999
Published version (DOI)

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.

Duke Scholars

John H. Reif
Author John H. Reif Computer Science

Published In

SIAM Journal on Computing

DOI

10.1137/S0097539797324291

ISSN

0097-5397

Publication Date

January 1, 1999

Volume

28

Issue

6

Start / End Page

2059 / 2089

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1999). Approximate complex polynomial evaluation in near constant work per point. SIAM Journal on Computing, 28(6), 2059–2089. https://doi.org/10.1137/S0097539797324291
Reif, J. H. “Approximate complex polynomial evaluation in near constant work per point.” SIAM Journal on Computing 28, no. 6 (January 1, 1999): 2059–89. https://doi.org/10.1137/S0097539797324291.
Reif JH. Approximate complex polynomial evaluation in near constant work per point. SIAM Journal on Computing. 1999 Jan 1;28(6):2059–89.
Reif, J. H. “Approximate complex polynomial evaluation in near constant work per point.” SIAM Journal on Computing, vol. 28, no. 6, Jan. 1999, pp. 2059–89. Scopus, doi:10.1137/S0097539797324291.
Reif JH. Approximate complex polynomial evaluation in near constant work per point. SIAM Journal on Computing. 1999 Jan 1;28(6):2059–2089.

Published In

SIAM Journal on Computing

DOI

10.1137/S0097539797324291

ISSN

0097-5397

Publication Date

January 1, 1999

Volume

28

Issue

6

Start / End Page

2059 / 2089

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics