Structured matrix methods for the computation of multiple roots of a polynomial

• It is shown that structured matrix methods allow multiple roots of a polynomial to be computed reliably.
• A geometric explanation, in terms of pejorative manifolds of a polynomial that has multiple roots, is provided and complements the numerical method.
• Structured matrix methods are used to perform polynomial deconvolution.
• A comparison of the results from the method described in the paper with the results from the suite of Matlab programs MultRoot is given.

This paper considers the application of structured matrix methods for the computation of multiple roots of a polynomial. In particular, the given polynomial f(y)f(y) is formed by the addition of noise to the coefficients of its exact form fˆ(y), and the noise causes multiple roots of fˆ(y) to break up into simple roots. It is shown that structured matrix methods enable the simple roots of f(y)f(y) that originate from the same multiple root of fˆ(y) to be ‘sewn’ together, which therefore allows the multiple roots of fˆ(y) to be computed. The algorithm that achieves these results involves several greatest common divisor computations and polynomial deconvolutions, and special care is required for the implementation of these operations because they are ill-posed. Computational examples that demonstrate the theory are included, and the results are compared with the results from MultRoot, which is a suite of Matlab programs for the computation of multiple roots of a polynomial.