DELAWARE VALLEY COMPUTER ALGEBRA SEMINAR

Approximate Complex Polynomial Evaluation in
Near Constant Work Per Point

John H. Reif

Computer Science Department, Duke University

We provide approximation algorithms for polynomial evaluation on the complex plane that cost, in many cases, near constant amortized work per point evaluation. To do this, we use an interesting reduction to fast Multipole algorithms for solving Trummer's problem. All previous algorithms for polynomial evaluation cost at least work O(log^2 n) per point.

We also provide approximation algorithms for polynomial evaluation restricted to the complex circle using instead a reduction to approximate real polynomial evaluation by interpolation at the Chebychev points. All of our results require poly-logarithmic depth with the same work bounds.

We further provide a lower bound for a wide class of schemes for approximate evaluation of a degree n polynomial on the unit circle; namely we prove that if a scheme uses an approximation polynomial of degree k, then it can only be convergent over a small fraction O(k/n) of the unit circle. This is the first lower bound of this sort proved, and the proof uses an interesting reduction to the approximation of a matrix product by a matrix of reduced rank.

Also to be presented at 29th Annual ACM Symposium on Theory of Computing (STOC), in El Paso, Texas, May 4-6, 1997.

A PostScript version of this paper is at http://www.cs.duke.edu/~reif/paper/Eval.ps

Friday, April 18, 1997 at 3:30pm in Room 259 of the Korman Center at Drexel University, 33rd and Market Streets, Philadelphia, PA.