Background

Traditional methods of solving polynomial equations of high degree with multiple roots, for example, those based on the Newton-Raphson method, yield unsatisfactory answers. Roundoff errors are sufficient to cause incorrect solutions, even if all the roots are simple, and these problems are compounded when the polynomial has multiple roots because they cause a multiple root to break up into simple roots. It is known that simple clustering of the computed roots does not necessarily yield a satisfactory solution. Further complications occur when the coefficients of the polynomial are subject to error because there now exists a (potentially infinite) family of solutions, each of which is valid provided that the backward error of each computed root is less than the error in the data.

The course will consist of lectures and laboratory classes on a new technique for computing the roots of a polynomial whose coefficients are subject to error, when the computed roots must satisfy stated conditions. This technique uses structured matrix methods on the Sylvester resultant matrix in order to perform a sequence of approximate greatest common divisor (GCD) computations.

Aims

The aims of the Summer School are:

• To provide examples from geometric modelling, systems theory and other disciplines in which computations on polynomials are required.
• To provides lectures and computer classes on a new and successful method of solving polynomial equations of high degree with multiple roots when the coefficients are subject to error.
• To provide lectures on structured matrix methods for approximate greatest common divisor computations.

In order to emphasise these aims of the Summer School, the theory of the methods will be presented for Bernstein basis polynomials (which is applicable to geometric modelling), and the power (monomial) basis, which is the most popular polynomial basis and used in many other applications, including systems theory and signal processing.

Technical Program

The topics covered in the Summer School include:

• Problems that yield polynomial equations of high degree
• Reasons for the failure of classical methods for solving polynomial equations of high degree
• Structured and unstructured condition numbers of roots of polynomials
• Structure preserving matrix methods with respect to:
  • The Sylvester resultant matrix and its subresultants
  • Approximate greatest common divisor computations
  • Equality constrained least squares problems
• The method of non-linear least squares

Invited speakers

The invited speakers are

• Professor Rob Corless (University of Western Ontario, Canada) slides
• Professor Gershon Elber (The Technion, Haifa, Israel) slides
• Professor Gene Golub (Stanford University, USA) slides
• Dr Ivan Markovsky (Southampton University, UK) slides
• Professor Zhonggang Zeng (Northeastern Illinois University, USA) slides