New methods for solving high degree polynomial equations that have multiple roots
Seminar Room 1, Newton Institute
The determination of the roots of a polynomial is a classical problem in mathematics to which much effort has been devoted. There exist many methods for their computation, but they all fail on high degree polynomials, or polynomials that have multiple roots. In particular, roundoff errors due to finite precision arithmetic are sufficient to cause a multiple root to break up into a cluster of simple roots, and the problems are compounded when the coefficients of the polynomial are subject to error.
In this talk, I will describe a radically new, and significantly better, method of computing the roots of a polynomial. The method has two stages:
Stage 1: Perform a succession of greatest common divisor (GCD) computations to calculate the multiplicity of each distinct root.
Stage 2: Use the information from Stage 1 to calculate the roots, and then refine them using the method of non-linear least squares.
The GCD calculations in Stage 1 use structured matrix methods, algebraic geometry, the least squares equality problem and methods of information theory. The non-linear least squares in Stage 2 is performed by the Gauss-Newton iteration.
Examples will be given to illustrate the success of the method.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.