首页| English| 中国科学院

Complexity Analysis of A Root Clustering Algorithm

副标题:

时间:2018-07-02  来源:数学机械化重点实验室

题目:           Complexity Analysis of A Root Clustering Algorithm

报告人:      Vikram Sharma (Institute of Mathematics Sciences, India)

时间地点:   2018.07.05  10:30pm  N219

摘要:           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.
相关附件
相关文档