Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



On efficient computation and asymptotic sharpness of Kalantari's bounds for zeros of polynomials

Author: Yi Jin
Journal: Math. Comp. 75 (2006), 1905-1912
MSC (2000): Primary 12D10, 65H05, 68Q25; Secondary 05A15, 11B37
Published electronically: June 28, 2006
MathSciNet review: 2240641
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study an infinite family of lower and upper bounds on the modulus of zeros of complex polynomials derived by Kalantari. We first give a simple characterization of these bounds which leads to an efficient algorithm for their computation. For a polynomial of degree $ n$ our algorithm computes the first $ m$ bounds in Kalantari's family in $ O(mn)$ operations. We further prove that for every complex polynomial these lower and upper bounds converge to the tightest annulus containing the roots, and thus settle a problem raised in Kalantari's paper.

References [Enhancements On Off] (What's this?)

  • 1. P. Henrici, Applied and Computational Complex Analysis, Vol. I, Wiley, New York, 1974. MR 0372162 (51:8378)
  • 2. M. D. Hirschhorn, A proof in the spirit of Zeilberger of an amazing identity of Ramanujan, Math. Mag. 69 (1996), no. 4, 267-269. MR 1424441 (97k:05019)
  • 3. B. Kalantari, An infinite family of bounds on zeros of analytic functions and relationship to Smale's bound, Math. Comp. 74 (2005), 841-852. MR 2114651 (2005k:65093)
  • 4. J. M. McNamee, A 2002 update of the supplementary bibliography on roots of polynomials, J. Comput. Appl. Math. 142 (2002), 433-434.MR 1906741
  • 5. J. M. McNamee and M. Olhovsky, A comparison of a priori bounds on (real or complex) roots of polynomials, to appear in Proceedings of 17th IMACS World Congress, Paris, France, July 2005.
  • 6. M. Mignotte, Mathematics for Computer Algebra, translated from the French by Catherine Mignotte, Springer-Verlag, New York, 1992. MR 1140923 (92i:68071)
  • 7. R. Stanley, Generating functions, in: Studies in Combinatorics, Gian-Carlo Rota, editor, Math. Asso. Amer., 1978, pp. 100-141. MR 0513004 (81i:05015)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 12D10, 65H05, 68Q25, 05A15, 11B37

Retrieve articles in all journals with MSC (2000): 12D10, 65H05, 68Q25, 05A15, 11B37

Additional Information

Yi Jin
Affiliation: Department of Computer Science, Rutgers University, New Brunswick, New Jersey 08901

Keywords: Bounds on polynomial roots, asymptotic sharpness, generating functions, recurrence relations
Received by editor(s): January 14, 2005
Received by editor(s) in revised form: August 3, 2005
Published electronically: June 28, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society