×

An adaptive subdivision method for root finding of univariate polynomials. (English) Zbl 1503.65096

Summary: The most common methods for root finding of polynomials are iterative. This type of methods shows some drawbacks, like the impossibility of parallelization, the unpredictable nature of the iterations, that prevents to search roots inside a pre-specified region of complex plane, and the moderated degree of the polynomials that they can handle. This work describes a recursive root finding method. It is based on the winding number of plane curves, that is related to the number of zeros of a polynomial in a plane region. By our previous work [Comput. Math. Appl. 67, No. 3, 555–568 (2014; Zbl 1350.65042)] we find the winding number at reasonable computational cost, so we can approximate the roots by recursive subdivision of the search region. This subdivision approach is parallelizable, with a known bound of the computational cost, and the search can be restrained, in contrast to the iterative methods. We use error returns to identify and avoid singular curves, adapting the subdivision to the roots. This allows us to handle high degree polynomials without resorting to the expensive multiprecision arithmetics of other recursive methods. A significant contribution is that we formally prove its correctness.

MSC:

65H04 Numerical computation of roots of polynomial equations

Citations:

Zbl 1350.65042
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ralston, Anthony; Rabinowitz, Philip, A first course in numerical analysis, xix+556 (1978), McGraw-Hill Book Co.: McGraw-Hill Book Co. New York, International Series in Pure and Applied Mathematics · Zbl 0976.65001
[2] Anderson, E.; Bai, Z.; Bischof, C.; Blackford, S.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Sorensen, D., LAPACK Users’ Guide (1999), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA · Zbl 0934.65030
[3] Smith, B. T.; Boyle, J. M.; Dongarra, J. J.; Garbow, B. S.; Ikebe, Y.; Klema, V. C.; Moler, C. B., Matrix eigensystem routines—EISPACK guide, ix+551 (1976), Springer-Verlag: Springer-Verlag Berlin, Lecture Notes in Computer Science, Vol. 6 · Zbl 0325.65016
[4] Fortune, Steven, An iterated eigenvalue algorithm for approximating roots of univariate polynomials, J. Symbolic Comput., 33, 5, 627-646 (2002), Computer algebra (London, ON, 2001) · Zbl 1004.65060
[5] Wilkinson, J. H., The Algebraic Eigenvalue Problem, xviii+662 (1965), Clarendon Press, Oxford · Zbl 0626.65029
[6] Pan, Victor Y., Solving a polynomial equation: some history and recent progress, SIAM Rev., 39, 2, 187-220 (1997) · Zbl 0873.65050
[7] Bini, Dario A.; Robol, Leonardo, Solving secular and polynomial equations: A multiprecision algorithm, J. Comput. Appl. Math., 272, 276-292 (2014) · Zbl 1310.65052
[8] Pan, Victor Y.; Tsigaridas, Elias, Accelerated approximation of the complex roots and factors of a univariate polynomial, Theoret. Comput. Sci., 681, 138-145 (2017) · Zbl 1375.65066
[9] Yap, Chee K.; Sagraloff, Michael, A simple but exact and efficient algorithm for complex root isolation, Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, 353-360 (2011), ACM · Zbl 1323.65051
[10] García Zapata, J. L.; Díaz Martín, J. C., Finding the number of roots of a polynomial in a plane region using the winding number, Comput. Math. Appl., 67, 3, 555-568 (2014) · Zbl 1350.65042
[11] García Zapata, J. L.; Díaz Martín, J. C., A geometric algorithm for winding number computation with complexity analysis, J. Complexity, 28, 320-345 (2012) · Zbl 1262.65057
[12] Henrici, Peter, (Applied and Computational Complex Analysis. vol. 1. Applied and Computational Complex Analysis. vol. 1, Wiley Classics Library (1988), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York), xviii+682, Power series—integration—conformal mapping—location of zeros, Reprint of the 1974 original, A Wiley-Interscience Publication · Zbl 0635.30001
[13] Henrici, Peter, Methods of search for solving polynomial equations, J. Assoc. Comput. Mach., 17, 273-283 (1970) · Zbl 0222.65057
[14] Herman, Aaron; Hong, Hoon; Tsigaridas, Elias, Improving root separation bounds, J. Symbolic Comput., 84, 25-56 (2018) · Zbl 1415.26005
[15] Kolmogorov, A. N.; Fomı̄n, S. V., Introductory real analysis, xii+403 (1975), Dover Publications Inc.: Dover Publications Inc. New York, Translated from the second Russian edition and edited by Richard A. Silverman, Corrected reprinting
[16] Burstall, R. M., Proving properties of programs by structural induction, Comput. J., 12, 1, 41-48 (1969) · Zbl 0164.46202
[17] Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D., Introduction to Automata Theory, Languages, and Computation (2000), Addison Wesley · Zbl 0980.68066
[18] Ying, Xingren; Katz, I. Norman, A reliable argument principle algorithm to find the number of zeros of an analytic function in a bounded domain, Numer. Math., 53, 1-2, 143-163 (1988) · Zbl 0628.65015
[19] Renegar, James, On the worst-case arithmetic complexity of approximating zeros of polynomials, J. Complexity, 3, 2, 90-113 (1987) · Zbl 0642.65031
[20] Arnold Schönhage, The fundamental theorem of algebra in terms of computational complexity, Technical report, Mathematisches Institut Universität Tübingen, 1982.; Arnold Schönhage, The fundamental theorem of algebra in terms of computational complexity, Technical report, Mathematisches Institut Universität Tübingen, 1982.
[21] Neff, C. Andrew; Reif, John H., An efficient algorithm for the complex roots problem, J. Complexity, 12, 2, 81-115 (1996) · Zbl 0888.12005
[22] Pan, Victor Y., Univariate polynomials: Nearly optimal algorithms for numerical factorization and rootfinding, J. Symbolic Comput., 33, 2002 (2001) · Zbl 1356.65125
[23] Knuth, Donald Ervin, Axioms and Hulls (1992), springer-Verlag Berlin
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.