Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schoenhage in 1982. The main drawbacks of Pan's method are that it is quite involved and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted ANEWDSC, which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. ANEWDSC can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task.
Many algorithms for approximate factorization and root isolation are known, see @cite_12 @cite_37 @cite_33 @cite_15 for surveys. The algorithms can be roughly split into two groups: There are iterative methods for simultaneously approximating all roots (or a single root if a sufficiently good approximation is already known); there are subdivision methods that start with a region containing all the roots of interest, subdivide this region according to certain rules, and use inclusion- and exclusion-predicates to certify that a region contains exactly one root or no root. Prominent examples of the former group are the Aberth-Ehrlich method (used for @cite_0 ) and the Weierstrass-Durand-Kerner method. These algorithms work well in practice and are widely used. However, a complexity analysis and global convergence proof is missing. Prominent examples of the second group are the Descartes method @cite_28 @cite_40 @cite_1 @cite_36 , the Bolzano method @cite_19 @cite_31 , the Sturm method @cite_8 , the continued fraction method @cite_44 @cite_21 @cite_23 , and the splitting circle method @cite_27 @cite_29 .
@cite_37 @cite_31 @cite_33 @cite_8 @cite_28 @cite_36 @cite_29 @cite_21 @cite_1 @cite_0 @cite_19 @cite_40 @cite_44 @cite_27 @cite_23 @cite_15 @cite_12
627545049 74955198 2144619406 2048184489 2084184830 1511166374 2099287615 2138897906 2168222442 1995250895 1531175519
Numerical Methods for Roots of Polynomials - Part II along with Part I (9780444527295) covers most of the traditional methods for polynomial root-finding such as interpolation and methods due to Graeffe, Laguerre, and Jenkins and Traub. It includes many other methods and topics as well and has a chapter devoted to certain modern virtually optimal methods. Additionally, there are pointers to robust and efficient programs. This book is invaluable to anyone doing research in polynomial roots, or teaching a graduate course on that topic. It is the first comprehensive treatment of Root-Finding in several decades with a description of high-grade software and where it can be downloaded. It offers a long chapter on matrix methods and includes Parallel methods and errors where appropriate. It proves invaluable for research or graduate course. This paper presents two results on the complexity of root isolation via Sturm sequences. Both results exploit amortization arguments. To approximate all roots (zeros) of a univariate polynomial, we develop two effective algorithms and combine them in a single recursive process. One algorithm computes a basic well isolated zero-free annulus on the complex plane, whereas another algorithm numerically splits the input polynomial of the nth degree into two factors balanced in the degrees and with the zero sets separated by the basic annulus, Recursive combination of the two algorithms leads to computation of the complete numerical factorization of a polynomial into the product of linear factors and further to the approximation of the roots. The new root-finder incorporates the earlier techniques of Schonhage, Neff Reif, and Kirrinnis and our old and new techniques and yields nearly optimal (up to polylogarithmic factors) arithmetic and Boolean cost estimates for the computational complexity of both complete factorization and root-finding. The improvement over our previous record Boolean complexity estimates is by roughly the factor of n for complete factorization and also for the approximation of well-conditioned (well isolated) roots, whereas the same algorithm is also optimal (under both arithmetic and Boolean models of computing) for the worst case input polynomial, whose roots can be ill-conditioned, forming clusters. (The worst case complexity bounds for root-finding are supported by our previous algorithms as well.) All algorithms allow processor efficient acceleration to achieve solution in polylogarithmic parallel time. In this paper, we provide polynomial bounds on the worst case bit-complexity of two formulations of the continued fraction algorithm. In particular, for a square-free integer polynomial of degree n with coefficients of bit-length L, we show that the bit-complexity of Akritas' formulation is O@?(n^8L^3), and the bit-complexity of a formulation by Akritas and Strzebonski is O@?(n^7L^2); here O@? indicates that we are omitting logarithmic factors. The analyses use a bound by Hong to compute the floor of the smallest positive root of a polynomial, which is a crucial step in the continued fraction algorithm. We also propose a modification of the latter formulation that achieves a bit-complexity of O@?(n^5L^2). Let f be a univariate polynomial with real coefficients, f@?R[X]. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the real roots of f in a given interval. In this paper, we consider a simple subdivision algorithm whose primitives are purely numerical (e.g., function evaluation). The complexity of this algorithm is adaptive because the algorithm makes decisions based on local data. The complexity analysis of adaptive algorithms (and this algorithm in particular) is a new challenge for computer science. In this paper, we compute the size of the subdivision tree for the SqFreeEVAL algorithm. The SqFreeEVAL algorithm is an evaluation-based numerical algorithm which is well-known in several communities. The algorithm itself is simple, but prior attempts to compute its complexity have proven to be quite technical and have yielded sub-optimal results. Our main result is a simple O(d(L+lnd)) bound on the size of the subdivision tree for the SqFreeEVAL algorithm on the benchmark problem of isolating all real roots of an integer polynomial f of degree d and whose coefficients can be written with at most L bits. Our proof uses two amortization-based techniques: first, we use the algebraic amortization technique of the standard Mahler-Davenport root bounds to interpret the integral in terms of d and L. Second, we use a continuous amortization technique based on an integral to bound the size of the subdivision tree. This paper is the first to use the novel analysis technique of continuous amortization to derive state of the art complexity bounds. Collins und Akritas (1976) have described the Descartes method for isolating the real roots of an integer polynomial in one variable. This method recursively subdivides an initial interval until Descartes' Rule of Signs indicates that all roots have been isolated. The partial converse of Descartes' Rule by Obreshkoff (1952) in conjunction with the bound of Mahler (1964) and Davenport (1985) leads us to an asymptotically almost tight bound for the resulting subdivision tree. It implies directly the best known complexity bounds for the equivalent forms of the Descartes method in the power basis (Collins Akritas, 1976), the Bernstein basis (Lane Riesenfeld, 1981) and the scaled Bernstein basis (Johnson, 1991), which are presented here in a unified fashion. Without losing correctness of the output, we modify the Descartes method such that it can handle bitstream coefficients, which can be approximated arbitrarily well but cannot be determined exactly. We analyze the computing time and precision requirements. The method described elsewhere by the author together with Kerber Wolpert (2007) and Kerber (2008) to determine the arrangement of plane algebraic curves rests in an essential way on variants of the bitstream Descartes algorithm; we analyze a central part of it. Collins und Akritas (1976) haben das Descartes-Verfahren zur Einschliesung der reellen Nullstellen eines ganzzahligen Polynoms in einer Veranderlichen angegeben. Das Verfahren unterteilt rekursiv ein Ausgangsintervall, bis die Descartes'sche Vorzeichenregel anzeigt, dass alle Nullstellen getrennt worden sind. Die partielle Umkehrung der Descartes'schen Regel nach Obreschkoff (1952) in Verbindung mit der Schranke von Mahler (1964) und Davenport (1985) fuhrt uns auf eine asymptotisch fast scharfe Schranke fur den sich ergebenden Unterteilungsbaum. Daraus folgen direkt die besten bekannten Komplexitatsschranken fur die aquivalenten Formen des Descartes-Verfahrens in der Monom-Basis (Collins Akritas, 1976), der Bernstein-Basis (Lane Riesenfeld, 1981) und der skalierten Bernstein-Basis (Johnson, 1991), die hier vereinheitlicht dargestellt werden. Ohne dass die Korrektheit der Ausgabe verloren geht, modifizieren wir das Descartes-Verfahren so, dass es mit "Bitstream"-Koeffizienten umgehen kann, die beliebig genau angenahert, aber nicht exakt bestimmt werden konnen. Wir analysieren die erforderliche Rechenzeit und Prazision. Das vom Verfasser mit Kerber Wolpert (2007) und Kerber (2008) an anderer Stelle beschriebene Verfahren zur Bestimmung des Arrangements (der Schnittfigur) ebener algebraischer Kurven fust wesentlich auf Varianten des Bitstream-Descartes-Verfahrens; wir analysieren einen zentralen Teil davon. Recent progress in polynomial elimination has rendered the computation of the real roots of ill-conditioned polynomials of high degree (over 1000) with huge coefficients (several thousand digits) a critica l operation in computer algebra. To rise to the occasion, the only method-candidate that has been considered by various authors for modification and improvement has been th e Collins-Akritas bisection method (1), which is a based on a variation of Vincent's theor em (2). The most recent example is the paper by Rouillier and Zimmermann (3), where the authors present We present algorithmic, complexity and implementation results concerning real root isolation of integer univariate polynomials using the continued fraction expansion of real algebraic numbers. One motivation is to explain the method's good performance in practice. We derive an expected complexity bound of [email protected]?"B(d^6+d^[email protected]^2), where d is the polynomial degree and @t bounds the coefficient bit size, using a standard bound on the expected bit size of the integers in the continued fraction expansion, thus matching the current worst-case complexity bound for real root isolation by exact methods (Sturm, Descartes and Bernstein subdivision). Moreover, using a homothetic transformation we improve the expected complexity bound to [email protected]?"B(d^[email protected]). We compute the multiplicities within the same complexity and extend the algorithm to non-square-free polynomials. Finally, we present an open-source C++ implementation in the algebraic library synaps, and illustrate its completeness and efficiency as compared to some other available software. For this we use polynomials with coefficient bit size up to 8000 bits and degree up to 1000. The classical problem of solving an nth degree polynomial equation has substantially influenced the development of mathematics throughout the centuries and still has several important applications to the theory and practice of present-day computing. We briefly recall the history of the algorithmic approach to this problem and then review some successful solution algorithms. We end by outlining some algorithms of 1995 that solve this problem at a surprisingly low computational cost.