×

A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration. (English) Zbl 1383.65043

Summary: We describe a subdivision algorithm for isolating the complex roots of a polynomial \(F\in\mathbb{C}[x]\). Given an oracle that provides approximations of each of the coefficients of \(F\) to any absolute error bound and given an arbitrary square \(\mathcal{B}\) in the complex plane containing only simple roots of \(F\), our algorithm returns disjoint isolating disks for the roots of \(F\) in \(\mathcal{B}\).
Our complexity analysis bounds the absolute error to which the coefficients of \(F\) have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square \(\mathcal{B}\), namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem, namely, to isolate all the roots of a polynomial of degree \(n\) with integer coefficients of bit size less than \(\tau\), our algorithm needs \(\tilde{O}(n^3+n^2\tau)\) bit operations, which is comparable to the record bound of V. Y. Pan [ibid. 33, No. 5, 701–733 (2002; Zbl 1004.65061)]. It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage’s splitting circle technique.
Our algorithm uses the quadtree construction of H. Weyl [Math. Z. 20, 131–150 (1924; JFM 50.0037.02)] with two key ingredients: using Pellet’s theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder’s modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from [J. Abbott, ACM Commun. Comput. Algebra 48, No. 1, 3–12 (2014; Zbl 1314.65068)], we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm.

MSC:

65H04 Numerical computation of roots of polynomial equations
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
65Y20 Complexity and performance of numerical algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abbott, J., Quadratic interval refinement for real roots, ACM Commun. Comput. Algebra, 28, 3-12 (2014), Poster presented at the International Symposium on Symbolic and Algebraic Computation (ISSAC), 2006 · Zbl 1314.65068
[2] Akritas, A. G.; Strzeboński, A., A comparative study of two real root isolation methods, Nonlinear Anal., 10, 4, 297-304 (2005) · Zbl 1147.65310
[3] Becker, R., The Bolzano Method to Isolate the Real Roots of a Bitstream Polynomial (2012), Saarland University: Saarland University Saarbrücken, Germany, Bachelor thesis
[4] Best, G., Notes on the Graeffe method of root squaring, Am. Math. Mon., 56, 2, 91-94 (1949) · Zbl 0032.17001
[5] Bini, D.; Fiorentino, G., Design, analysis, and implementation of a multiprecision polynomial rootfinder, Numer. Algorithms, 23, 127-173 (2000) · Zbl 1018.65061
[6] Bini, D. A.; Robol, L., Solving secular and polynomial equations: a multiprecision algorithm, J. Comput. Appl. Math., 272, 276-292 (2014) · Zbl 1310.65052
[7] Burr, M.; Krahmer, F., Sqfreeeval: an (almost) optimal real-root isolation algorithm, J. Symb. Comput., 47, 2, 153-166 (2012) · Zbl 1269.65046
[8] Collins, G. E., Continued fraction real root isolation using the Hong bound, J. Symb. Comput., 72, 21-54 (2016) · Zbl 1329.65094
[9] Collins, G. E.; Akritas, A. G., Polynomial real root isolation using Descartes’ rule of signs, (Symposium on Symbolic and Algebraic Computation (SYMSAC) (1976)), 272-275
[10] Collins, G. E.; Krandick, W., An efficient algorithm for infallible polynomial complex root isolation, (Papers from the International Symposium on Symbolic and Algebraic Computation. Papers from the International Symposium on Symbolic and Algebraic Computation, ISSAC ’92 (1992), ACM: ACM New York, NY, USA), 189-194 · Zbl 0964.68582
[11] Davenport, J. H., Computer Algebra for Cylindrical Algebraic Decomposition (1985), Reprinted as Tech. Report 88-10. School of Mathematical Sci., U. of Bath, Claverton Down, Bath BA2 7AY, England
[12] Du, Z.; Sharma, V.; Yap, C. K., Amortized Bound for Root Isolation via Sturm Sequences, 113-129 (2007), Birkhäuser Basel: Birkhäuser Basel Basel · Zbl 1152.65426
[13] Eigenwillig, A., Real Root Isolation for Exact and Approximate Polynomials Using Descartes’ Rule of Signs (2008), Saarland University, PhD thesis
[14] Eigenwillig, A.; Kettner, L.; Krandick, W.; Mehlhorn, K.; Schmitt, S.; Wolpert, N., A Descartes Algorithm for Polynomials with Bit-Stream Coefficients, 138-149 (2005), Springer: Springer Berlin, Heidelberg · Zbl 1169.65315
[15] Emiris, I. Z.; Pan, V. Y.; Tsigaridas, E. P., Algebraic algorithms, (Computing Handbook, Third Edition: Computer Science and Software Engineering (2014)), pages 10: 1-30
[16] Fortune, S., An iterated eigenvalue algorithm for approximating roots of univariate polynomials, J. Symb. Comput., 33, 5, 627-646 (2002) · Zbl 1004.65060
[17] Giusti, M.; Lecerf, G.; Salvy, B.; Yakoubsohn, J.-C., On location and approximation of clusters of zeros of analytic functions, Found. Comput. Math., 5, 3, 257-311 (2005) · Zbl 1109.65046
[18] Henrici, P., Applied and Computational Complex Analysis, Volume 1: Power Series Integration Conformal Mapping Location of Zero, Pure Appl. Math (1974), J. Wiley & Sons · Zbl 0313.30001
[19] Householder, A. S., Dandelin, Lobacevskii, or Graeffe, Am. Math. Mon., 66, 6, 464-466 (1959) · Zbl 0089.24202
[20] Kerber, M.; Sagraloff, M., Root refinement for real polynomials using quadratic interval refinement, J. Comput. Appl. Math., 280, 377-395 (2015), A preliminary version appeared in the Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), 2011 · Zbl 1309.65052
[21] Kirrinnis, P., Partial fraction decomposition in C(z) and simultaneous Newton iteration for factorization in C[z], J. Complex., 14, 3, 378-444 (1998) · Zbl 0934.12005
[22] Kobel, A.; Rouillier, F.; Sagraloff, M., Computing real roots of real polynomials ... and now for real!, (Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2016, Waterloo, ON, Canada, July 19-22, 2016 (2016)), 303-310 · Zbl 1365.65142
[23] Kobel, A.; Sagraloff, M., Fast approximate polynomial multipoint evaluation and applications (2013), CORR
[24] McNamee, J. M., A 2002 update of the supplementary bibliography on roots of polynomials, J. Comput. Appl. Math., 142, 2, 433-434 (2002) · Zbl 1002.65056
[25] McNamee, J. M., Numerical Methods for Roots of Polynomials, Stud. Comput. Math., vol. 1 (2007), Elsevier Science · Zbl 1143.65002
[26] McNamee, J. M.; Pan, V. Y., Efficient polynomial root-refiners: a survey and new record efficiency estimates, Comput. Math. Appl., 63, 1, 239-254 (2012) · Zbl 1238.65044
[27] McNamee, J. M.; Pan, V. Y., Numerical Methods for Roots of Polynomials, Stud. Comput. Math., vol. 2 (2013), Elsevier Science · Zbl 1279.65053
[28] Mehlhorn, K.; Sagraloff, M.; Wang, P., From approximate factorization to root isolation with application to cylindrical algebraic decomposition, J. Symb. Comput., 66, 34-69 (2015), A preliminary version appeared in the Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC), 2013 · Zbl 1357.68305
[29] Mourrain, B., Tsigaridas, E.P., 2009. On the complexity of complex root isolation. In: Proc. 10th Int. Symp. on Effective Methods in Algebraic Geometry (MEGA), Barcelona, Spain.; Mourrain, B., Tsigaridas, E.P., 2009. On the complexity of complex root isolation. In: Proc. 10th Int. Symp. on Effective Methods in Algebraic Geometry (MEGA), Barcelona, Spain.
[30] Mourrain, B.; Vrahatis, M.; Yakoubsohn, J., On the complexity of isolating real roots and computing with certainty the topological degree, J. Complex., 18, 2, 612-640 (2002) · Zbl 1008.65022
[31] Neff, C.; Reif, J. H., An efficient algorithm for the complex roots problem, J. Complex., 12, 2, 81-115 (1996) · Zbl 0888.12005
[32] Pan, V. Y., Solving a polynomial equation: some history and recent progress, SIAM Rev., 39, 2, 187-220 (1997) · Zbl 0873.65050
[33] Pan, V. Y., Approximating complex polynomial zeros: modified Weyl’s quadtree construction and improved Newton’s iteration, J. Complex., 16, 1, 213-264 (2000) · Zbl 1041.65043
[34] Pan, V., Univariate polynomials: nearly optimal algorithms for numerical factorization and root finding, J. Symb. Comput., 33, 5, 701-733 (2002) · Zbl 1004.65061
[35] Pan, V. Y.; Tsigaridas, E. P., On the Boolean complexity of real root refinement, (Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC ’13 (2013), ACM: ACM New York, NY, USA), 299-306 · Zbl 1360.65140
[36] Pan, V. Y.; Tsigaridas, E. P., Accelerated approximation of the complex roots of a univariate polynomial, (Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, SNC ’14 (2014), ACM: ACM New York, NY, USA), 132-134 · Zbl 1345.65034
[37] Pawlowski, P., The location of the zeros of the higher order derivatives of a polynomial, Proc. Am. Math. Soc., 127, 5, 1493-1497 (1999) · Zbl 0960.30005
[38] Pinkert, J. R., An exact method for finding the roots of a complex polynomial, ACM Trans. Math. Softw., 2, 4, 351-363 (Dec. 1976)
[39] Rahman, Q.; Schmeisser, G., Analytic Theory of Polynomials, London Math. Soc. Monogr. Ser (2002), Clarendon Press · Zbl 1072.30006
[40] Renegar, J., On the worst-case arithmetic complexity of approximating zeros of polynomials, J. Complex., 3, 2, 90-113 (1987) · Zbl 0642.65031
[41] Rouillier, F.; Zimmermann, P., Efficient isolation of polynomial’s real roots, Proceedings of the International Conference on Linear Algebra and Arithmetic 2001. Proceedings of the International Conference on Linear Algebra and Arithmetic 2001, J. Comput. Appl. Math., 162, 1, 33-50 (2004) · Zbl 1040.65041
[42] Sagraloff, M., When Newton meets Descartes: a simple and fast algorithm to isolate the real roots of a polynomial, (Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation, ISSAC ’12 (2012), ACM: ACM New York, NY, USA), 297-304 · Zbl 1323.65050
[43] Sagraloff, M., A near-optimal algorithm for computing real roots of sparse polynomials, (Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14 (2014), ACM: ACM New York, NY, USA), 359-366 · Zbl 1325.65068
[44] Sagraloff, M., On the complexity of the Descartes method when using approximate arithmetic, J. Symb. Comput., 65, 0, 79-110 (2014) · Zbl 1321.65080
[45] Sagraloff, M.; Mehlhorn, K., Computing real roots of real polynomials, J. Symb. Comput., 73, 46-86 (2016) · Zbl 1330.65072
[46] Sagraloff, M.; Yap, C. K., A simple but exact and efficient algorithm for complex root isolation, (Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ISSAC ’11 (2011), ACM: ACM New York, NY, USA), 353-360 · Zbl 1323.65051
[47] Schönhage, A., Asymptotically fast algorithms for the numerical multiplication and division of polynomials with complex coefficients, (Calmet, J., Computer Algebra. Computer Algebra, EUROCAM ’82, European Computer Algebra Conference, Marseille, France, 5-7 April, 1982. Computer Algebra. Computer Algebra, EUROCAM ’82, European Computer Algebra Conference, Marseille, France, 5-7 April, 1982, Lect. Notes Comput. Sci., vol. 144 (1982), Springer), 3-15
[48] Schönhage, A., The Fundamental Theorem of Algebra in Terms of Computational Complexity (1982), Math. Inst. Univ. Tübingen, Technical report
[49] Schröder, E., Über unendliche viele Algorithmen zur Auflösung der Gleichungen, Math. Ann., 2, 317-365 (1870)
[50] Sharma, V., Complexity of real root isolation using continued fractions, Theor. Comput. Sci., 409, 292-310 (2008) · Zbl 1158.68055
[51] Sharma, V.; Batra, P., Near optimal subdivision algorithms for real root isolation, (Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC ’15 (2015), ACM: ACM New York, NY, USA), 331-338 · Zbl 1345.65035
[52] Strzeboński, A., Real root isolation for exp-log-arctan functions, J. Symb. Comput., 47, 3, 282-314 (2012) · Zbl 1244.65070
[53] Tsigaridas, E. P., Improved bounds for the cf algorithm, Theor. Comput. Sci., 479, 120-126 (2013) · Zbl 1291.68436
[54] Tsigaridas, E. P.; Emiris, I. Z., On the complexity of real root isolation using continued fractions, Theor. Comput. Sci., 392, 1-3, 158-173 (2008) · Zbl 1134.68067
[55] Turán, P.; Halâasz, G.; Pintz, J., On a New Method of Analysis and Its Applications (1984), A Wiley-Interscience Publication, Wiley-Interscience
[56] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1055.68168
[57] Weyl, H., Randbemerkungen zu Hauptproblemen der Mathematik. II. Fundamentalsatz der Algebra and Grundlagen der Mathematik, Math. Z., 20, 131-151 (1924) · JFM 50.0064.03
[58] Wilf, H. S., A global bisection algorithm for computing the zeros of polynomials in the complex plane, J. ACM, 25, 3, 415-420 (July 1978)
[59] Yakoubsohn, J.-C., Finding a cluster of zeros of univariate polynomials, J. Complex., 16, 3, 603-638 (2000) · Zbl 0974.65045
[60] Yakoubsohn, J.-C., Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions, J. Complex., 21, 5, 652-690 (2005) · Zbl 1084.65055
[61] Yap, C. K., Fundamental Problems of Algorithmic Algebra (2000), Oxford University Press · Zbl 0999.68261
[62] Yap, C.; Sagraloff, M.; Sharma, V., Analytic root clustering: a complete algorithm using soft zero tests, (Bonizzoni, P.; Brattka, V.; Löwe, B., The Nature of Computation. Logic, Algorithms, Applications - 9th Conference on Computability in Europe. The Nature of Computation. Logic, Algorithms, Applications - 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. The Nature of Computation. Logic, Algorithms, Applications - 9th Conference on Computability in Europe. The Nature of Computation. Logic, Algorithms, Applications - 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013, Lect. Notes Comput. Sci., vol. 7921 (2013), Springer), 434-444 · Zbl 1416.65068
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.