Loading...
Please wait, while we are loading the content...
Similar Documents
Numerically Stable Algorithms for Winding Number Computation and Polynomial Root-finding
| Content Provider | Semantic Scholar |
|---|---|
| Author | Zhao, Liang |
| Copyright Year | 2016 |
| Abstract | be a polynomial of degree n whose coefficients are complex numbers. Our subject is to study the worstcase complexity of approximating within distance , every zeros zj in a given rectangular region R =:= {z ∈ C : |Re(z) − a| < r1, |Im(z) − b| < r2}. Polynomial root-finding has been one of the most important computational problems, and there have been both theoretical and practical results on this problem. In theory, there is Pan’s algorithm [3], which is refined from Schonhage’s splitting circle method [5]. Pan’s algorithm achieves near-optimal arithmetic and bit-complexity, but it is impractical. Practical root-finding packages such as MPSOLVE [1] or eigensolve [2] have excellent empirical behaviour, but their validity haven’t been proved entirely as they rely on Aberth’s or Weierstrass-Durand-Kerner’s method. The main result of this paper is an algorithm modified from Renegar’s algorithm. Renegar proposed a root-finding algorithm in [4] using Newton’s method, Schur-Cohn algorithm and an exclusion test based on winding number calculation. In this paper we modified the winding number subalgorithm so that it is numerically stable, thus making the root-finding algorithm ready for practical use. In complex analysis, the winding number of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counter-clockwise around the point. In particular, the winding number of a simple closed curve C around point a is defined as follows: winding number = ∮ |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://matthewpjohnson.org/fwcg2016/FWCG_2016_paper_33.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
