New methods for solving high degree polynomial equations that have multiple roots

43 mins 27 secs, 601.01 MB, MPEG-4 Video 480x360, 25.0 fps, 44100 Hz, 1.84 Mbits/sec

About this item

Description:	Winkler, J (Sheffield) Tuesday 22 January 2008, 15:30-16:00 Zeros of Graph Polynomials

Created:

2008-02-01 12:37

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Winkler, J

Language:

eng (English)

Credits:

Author:

Winkler, J


Abstract:	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.

Abstract:

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	480x360	1.84 Mbits/sec	601.01 MB	View	Download
Flash Video	480x360	801.99 kbits/sec	255.72 MB	View	Download
iPod Video	480x360	505.28 kbits/sec	161.11 MB	View	Download
Windows Media Video (for download)	480x360	479.18 kbits/sec	152.79 MB	View	Download
Windows Media Video (for streaming)	480x360	447.68 kbits/sec	142.74 MB	View	Download	Stream
RealMedia	480x360	878.12 kbits/sec	279.99 MB	View	Download	Stream
QuickTime (for download)	384x288	848.38 kbits/sec	270.51 MB	View	Download
QuickTime (for streaming)	480x360	906.77 kbits/sec	289.12 MB	View	Download
MP3	44100 Hz	125.04 kbits/sec	39.66 MB	Listen	Download