On Polynomial Roots Approximation Via Dominant Eigenspaces And Isolation Of Real Roots

Finding the roots of a given polynomial is a very old and noble problem in mathematics and computational mathematics. For about 4,000 years, various approaches had been proposed to solve this problem (see cite{FC99}). In 1824, Niels Abel showed that there existed polynomials of degree five, whose roots could not be expressed using radicals and arithmetic operations through their coefficients. Here is an example of such polynomials:$$x^5-4x-2.$$ Thus we must resort to iterative methods to approximate the roots of a polynomial given with its coefficients. There are many algorithms that approximate the roots of a polynomial(see cite{B40}, cite{B68}, cite{MN93}, cite{MN97}, cite{MN99}, cite{MN02}, cite{MN07}). As important examples we cite Quadtree (Weyl\u27s) Construction and Newton\u27s Iteration (see cite{P00a}). Some of the algorithms have as their goal to output a single root, for example, the absolutely largest root. Some other algorithms aim to output a subset of all the roots of the given polynomial, for example, all the roots within a fixed region on the complex plane. In many applications (e.g., algebraic geometric optimization), only the real roots are of interest, and they can be much less numerous than all the roots of the polynomial (see cite{MP13}). Nevertheless, the best numerical subroutines, such as MPSolve 2.0 cite{BF00}, Eigensolve cite{F02}, and MPsolve 3.0 cite{BR14}, approximate all real roots about as fast and as slow as all complex roots. The purpose of this thesis is to find real roots of a given polynomial effectively and quickly, this is accomplished by separating real roots from the other roots of the given polynomial and by finding roots which are clustered and absolutely dominant. We use matrix functions throughout this thesis to achieve this goal. One of the approaches is to approximate the roots of a polynomial $p(x)$ by approximating the eigenvalues of its associated companion matrix $C_{p}$. This takes advantage of using the well-known numerical matrix methods for the eigenvalues. This dissertation is organized as follows. Chapter 1 is devoted to brief history and modern applications of Polynomial root-finding, definitions, preliminary results, basic theorems, and randomized matrix computations. In Chapter 2, we present our Basic Algorithms and combine them with repeated squaring to approximate the absolutely largest roots as well as the roots closest to a selected complex point. We recall the matrix sign function and apply it to eigen-solving. We cover its computation and adjust it to real eigen-solving. In Chapter 3, we present a matrix free algorithm to isolate and approximate real roots of a given polynomial. We use a Cayley map followed by Dandelin\u27s (Lobachevsky\u27s, Gräffe\u27s) iteration. This is in part based on the fact that we have at hand good and efficient algorithms to approximate roots of a polynomial having only real roots (for instance the modified Laguerre\u27s algorithm of [DJLZ97]). The idea is to extract (approximately) from the image of the given polynomial (via compositions of rational functions) a factor whose roots are all real, which can be solved using modified Laguerre\u27s algorithm, so we can output good approximations of the real roots of the given polynomial. In Chapter 4, we present an algorithm based on a matrix version of the Cayley map used in Chapter 3. As our input, we consider the companion matrix of a given polynomial. The Cayley map and selected rational functions are treated as matrix functions. Via composition of matrix functions we generate and approximate the eigenspace associated with the real eigenvalues of the companion matrix, and then we readily approximate the real eigenvalues of the companion matrix of the given polynomial. To simplify the algorithm and to avoid numerical issues appearing in computation of the high powers of matrices, we use factorization of $P^{k}-P^{-k}$ as the product $prod_{i=0}^{k-1}(P-omega_k^iP^{-1})$ where $omega_k=exp(2pisqrt {-1}/k)$ is a primitive $k$th root of unity