Real root-finding

ABSTRACT

In this paper we seek all real roots of a polynomial with real coefficients and real and nonreal roots. Somewhat paradoxically, one of the most effective solutions is by approximating these real roots semi-numerically together with all nonreal roots. Alternative methods are symbolic, based on Descartes' rule of signs (which can be combined with the continued fraction approximation algorithm) or the Sturm (or Sturm-Habicht) sequences. We combine various old and new techniques to devise semi-numerical algorithms that are effective where the real roots do not lie near the nonreal ones.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: R. P. Brent, Algorithms for Minimization Without Derivatives, Prentice-Hall, Englewood Cliffs, New Jersey, 1973.
• 3: D. A. Bini, G. Fiorentino, Design, Analysis, and Implementation of a Multiprecision Polynomial Rootfinder, Numerical Algorithms, 23, 127--173, 2000.
• 4: D. A. Bini, L. Gemignani, B. Meini, Computations with Infinite Toeplitz Matrices and Polynomials, Linear Algebra and Its Applications, 343--344, 21--61, 2002.
• 5: D. A. Bini, L. Gemignani, V. Y. Pan, Inverse Power and Durand/Kerner Iteration for Univariate Polynomial Root-finding, Computers and Mathematics (with Applications), 47, 2/3, 447--459, 2004. (Also Technical Report TR 2002 020, CUNY Ph.D. Program in Computer Science, Graduate Center, City University of New York, 2002.)
• 6: Dario A. Bini , Luca Gemignani , Victor Y. Pan, Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations, Numerische Mathematik, v.100 n.3, p.373-408, May 2005 [doi>10.1007/s00211-005-0595-4]
• 7: D. A. Bini, L. Gemignani, V. Y. Pan, Improved Initialization of the Accelerated and Robust QR-like Polynomial Root-finding, Electronic Transactions on Numerical Analysis, 17, 195--205, 2004.
• 8: 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]
• 9: Dario Bini , Victor Y. Pan, Computing Matrix Eigenvalues and Polynomial Zeros Where the Output is Real, SIAM Journal on Computing, v.27 n.4, p.1099-1115, Aug. 1998 [doi>10.1137/S0097539790182482]
• 10: C. Carstensen, Linear Construction of Companion Matrices, Linear Algebra and Its Applications, 149, 191--214, 1991.
• 11: George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806346]
• 12: Frédéric Cazals , Jean-Charles Faugère , Marc Pouget , Fabrice Rouillier, The implicit structure of ridges of a smooth parametric surface, Computer Aided Geometric Design, v.23 n.7, p.582-598, October 2006 [doi>10.1016/j.cagd.2006.04.002]
• 13: George E. Collins , Rudiger Loos, Real zeroes of polynomials, Computer algebra: symbolic and algebraic computation (2nd ed.), Springer-Verlag New York, Inc., New York, NY, 1983
• 14: Qiang Du , Ming Jin , T. Y. Li , Z. Zeng, Quasi-Laguerre Iteration in Solving Symmetric Tridiagonal Eigenvalue Problems, SIAM Journal on Scientific Computing, v.17 n.6, p.1347-1368, Nov. 1996 [doi>10.1137/S1064827594273225]
• 15: Qiang Du , Ming Jin , T. Y. Li , Z. Zeng, The quasi-Laguerre iteration, Mathematics of Computation, v.66 n.217, p.345-361, Jan. 1997 [doi>10.1090/S0025-5718-97-00786-2]
• 16: Z. Du, V. Sharma, C. K. Yap, Amortized Bound for Root Isolation via Sturm Sequences, Chapter 8, pages 105--121 in Symbolic Numeric Computing (D. Wang and L. Zhi, editors), Birkhäuser, Basel/Boston, 2007.
• 17: I. Z. Emiris , A. Kakargias , S. Pion , M. Teillaud , E. P. Tsigaridas, Towards and open curved kernel, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997882]
• 18: I. Z. Emiris, B. Mourrain, E. P. Tsigaridas, Real Algebraic Numbers: Compexity Analysis and Experimentation, in Reliable Implementations of Real Number Algorithms: Theory and Practice, P. Hertling, C. Hoffmann, W. Luther, N. Revol editors, LNCS, Springer (to appear), also available in www.inria.fr/rrrt/rr-5897.html, 2007.
• 19: Steven Fortune, An iterated eigenvalue algorithm for approximating roots of univariate polynomials, Journal of Symbolic Computation, v.33 n.5, p.627-646, May 2002 [doi>10.1006/jsco.2002.0526]
• 20: M. Fiedler, Expressing a Polynomial As the Characteristic Polynomial of a Symmetric Matrix, Linear Algebra and Its Applications, 141, 265--270, 1990.
• 21: L. V. Foster, Generalization of Laguerre's Method: Higher Order Methods, SIAM J. on Numerical Analysis, 18, 6, 1004--1018, 1981.
• 22: G. H. Golub, C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, Maryland, 1996 (third addition).
• 23: P. Henrici, Applied and Computational Complex Analysis, 1, John Wiley, New York, 1974.
• 24: Hoon Hong, Bounds for absolute positiveness of multivariate polynomials, Journal of Symbolic Computation, v.25 n.5, p.571-585, May 1998 [doi>10.1006/jsco.1997.0189]
• 25: E. Hansen, M. Patrick, J. Rusnack, Some Modification of Laguerre's Method, BIT, 17, 409--417, 1977.
• 26: J. R. Johnson, Algorithms for Polynomial Real Root Isolation, Quantifier Elimination and Cylindrical Algebraic Decomposition, (B. Caviness and J. R. Johnson, editors), 269--299, Springer, 1998.
• 27: W. Krandick, Isolierung reeller Nullstellen von Polynomen, In Wissenschaftliches Rechnen (J. Herzberger, editor), 105--154, Akademie Verlag, Berlin, 1995.
• 28: Peter Kirrinnis, Partial fraction decomposition in Cz and simultaneous Newton iteration for factorization in Cz , Journal of Complexity, v.14 n.3, p.378-444, Sept. 1, 1998 [doi>10.1006/jcom.1998.0481]
• 29: Bernard Mourrain , Jean-Pierre Técourt , Monique Teillaud, On the computation of an arrangement of quadrics in 3D, Computational Geometry: Theory and Applications, v.30 n.2, p.145-164, February 2005 [doi>10.1016/j.comgeo.2004.05.003]
• 30: John Michael McNamee, A bibliography on roots of polynomials, Journal of Computational and Applied Mathematics, v.47 n.3, p.391-394, Sept. 30, 1993 [doi>10.1016/0377-0427(93)90064-I]
• 31: J. M. McNamee, A Supplementary Bibliography on Roots of Polynomials, J. Computational and Applied Mathematics, 78, 1, 1997.
• 32: John M. McNamee, An updated supplementary bibliography on roots of polynomials, Journal of Computational and Applied Mathematics, v.110 n.2, p.305-306, Oct. 1999 [doi>10.1016/S0377-0427(99)00273-3]
• 33: John Michael McNamee, A 2002 update of the supplementary bibliography on roots of polynomials, Journal of Computational and Applied Mathematics, v.142 n.2, p.433-434, 15 May 2002
• 34: F. Malek, R. Vaillancourt, Polynomial Zerofinding Iterative Matrix Algorithms, Computers and Math. with Applications, 29,1, 1--13, 1995.
• 35: F. Malek, R. Vaillancourt, A Composite Polynomial Zerofinding Matrix Algorithm, Computers and Math. with Applications, 30,2, 37--47, 1995.
• 36: V. Y. Pan, An Algebraic Approach to Approximate Evaluation of a Polynomial on a Set of Real Points, Advances in Computational Mathematics, 3, 41--58, 1995.
• 37: Victor Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Review, v.39 n.2, p.187-220, June 1997 [doi>10.1137/S0036144595288554]
• 38: Victor Y. Pan, Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration, Journal of Complexity, v.16 n.1, p.213-264, March 2000 [doi>10.1006/jcom.1999.0532]
• 39: Victor Y. Pan, Structured matrices and polynomials: unified superfast algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 40: 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 [doi>10.1006/jsco.2002.0531]
• 41: B. Parlett, Laguerre's Method Applied to the Matrix Eigenvalue Problem, Math. of Computation, 18, 464--485, 1964.
• 42: Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 43: V. Y. Pan, M. Abu Tabanjeh, Z. Q. Chen, E. Landowne, A. Sadikou, New Transformations of Cauchy Matrices and Trummer's Problem, Computers & Mathematics (with Applications), 35, 12, 1--5, 1998.
• 44: V. Y. Pan, D. Ivolgin, B. Murphy, R. E. Rosholt, Y. Tang, X. Wang, X. Yan, Root-finding with Eigen-solving, Chapter 14, pages 219--245 in Symbolic-Numeric Computation, (Dongming Wang and Li-Hong Zhi, editors), Birkhäuser, Basel/Boston, 2007.
• 45: Victor Y. Pan , Myong-Hi Kim , Akimou Sadikou , Xiaohan Huang , Ailong Zheng, On isolation of real and nearly real zeros of a univariate polynomial and its splitting into factors, Journal of Complexity, v.12 n.4, p.572-594, Dec. 1996 [doi>10.1006/jcom.1996.0034]
• 46: V. Y. Pan, A. Zheng, X. Huang, Y. Yu, Fast Multipoint Polynomial Evaluation and Interpolation via Computation with Structured Matrices, Annals of Numerical Math., 4, 483--510, 1997.
• 47: James Renegar, On the worst-case arithmetic complexity of approximating zeros of polynomials, Journal of Complexity, v.3 n.2, p.90-113, June 1987 [doi>10.1016/0885-064X(87)90022-7]
• 48: Fabrice Rouillier , Paul Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, v.162 n.1, p.33-50, 1 January 2004 [doi>10.1016/j.cam.2003.08.015]
• 49: A. Schönhage, The Fundamental Theorem of Algebra in Terms of Computational Complexity, Mathematics Department, University of Tübingen, Germany, 1982.
• 50: G. W. Stewart, Matrix algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 51: A. Terui and T. Sasaki, Durand-Kerner Method for the Real Roots, Japan J. Indust. Appl. Math., 19, 1, 19--38, 2002.
• 52: X. Zou, Analysis of the Quasi-Laguerre Method, Numerische Math., 82, 491--519, 1999.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations

General Terms:
Algorithms

Keywords:
real roots, root-finding, univariate polynomials