Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Algebraic Moments - Real Root Finding and Related Topices.


Ph. Rostalski

ETH Zurich, no. DISS. ETH NO. 18371, pp. 211

Polynomial root finding is a classical and well studied problem in mathematics with practical applications in many areas. Various relevant questions can be reformulated into the task of finding all common roots of a given system of polynomials in several variables, the so-called algebraic variety or zero set. Traditionally, root finding algorithms are implemented in exact arithmetics over algebraically closed fields and fall into the area of computational algebraic geometry. However, in practical applications data is often uncertain and only known up to a certain finite precision. Algorithms in the new and promising area of numerical polynomial algebra or numerical algebraic geometry reflect this issue. Just like in linear algebra, the use of numerical methods has the potential of reducing the complexity and storage requirements and thus allows to treat problems of larger size. Almost all existing numerical algebraic methods perform computations over the field of complex numbers, while in practical problems the variables are mostly real valued. In this thesis we address the need for numerical software in real algebraic geometry by proposing two algorithms for computing real roots or even roots in certain semialgebraic sets. A novel semi-definite representation of the real radical ideal allows a unified treatment for the computation of real and complex roots as well as the construction of border and Gröbner bases of the ideal or its real radical ideal respectively. We address the issue of augmenting existing symbolic-numeric algorithms with real algebraic features and provide a first step towards efficient algebraic algorithms for computations over the real numbers. After recalling some basic concepts from commutative algebra and algebraic geometry, two existing root finding methods are discussed. Nonlinear parametric programming is introduced as an example, which can be tackled using polynomial algebra for presolving. The precomputation, based on solving first order optimality conditions, is particularly useful in time critical applications of parametric programming. Model predictive control, where an optimal control problem with changing initial state is solved in real time, demonstrates an important example. The first approach uses symbolic computation and proceeds by precomputing Gröbner basis and so-called generalized companion matrices. The online algorithm reduces to the evaluation of the parameters in these matrices, a few numerical eigenvalue computations and a finite search among all real and feasible candidate solutions (appearing as eigenvalues of the precomputed matrices). The second approach utilizes the structure of the parametric equations within the KKT equations. By solving a single generic instance of these equations, homotopy continuation over the complex numbers can be used to efficiently trace the solutions to a solution for any other value of the parameter. Motivated by the drawbacks of existing symbolic algorithms, such as the effect of blow-up in the integer coefficients of Gröbner bases, its representation instability or the potentially large number of redundant complex solutions, we focus on the development of numerical algorithms for computations over the real numbers. Based on existing semidefinite programming relaxations for global optimization, the matrix of moments (or moment matrix) and semidefinite programming are considered as natural candidates. We start by recalling basic concepts from real algebraic geometry and review well known results about moment matrices and their kernels. A careful analysis of the structure of moment matrices leads to a novel algorithm for computing roots of a system of polynomials as well as other interesting algebraic objects such as border or Gröbner bases of the real radical ideal. A single generic linear form is used to represent the algebraic variety or more precisely a certain set of polynomials whose zero set is the desired variety. Depending on the structure and properties of the linear form, this set of polynomials is an ideal or even a radical ideal with the properties that its roots are precisely the considered subset (all complex roots, all real roots or even a subset described by additional inequalities). All steps in the algorithm can be performed using numerical linear algebra and, for the computation over the real numbers, semidefinite programming. Termination of the algorithm is proven under the condition that the number of roots we want to compute is finite. Extensions to zero-dimensional subsets of all roots as well as a first attempt towards positive dimensional solution sets are illustrated. In certain cases the algorithm can also be used to obtain exact certificates for the nonexistence of roots, despite the use of floating point arithmetics. The enabling tool for the real version of the algorithm is the representation of the real radical ideal using moment matrices. We show how this representation can be embedded into existing numerical algebraic algorithms to enable real algebraic computations. The approach is illustrated on a particularly simple instance, namely a basic prolongation projection method. Different implementation options are discussed and we demonstrate its applicability on a large sample of examples. Even though the current implementation of the algorithm is not yet fully competitive with other available solvers, it shows exemplarily how real algebraic features maybe added to this class of algorithms.


Type of Publication:

(03)Ph.D. Thesis

M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhDThesis { Xxx:2009:IFA_3456,
    author={Ph. Rostalski},
    title={{Algebraic Moments - Real Root Finding and Related Topices.}},
Permanent link