Approximate complex polynomial evaluation in near constant work per point

Given the n complex coefficients of a degree n - 1 complex polynomial, we w ish to evaluate the polynomial at a large number m greater than or equal to n of points on the complex plane. This problem is required by many algebra ic 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 Com puter Algorithms, Addison-Wesley, 1974]). We assume an arithmetic model of computation, where on each step we can execute an arithmetic operation, whi ch is computed exactly. All previous exact algorithms [C. M. Fiduccia, Proc eedings 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 Numeric al 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 Omeg a(log(2) n) per point, and previously, there were no known approximation al gorithms for complex polynomial evaluation within the unit circle with work bounds better than the fastest known exact algorithms. There are known app roximation algorithms [V. Rokhlin, J. Complexity, 4 (1988), pp. 12-32; V. Y . Pan, J. H. Reif, and S. R. Tate, in Proceedings 32nd Annual IEEE Symposiu m on Foundations of Computer Science, 1992, pp. 703-713] for polynomial eva luation at real points, but these do not extend to evaluation at general po ints on the complex plane. We provide approximation algorithms for complex polynomial evaluation that cost, in many cases, near constant amortized work per point. Let k = log(\P \/epsilon), where \P\ is the sum of the moduli of the coefficients of the i nput polynomial P(z). Let (P) over tilde(z(j)) be an epsilon-approx of P(z) if epsilon upper bounds the modulus of the error of the approximation (P) over tilde(z(j)) at each evaluation point z(j), that is, \P(z(j)) - (P) ove r tilde(z(j))\ less than or equal to epsilon; note that epsilon is an absol ute error bound rather than a relative error bound. In many applications (p articularly in signal processing) the evaluation points z(j) are fixed and require only polylogarithmic k = log(\P\/epsilon) = O(log(O(1)) n); for the se cases we get a surprising reduction in work by use of approximation algo rithms, as compared to the fastest known exact algorithms. We epsilon-approx complex degree n - 1 polynomial evaluation at m greater t han or equal to n log n/ log(2) k fixed points on or within the unit disk i n the complex plane in amortized work O(log(2) k) per point, which is O(log (2) log n) for polylogarithmic k. If the m points are not fixed, then we ha ve increased amortized work O(log(2) k+log m) per point, which is O(log m) for polylogarithmic k and m greater than or equal to n log n/ log k, and is still substantially below the previous bound of Omega(log(2) m) for known exact algorithms. We further reduce our amortized bounds for special sets o f evaluation points widely used in signal processing applications. The chir p transform is equivalent to evaluating a complex degree n - 1 polynomial a t the chirp points, which are zeta(j), j = 0,..., m - 1, for some fixed com plex number zeta. We epsilon-approx complex degree n - 1 polynomial evaluat ion at these m chirp points, where m greater than or equal to n log n/ log( 2) k and \zeta\ less than or equal to 1 in amortized work O(log k) per poin t, whereas the previous best bounds for exact evaluation (via the chirp tra nsform) were Omega(log m) per point [A. V. Aho, K. Steiglitz, and J. D. Ull man, SIAM J. Comput., 4 (1975), pp. 533-539]. All these results use an inte resting reduction to fast multipole algorithms for solving Trummer's proble m. Using instead a reduction to approximate real polynomial evaluation (by int erpolation at the Chebyshev points), in total work O(n log k), we epsilon-approx the evaluation of a degree n polynomial at the first n power s of the n'th root of unity, where n' greater than or equal to Omega(n(2) / k), and epsilon-approx the n-point DFT for certain inputs with descending coefficie nt magnitude. All of our results require polylogarithmic (that is, log O(1) n) depth with the same work bounds. We also provide a lower bound for a wide class of sc hemes for approximate evaluation of a degree n - 1 polynomial on the unit c ircle; namely, we prove that if a scheme uses an approximation polynomial o f degree k - 1, then it can be convergent only over a small fraction O(k/n) of the unit circle. We believe 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.