Approximate complex polynomial evaluation in near constant work per point
John H. Reif · 1997
. Given the n complex coe#cients of a degree n - 1 complex polynomial, we wish to evaluate the polynomial 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 (e.g., [A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974]). We assume an arithmetic model of computation, where on each step we can execute an arithmetic operation, which is computed exactly. All previous exact algorithms [C. M. Fiduccia, Proceedings 4th Annual ACM Symposium on Theory of Computing, 1972, pp. 88--93; H. T. Kung, Fast Evaluation and Interpolation, Carnegie-Mellon, 1973; A. B. Borodin and I. Munro, The Computational Complexity of Algebraic and Numerical Problems, American Elsevier, 1975; V. Pan, A. Sadikou, E. Landowne, and O. Tiga, Comput. Math. Appl., 25 (1993), pp. 25--30] cost at least work ## log 2 n) per point, and previously, the...