P.B. Callahan and S.R. Kosaraju, A decomposition of multi-dimensional point sets with applications to k-nearest-neighbors and n-body potential fields, J. ACM 42:1 (1995), 67-90.

Digital Library

Google Scholar

[7]

J. Carrier, L. Greengard, and V. Rokhlin, A fast adaptive Multipole algorithm for particle simulations, SiAM J. Scientific and Statistical Computing 9:4 (1988), 669-686.

Digital Library

Google Scholar

[8]

C.D. Conte and C. deBoor, Elementary Numerical Analysis: An Algorithmic Approach, McGraw- Hill, NY (1980).

Digital Library

Google Scholar

[9]

j.M. Cooley, P.A. Lewis, and P.D. Welch, History of the fast Fourier transform, Proc. IEEE 55 (1967), 1675-1677.

Crossref

Google Scholar

[10]

J.M. Cooley and J.W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comp. 19 (1965), 297-301.

Crossref

Google Scholar

[11]

G. Dahlquist and A. BjSrck, Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ (1974).

Digital Library

Google Scholar

[12]

G.C. Danielson and C. Lanczos, Some improvements in practical Fourier analysis and their application to X-ray scattering from liquids, J. Franklin Institute 233 (1942), 365-380 and 435- 452.

Crossref

Google Scholar

[13]

A.L. Delcher and S.R. Kosaraju, Optimal parallel evaluation of tree-structured computations by raking, Proc. 3rd Aegean Work. on Comp. (1988), 101-110.

Digital Library

Google Scholar

[14]

A. Dutt, M. Gu, V. Rokhlin, Fast Algorithms for Polynomial Interpolation, integration and Differentiation, SIAM J. Numer. Anal., Vol. 33,No. 5, (1996), 1689-1711

Digital Library

Google Scholar

[15]

A. Dutt, Fast Fourier Transforms for Nonequispaced Data, Yale Department of Computer Science, Technical Report 980, (1993).

Google Scholar

[16]

A. Dutt, V. Rokhlin, Fast Fourier Transforms for Nonequispaced Data II, Applied and Computational Harmonic Analysis, Acedemic Press, 2, (1995), pp. 85-100.

Google Scholar

[17]

A. Edelman, P. McCorquodale, S. Toledo, The Future Fast Fourier Transform?, Eighth SIAM Conference on Parallel Processing, Minneapolis, MN, March (1997).

Google Scholar

[18]

W.D. Elliott and J.A. Board, Fast fourier transform accelerated fast multipole algorithm, SIAM J. Sci. Comput., Vol. 17, No. 2 (1996), 398-415.

Digital Library

Google Scholar

[19]

C.M. Fiduccia, Polynomial evaluation via the division algorithm- the fast Fourier transform revisited, Proc. 4th Annual ACM Symposium on Theory of Computing (1972), 88-93.

Digital Library

Google Scholar

[20]

W.M. Gentleman and G. Sande, Fast Fourier transforms for fun and profit, Proc. AFIPS 1966 Fall Joint Computer Conf. 29 (1966), 563-578.

Google Scholar

[21]

A. Gerasoulis, A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors, Math. of Computation 50:t81 (1988), 179-188.

Crossref

Google Scholar

[22]

A. Gerasoulis, M.D. Grigoriadis, and Liping Sun, A fast algorithm for Trummer's problem, SIAM J. Sci. Statist. Comput. 8 (1987), 135-138.

Digital Library

Google Scholar

[23]

I.J. Good, The interaction algorithm and practical Fourier series, J. Royal Statistics Soc. B20 (1958), 361-372. Addendum 22 (1960), 372-375.

Google Scholar

[24]

L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, J. Computational Physics 73 (1987), 325-348.

Digital Library

Google Scholar

[25]

L. Greengard and V. Rokhlin, On the efficient implementation of the fast multipole algorithm, TR RR-602, Yale Univ. Dept. of CS, (1988).

Google Scholar

[26]

P. Henrici, Applied and Computational Complex Analysis, III, Wiley, New York (1986).

Digital Library

Google Scholar

[27]

M.S. Henry, Approximation by Polynomials: Interpolation and Optimal Nodes, Math. Monthly 91:8 (1984), 497-499.

Crossref

Google Scholar

[28]

E. Horowitz, A fast method for interpolation using preconditioning, Information Processing Letters 1:4 (1972), 157-163.

Crossref

Google Scholar

[29]

H.T. Kung, Fast evaluation and interpolation, Dept. of Comp. Sci., Carnegie-Mellon Univ., Pittsburgh, PA. (1973).

Google Scholar

[30]

G.L. Miller and J.H. Reif, Parallel tree contraction part 1: Fundamentals, Chapter in Randomness and Computation S. Micali, Ed. 5 JAi Press, Greenwich, CT (1989), 47-72.

Google Scholar

[31]

R. Moenck and A.B. Borodin, Fast modular transforms via division, Conf. Record, IEEE 13th Annual Symp. on Switching and Automata Theory (i972), 90-96.

Digital Library

Google Scholar

[32]

A.C.R. Newbery, Error Analysis for Polynomial Evaluation, Math. Comp. 28:127 (197'9), 789-793.

Crossref

Google Scholar

[33]

V. Pan, Fast Evaluation and Interpolation at the Chebyshev Sets of Points, Appl. Math. Lett. 2:3 ( 1989 ), 255- 258.

Crossref

Google Scholar

[34]

V.Y. Pan, J.H. Reif, and S.R. Tate, The Power of Combining the Techniques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms, Proc. 32nd Ann. IEEE Syrup. Foundations of Computer Science, Pittsburgh, PA (1992), 703-713.

Digital Library

Google Scholar

[35]

V. Pan, A. Sadikou, E. Landowne, and O. Tiga, A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation, to appear (1996).

Google Scholar

[36]

L.R. Rabiner and C.M. Ra~er (eds.), Digital Signal Processing, IEEE Press, New York (1972).

Digital Library

Google Scholar

[37]

J.H. Reif, Approximate Complex Polynomial Evaluation in Near Constant Work Per Point, full version of this paper, in postscript (1997). http://www.cs, d u ke. ed u / ^- reiff paper/Eval, ps

Google Scholar

[38]

J.H. Reif and S.R. Tate, Fast spatial decomposition and closest pair computation for limited precision input., Tech. Rpt. No96-001, Univ. of North Texas, Dept. of Computer Science (1996). http: / / www.cs.duke.ed u/,~reif/paper / Sep.ps

Google Scholar

[39]

J.H. Reif and S.R. Tale, N-body simulation I: Fast algorithms for potential field evaluation and 7)-ummer's problem, Tech. Rpt. N-96-002, Univ. of North Texas, Dept. of Computer Science (1996). http://www.cs.duke.edu/~,reif/paper/Multipole.ps

Google Scholar

[40]

V. Rokhlin, A Fast Algorithm for the Discrete Laplace transformation, J. of Complexity 4 (1988), 12-32.

Digital Library

Google Scholar

[41]

C. Runge and H. KSnig, Die Grundlehren der mathematischen Wissenschaften, 11 (1924), Springer, Berlin.

Google Scholar

Cited By

View all

Ercegovac MMuller J(2010)An Efficient Method for Evaluating Complex PolynomialsJournal of Signal Processing Systems10.1007/s11265-008-0265-858:1(17-27)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1007/s11265-008-0265-8
Zaher Merhi Milad Ghantous Mohammad Elgamel Magdy Bayoumi Ayman El-Desouki (2007)A fully-pipelined parallel architecture for Kalman tracking filterProceedings of the 2007 IEEE International Conference on Application-Specific Systems, Architectures and Processors10.1109/ASAP.2007.4429968(81-86)Online publication date: 9-Jul-2007
https://dl.acm.org/doi/10.1109/ASAP.2007.4429968
Pan VAbu Tabanjeh MChen ZProvidence SSadikou A(2005)Transformations of Cauchy matrices, Trummer's problem and a Cauchy-like linear solverSolving Irregularly Structured Problems in Parallel10.1007/BFb0018546(274-284)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0018546
Show More Cited By

Index Terms

Approximate complex polynomial evaluation in near constant work per point
1. Mathematics of computing
  1. Mathematical analysis
  2. Mathematical software

Recommendations

Approximate Complex Polynomial Evaluation in Near Constant Work Per Point

Given the n complex coefficients of a degree n-1 complex polynomial, we wish to evaluate the polynomial at a large number $m \ge n$ of points on the complex plane. This problem is required by many algebraic computations and so is considered in most ...
Approximate polynomial GCD over integers

Symbolic numeric algorithms for polynomials are very important, especially for practical computations since we have to operate with empirical polynomials having numerical errors on their coefficients. Recently, for those polynomials, a number of ...
New Resultant Inequalities and Complex Polynomial Factorization

The author deduces some new probabilistic estimates on the distances between the zeros of a polynomial $p(x)$ by using some properties of the discriminant of $p(x)$ and applies these estimates to improve the fastest deterministic algorithm for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing

May 1997

752 pages

ISBN:0897918886

DOI:10.1145/258533

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 May 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC97

Sponsor:

SIGACT

STOC97: 29th Annual Symposium on Theory of Computing

May 4 - 6, 1997

Texas, El Paso, USA

Acceptance Rates

STOC '97 Paper Acceptance Rate 75 of 211 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
495
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)7

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ercegovac MMuller J(2010)An Efficient Method for Evaluating Complex PolynomialsJournal of Signal Processing Systems10.1007/s11265-008-0265-858:1(17-27)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1007/s11265-008-0265-8
Zaher Merhi Milad Ghantous Mohammad Elgamel Magdy Bayoumi Ayman El-Desouki (2007)A fully-pipelined parallel architecture for Kalman tracking filterProceedings of the 2007 IEEE International Conference on Application-Specific Systems, Architectures and Processors10.1109/ASAP.2007.4429968(81-86)Online publication date: 9-Jul-2007
https://dl.acm.org/doi/10.1109/ASAP.2007.4429968
Pan VAbu Tabanjeh MChen ZProvidence SSadikou A(2005)Transformations of Cauchy matrices, Trummer's problem and a Cauchy-like linear solverSolving Irregularly Structured Problems in Parallel10.1007/BFb0018546(274-284)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0018546
Pan VKarloff H(1998)Approximate polynomial Gcds, Padé approximation, polynomial zeros and bipartite graphsProceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms10.5555/314613.314649(68-77)Online publication date: 1-Jan-1998
https://dl.acm.org/doi/10.5555/314613.314649

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Approximate Complex Polynomial Evaluation in Near Constant Work Per Point

Approximate polynomial GCD over integers

New Resultant Inequalities and Complex Polynomial Factorization