Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal (up to polylog factors) sequential and parallel algorithms for approximating complex polynomial zeros

Full text

Pdf (962 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 741 - 750

Year of Publication: 1995

ISBN:0-89791-718-9

Author

Victor Y. Pan

Math. & Computer Science Dept., Lehman College, CUNY, Bronx, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 15, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/225058.225292 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AHU	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	BFKT	Michael Ben-Or , Ephraim Feig , Dexter Kozen , Prasoon Tiwari, A fast parallel algorithm for determining all roots of a polynomial with real roots, SIAM Journal on Computing, v.17 n.6, p.1081-1092, Dec. 1988 [doi>10.1137/0217069]
	BP	Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
	BP91	Dario Bini , Victor Pan, Parallel complexity of tridiagonal symmetric Eigenvalue problem, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.384-393, January 28-30, 1991, San Francisco, California, United States
	BT	Michael Ben-Or , Prasoon Tiwari, Simple algorithms for approximating all roots of a polynomial with real roots, Journal of Complexity, v.6 n.4, p.417-442, Dec. 1990 [doi>10.1016/0885-064X(90)90032-9]
	CN	Don Coppersmith , C. Andrew Neff, Roots of a polynomial and its derivatives, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.271-279, January 23-25, 1994, Arlington, Virginia, United States
	H70	A.S. Householder, The Numerical Treatment of a Single Nonlinear Equation, McGraw-Hill, New York, 1970.
	He	Peter Henrici , William R. Kenan, Applied & computational complex analysis: power series integration conformal mapping location of zero, John Wiley & Sons, Inc., New York, NY, 1988
	KR	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	N	C. Andrew Neff, Specified precision polynomial root isolation is in NC, Journal of Computer and System Sciences, v.48 n.3, p.429-463, June 1994 [doi>10.1016/S0022-0000(05)80061-3]
	NR	C.A. Neff, J.H. Reif, An O(n2+elogb) Algorithm for the Complex Root Problem, Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science, 540-547, 1994.
	P	V. Y. Pan, Optimal and Nearly Optimal Algorithms for Approximating Polynomial Zeros, Computers & Math. (with Applics.), to appear.
	P85	Victor Y. Pan, Fast and Efficient Parallel Algorithms for the Exact Inversion of Integer Matrices, Proceedings of the Fifth Conference on Foundations of Software Technology and Theoretical Computer Science, p.504-519, December 16-18, 1985
	P87	V. Y. Pan, Sequential and Parallel Complexity of approximate Evaluation of Polynomial Zeros, Computers & Math. (with Applics.), 14, 591-622, 1987.
	P87a	V. Pan, Complexity of parallel matrix computations, Theoretical Computer Science, v.54 n.1, p.65-85, 1987 [doi>10.1016/0304-3975(87)90019-3]
	P92b	V. Y. Pan, Parametrization of Newton's Iteration for Computations with Structured Matrices and Applications, Computers & Mathematics (with Applics.), 24, 3, 61-75.
	P92c	Victor Pan, Parallel solution of Toeplitzlike linear systems, Journal of Complexity, v.8 n.1, p.1-21, March, 1992 [doi>10.1016/0885-064X(92)90031-6]
	P93e	V. Y. Pan, Concurrent Iterative Algorithm for Toeplitz-like Linear Systems, IEEE Transactions on Parallel and Distributed Systems, v.4 n.5, p.592-600, May 1993 [doi>10.1109/71.224221]
	P94	Victor Y. Pan, New techniques for approximating complex polynomial zeros, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.260-270, January 23-25, 1994, Arlington, Virginia, United States
	P94a	V. Y. Pan, New Resultant Inequalities and Complex Polynomial Factorization, SIAM Journal on Computing, v.23 n.5, p.934-950, Oct. 1994 [doi>10.1137/S0097539792235712]
	P,b	V. Y. Pan, Deterministic Improvement of Complex Polynomial Factorization Based on the Properties of the Associated Resultant, Computers & Math. (with Applics.), to appear.
	Sc	A. Schonhage, The Fundamental Theorem of Algebra in Terms of Computational Complexity, manuscript, 1982.

CITED BY 7

	Victor Y. Pan, Approximate polynomial Gcds, Padé approximation, polynomial zeros and bipartite graphs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.68-77, January 25-27, 1998, San Francisco, California, United States
	Bernard Mourrain , Victor Y. Pan, Asymptotic acceleration of solving multivariate polynomial systems of equations, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.488-496, May 24-26, 1998, Dallas, Texas, United States
	Victor Y. Pan , Zhao Q. Chen, The complexity of the matrix eigenproblem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.507-516, May 01-04, 1999, Atlanta, Georgia, United States
	Victor Y. Pan, Univariate polynomials: nearly optimal algorithms for factorization and rootfinding, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.253-267, July 2001, London, Ontario, Canada
	Victor Y. Pan, Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding, Journal of Symbolic Computation, v.33 n.5, p.701-733, May 2002
	Victor Y. Pan, Can the TPRI structure help us to solve the algebraic eigenproblem?, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Tateaki Sasaki , Akira Terui, Computing clustered close-roots of univariate polynomials, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan