Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6861211 | Journal of Symbolic Computation | 2018 | 46 Pages |
Abstract
Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Ruben Becker, Michael Sagraloff, Vikram Sharma, Chee Yap,