2015/01/30 by Vikram Sharma, Sharma, Vikram, Prashant Batra +1
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.1501.07774
openalex publication_date 2015/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We describe a subroutine that improves the running time of any subdivision algorithm for real root isolation. The subroutine first detects clusters of roots using a result of Ostrowski, and then uses Newton iteration to converge to them. Near a cluster, we switch to subdivision, and proceed recursively. The subroutine has the advantage that it is independent of the predicates used to terminate the subdivision. This gives us an alternative and simpler approach to recent developments of Sagraloff (2012) and Sagraloff-Mehlhorn (2013), assuming exact arithmetic. The subdivision tree size of our algorithm using predicates based on Descartes's rule of signs is bounded by O(nlog n), which is better by O(nlog L) compared to known results. Our analysis differs in two key aspects. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and second, we use the geometry of clusters of roots instead of the Davenport-Mahler bound. The analysis naturally extends to other predicates.