Structured methods for polynomial computation

Polynomial root finding is a classic and fundamental problem in symbolic algebra and applied mathematics. One important example of standard and much used univariate root finding technique consists in applying the QR method to compute the eigenvalues of the Frobenius companion matrix (see for instance the Matlab command ‘roots’). Ill conditioned cases require more sophisticated techniques which make use of multiprecision when necessary : Some of the most ecient algorithms developed lately are based on iterative methods such as Newton and Aberth or Durand-Kerner/ Weierstrass, coupled with techniques of cluster detection and root isolation (BF], [F]). There is a close relationship between the two approaches : the Durand-Kerner method, for instance, corresponds to QR eigenvalue iteration on the Lagrange companion matrix as proposed in [F]. More generally, root finding methods can often be expressed in matrix form and carried out along the lines of classic problems in numerical linear algebra (e.g., eigenvalue computation). On the other hand, we have assisted in the last years to a remarkable development of numerical methods which are specifically tailored to certain structured classes of matrices. The use of a clever structured parametrization in the design of an algorithm is meant to lower complexity bounds and memory requirements, while avoiding or limiting a deterioration of stability properties. In particular, eigensolvers and linear system solvers that exploit rank structure have been the subject of several research papers and contributions to major conferences (e.g. ILAS, ISSAC, SNC). The matrix formulation of most approaches to polynomial root finding mostly involves structured matrices, such as companion matrices in various bases. It is therefore natural to combine results from these two domains and incorporate the use of matrix structure (e.g., rank structure such as quasi/semi-separability) in the design and analysis of root finding algorithms ; an interesting attempt in this direction can be found in [GU]. Developments in this line of research are proposed as the main theme for this thesis. Issues to be explored include : – theoretical contributions (convergence and other properties of the chosen methods, detection and properties of matrix structure, adaptation of the root finding method to structure), – effective design of suitable algorithms, with emphasis on adaptivity (use of symbolic computation or multiprecision when needed, and standard double precision whenever possible), – stability analysis, – implementation, – and possible generalizations. More generally, we point out that matrix-based methods play a crucial part in many other instances of polynomial computations besides rootfinding (see e.g. [BP], [P]), to which the scope of the thesis may be extended. Structured methods play a crucial role in symbolic-numeric computation, since they allow to improve complexity (either in a symbolic or in a numeric framework) and may provide further insight as to the peculiarities of the problem of interest. Conversely, the design of symbolic/numeric approaches tailored to a specific problem motivates the study of matrix structures that may later find an application in other contexts. References : [BF] D. A. Bini, G. Fiorentino, Design, analysis and implementation of a multiprecision polynomial root finder, Numer. Alg. 23 (2000), pages 127-173. [F] S. Fortune, An Iterated Eigenvalue Algorithm for Approximating Roots of Univariate Polynomials, J. Symb. Comp. 33 (2002), pages 627-646. [GU] L. Gemignani, F. Uhlig, A Fast Hybrid Symbolic-Numeric Solver for Secular Equations, preprint. [BP] D. A. Bini, V. Y. Pan, Polynomial and Matrix Computations, Birkhauser(1994). [P] V. Y. Pan, Structured Matrices and Polynomials : Unified Superfast Algorithms, Birkhauser (2001).

Contact:[Paola Boito


Menu principal

Haut de page