On the maximum computing time of the bisection method for real root isolation. (March 2017)

• Record Type: Journal Article
• Authors: Collins, George E.
• Is Part Of: Journal of symbolic computation. Volume 79(2017)Part 2
• Page Start: 444
• Page End: 456
• Publication Date: 2017-03
• Subjects: Polynomial roots -- Real roots -- Root isolation -- Computing time -- Algorithm analysis -- Dominance; 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.2016.02.017
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: The bisection method for polynomial real root isolation was introduced by Collins and Akritas in1976 . In1981 Mignotte introduced the polynomials A a, n ( x ) = x n − 2 ( a x − 1 ) 2, a an integer, a ≥ 2 and n ≥ 3 . First we prove that if a is odd then the computing time of the bisection method when applied to A a, n dominates n 5 ( log ⁡ d ) 2 where d is the maximum norm of A a, n . Then we prove that if A is any polynomial of degree n with maximum norm d then the computing time of the bisection method, with a minor improvement regarding homothetic transformations, is dominated by n 5 ( log ⁡ d ) 2 . It follows that the maximum computing time of the bisection method is codominant with n 5 ( log ⁡ d ) 2 .