Nearly optimal refinement of real roots of a univariate polynomial. (May 2016)

• Record Type: Journal Article
• Authors: Pan, Victor Y.; Tsigaridas, Elias P.
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 181
• Page End: 204
• Publication Date: 2016-05
• Subjects: Real root refinement -- Polynomial -- Boolean complexity -- Fast polynomial division -- Precision of computing; 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.06.009
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We assume that a real square-free polynomial A has a degree d, a maximum coefficient bitsize τ and a real root lying in an isolating interval and having no nonreal roots nearby (we quantify this assumption). Then we combine the Double Exponential Sieve algorithm (also called the Bisection of the Exponents ), the bisection, and Newton iteration to decrease the width of this inclusion interval by a factor of t = 2 − L . The algorithm has Boolean complexity O ˜ B ( d 2 τ + d L ) . This substantially decreases the known bound O ˜ B ( d 3 + d 2 L ) and is optimal up to a polylogarithmic factor. Furthermore we readily extend our algorithm to support the same upper bound on the complexity of the refinement of r real roots, for any r ≤ d, by incorporating the known efficient algorithms for multipoint polynomial evaluation. The main ingredient for the latter is an efficient algorithm for (approximate) polynomial division; we present a variation based on structured matrix computation with quasi-optimal Boolean complexity.