Ten methods to bound multiple roots of polynomials (Q1398714)

Let \(P\in{\mathbb C}[z]\) be a univariate polynomial, and \(\widetilde{z} \in {\mathbb C}\) be such that \(P\) has a \(k\)-fold root cluster near \(\widetilde{z}\). The author examines, for 17 different types of polynomials \(P\), the behavior of nine methods to compute a disc near \(\widetilde{z}\) which contains at least (or, for some methods, exactly) \(k\) roots of \(P\). Most of the methods are known, though some new variations are presented. All possible effects of rounding errors are accounted for in the implementation and testing of each method, and complexity bounds are presented for each as well. Single precision arithmetic is used throughout. Based on the results of the tests, the author derives a tenth, hybrid algorithm which does not require knowledge of \(k\) in advance, and which almost always gives, numerically, nearly optimal discs. This algorithm has been implemented in Matlab 4.0 and is available in the INTLAB toolbox, which can be downloaded (freely, for private and academic purposes) from the author's homepage.