* Faculty       * Staff       * Contact       * Institute Directory
* Research Groups      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Events       * Institute Events      
* Lab Manual       * Institute Computing      
No Menu Selected

* Research

Ph.D. Theses

Efficient Algorithms for Computing the Nearest Polynomial with Constrained Roots

By Markus A. Hitz
Advisor: Erich Kaltofen
April 17, 1998

The location of polynomial roots is sensitive to perturbations of the coefficients. Continuous changes of the coefficients of a polynomial move the roots continuously. We consider the problem of finding the minimal perturbations to the coefficients to move one or several roots to given loci. We measure minimality in the Euclidean distance to the coefficient vector, as well as the maximal coefficient-wise change in absolute value (infinity norm), and in the Manhattan norm ($l^1$-norm). In the Euclidean norm the computational task reduces to a least squares problem, in the infinity norm and the $l^1$-norm it can be formulated as a linear program.

We can derive symbolic solutions in closed form for the Euclidean norm in the case of complex coefficients and a single complex root. Our new result is a formula for the minimum change in the infinity norm for the case of real coefficients and a single real root. Based on the principle of {\em parametric minimization} we develop hybrid symbolic-numeric algorithms to constrain one root of a complex or real polynomial to a curve in the complex plane.

As an application to robust control, we give a polynomial-time algorithm to compute the radius of stability in the Euclidean norm for a variety of stability domains.

* Return to main PhD Theses page