Academy of Mathematics and Systems Science, CAS Colloquia & Seminars
Speaker:
Vikram Sharma,Institute of Mathematics Sciences, India
Inviter:
Title:
Complexity Analysis of A Root Clustering Algorithm
Time & Venue:
2018.7.5 10:30pm N219
Abstract:
Computing the roots of analytic functions is one of the most fundamental problems in numerical analysis. Not many algorithms are known in the literature for solving the problem, and very few of these algorithms provide a complete complexity analysis. One such result is that the roots of a polynomial-time computable function are also poly-time computable. However, this result is not uniform and it assumes that the roots are all simple. A desirable goal is to devise algorithms that don't make such assumptions. However, then the problem changes from finding roots to finding clusters. Moreover, in the bit-model of computation, we cannot decide whether a number is zero or not. Therefore, the challenge is to devise a complete algorithm for finding root clusters of complex analytic (holomorphic) functions without exact comparisons with zero. This was achieved by Yap, Sagraloff, Sharma, CiE, 2013. Their algorithm is a subdivision based algorithm. In this paper, we derive bounds on the number of boxes in the subdivision process. Our analysis uses the continuous amortization framework of Burr and Krahmer, J. of Symb. Comp, 2012. We derive bounds similar to the one by Yakoubsohn, J. of Complexity, 2005, where only an exclusion based subdivision algorithm is given. We also derive bounds on the precision requirements of the algorithm.