Faculty       Staff       Students & Alumni       Committees       Contact       Institute Directory
 All Research Groups       PhD Theses       Technical Reports       Institute Research
 Undergraduate Program       Graduate Program       Courses       Institute Catalog
 Undergraduate       Graduate       Institute Admissions: Undergraduate | Graduate
 Colloquia       Seminars       News       Events       Institute Events
 Overview       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.

 General inquiries: info@cs.rpi.edu Technical issues: www@cs.rpi.edu 110 8th Street Troy, NY 12180-3590 (518) 276-8326