ETD system

Electronic theses and dissertations repository


Tesi etd-09272012-094839

Thesis type
Tesi di dottorato di ricerca
Polynomial Eigenproblems: a Root-Finding Approach
Settore scientifico disciplinare
Corso di studi
relatore Prof. Gemignani, Luca
tutor Prof. Bini, Dario Andrea
Parole chiave
  • polynomial matrix
  • matrix polynomial
  • eigenvalue problem
  • structured eigenvalue problem
Data inizio appello
Riassunto analitico
A matrix polynomial, also known as a polynomial matrix, <br>is a polynomial whose coefficients are matrices; or, equivalently, a matrix whose elements are polynomials.<br><br><br>If the matrix polynomial P(x) is regular, that is if p(x):=det(P(x)) is not identically zero, <br>the polynomial eigenvalue problem associated with P(x) is equivalent to the<br>computation of the roots of the polynomial p(x); such roots are called the<br>eigenvalues of the regular matrix polynomial P(x). Sometimes, one is also interested in computing <br>the corresponding (left and right) eigenvectors.<br><br>Recently, much literature has been addressed to the polynomial<br>eigenvalue problem. This line of research is currently very active: the theoretical properties of PEPs are studied, <br>and fast and numerically stable methods are sought <br>for their numerical solution. The most commonly encountered <br>case is the one of degree 2 polynomials,<br>but there exist applications where higher degree polynomials appear. More generally, PEPs are special <br>cases belonging to the wider class of nonlinear eigenvalue problems. Amongst nonlinear eigenvalue problems, rational eigenvalue <br>problems <br> can be immediately brought to polynomial form, multiplying them by their least common denominator; truly <br>nonlinear eigenvalue problems may be approximated with PEPs, truncating some matrix power series, or with <br>rational eigenproblems, using rational approximants such as Padé approximants.<br><br>To approximate numerically the solutions of PEPs, several<br>algorithms have been introduced based on the technique of<br>linearization where the polynomial problem is replaced by a linear<br>pencil with larger size and the customary methods for the generalised<br>eigenvalue problem, like for instance the QZ algorithm, are applied.<br><br><br>This thesis is addressed to the design and analysis of <br>algorithms for the polynomial eigenvalue problem based on a root-finding approach. <br>A root-finder is applied to the <br>characteristic equation p(x)=0. In particular, we discuss algorithms based on the<br>Ehrlich-Aberth iteration.<br><br>The Ehrlich-Aberth iteration (EAI) is a method that simultaneously approximates all <br>the roots of a (scalar) polynomial. <br> <br><br>In order to adapt the EAI to the numerical solution of a PEP, <br>we propose a method based on the Jacobi formula; two implementation of the EAI are <br>discussed, of which one uses a linearization and the other works directly on the matrix polynomial. <br>The algorithm that we propose has quadratic computational complexity with respect to <br>the degree k of the matrix polynomial. This leads to computational advantage when the ratio k^2/n, where <br>n is the dimension of the matrix coefficients, is large. <br>Cases of this kind can be encountered, for instance,<br> in the truncation of matrix power series. If k^2/n is small, the EAI can be implemented <br>in such a way that its asymptotic complexity is cubic (or slightly supercubic) in nk, but QZ-based methods appear to be <br>faster in this case. Nevertheless, experiments suggest that the EAI can improve the approximations of the QZ in terms of forward <br>error, so that even when it is not as fast as other algorithms it is still suitable as a refinement method.<br><br>The EAI does not compute the eigenvectors. If they are needed, the EAI <br>can be combined with other methods such as the SVD or the inverse iteration. In the <br>experiments we performed, eigenvectors were computed in this way, and <br>they were approximated with higher accuracy with respect to the QZ.<br><br>Another root-finding approach to PEPs, similar to the EAI, is to <br>apply in sequence the Newton method to each single eigenvalue, using an implicit deflation of the previously <br>computed roots of the determinant<br>in order to avoid to approximate twice the same eigenvalue. Our numerical experience <br>suggests that in terms of efficiency the EAI is superior with respect to the sequential Newton method with deflation.<br><br>Specific attention concerns structured problems where the matrix<br>coefficients have some additional feature which is reflected on<br>structural properties of the roots. For instance, in the case of<br>T-palindromic polynomials, the roots are encountered in pairs (x,1/x). <br>In this case the goal is to design<br>algorithms which take advantage of this additional information about<br>the eigenvalues and deliver approximations to the eigenvalues which<br>respect these symmetries independently of the rounding<br>errors.<br>Within this setting, we study the case of polynomials endowed with specific properties<br>like, for instance, palindromic, T-palindromic, Hamiltonian, symplectic, even/odd, etc.,<br>whose eigenvalues have special symmetries in the complex plane. <br>In general, we<br>may consider the case of structures where the roots can be grouped in<br>pairs as (x,f(x)), where f(x) is any self-inverse analytic function such that. <br><br><br>We propose a unifying treatment of structured polynomials belonging to this class <br>and show how the EAI can be adapted to deal with them in a<br>very effective way. Several structured variants of the EAI are available to this goal: <br>they are described in this thesis. <br>All of such variants enable one to<br>compute only a subset of eigenvalues and to recover the remaining part<br>of the spectrum by means of the symmetries satisfied by the<br>eigenvalues. By exploiting the structure of the problem, this<br>approach leads to a saving on the number of floating point operations and provides<br>algorithms which yield numerical approximations fulfilling<br>the symmetry properties. Our research on the structured EAI can of course be applied also to scalar polynomials: in the <br>next future, we plan to exploit our results and design new features for the software MPSolve.<br><br>When studying the theoretical properties of the change of variable, useful to design one of the structured EAI methods, we had the <br>chance to discover some theorems on the behaviour of the complete eigenstructure of a matrix polynomial under a rational change of <br>variable. Such results are discussed in this thesis.<br><br>Some, but not all, of the different structured versions of the EAI algorithm have a drawback: accuracy is lost for eigenvalues that <br>are close to a finite number of critical values, called exceptional eigenvalues. On the other <br>hand, it turns out that at least for some specific structures <br>the versions that suffer from this problem are also the most efficient ones: thus, it is desirable to circumvent the <br>loss of accuracy. This can <br>be done by the design of a structured refinement Newton algorithm. Besides <br>its application to structured PEPs, this algorithm can have further application to the computation of the <br>roots of scalar polynomials whose roots appear in pairs.<br><br>In this thesis, we also present the results of several<br>numerical experiments performed in order to test the effectiveness of<br>our approach in terms of speed and of accuracy. We have compared the<br>Ehrlich-Aberth iteration with the Matlab functions polyeig and quadeig. In the structured case, we have also considered, when<br>available, other structured methods, say, the URV algorithm by<br>Schroeder . Moreover, the different versions of our algorithm are compared one with another.