Computing real roots of real polynomials. (March 2016)

• Record Type: Journal Article
• Authors: Sagraloff, Michael; Mehlhorn, Kurt
• Is Part Of: Journal of symbolic computation. Volume 73(2016)
• Page Start: 46
• Page End: 86
• Publication Date: 2016-03
• Subjects: Root finding -- Root isolation -- Root refinement -- Approximate arithmetic -- Certified computation -- Complexity analysis; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.03.004
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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 Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 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, denotedA New Dsc, 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.A New Dsc 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.