现在位置:首页 > 学术报告
 

 

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.
 

 

附件下载:
 
 
【打印本页】【关闭本页】
电子政务平台   |   科技网邮箱   |   ARP系统   |   会议服务平台   |   联系我们   |   友情链接