| This thesis consists of two parts, each presenting an active area in the field of matrix eigenvalue computation. In Part I, after reviewing a general framework for matrix formulations of polynomial root problems, we focus on developing fast and stable QR-like algorithms for eigenvalue computations of real orthogonal Hessenberg matrices and real companion matrices. It is well known that an orthogonal Hessenberg matrix H can be expressed as a product of Givens rotation matrices. We further find that a shifted QR iteration on H can be realized through a series of Givens rotation swaps. Such new Givens-swapping technique enables us to develop a fast O(n2) and backward stable QR-like algorithm for H.For companion matrices, it is not until recently that researchers noticed that the Hessenberg iterates Ck have an invariant off-diagonal low rank structure. Based on such observation, by applying the Givens-swapping technique and by expressing matrices with off-diagonal low ranks in their sequentially semi-separable (SSS) forms, we develop another new O(n2) QR-like algorithm for real companion matrices. Our numerical experiments demonstrated the high speed performance of the new algorithm. In practice we observed little growth in backward error in our algorithm.In Part II, we turn to quadratic eigenvalue problems (QEPs) of the form: (lambda2M + lambdaD + K)x = 0. After a brief review on basic concepts and techniques in QEPs (such as its spectral transformation and linearization), we focus on subspace projection methods for solving QEPs. The main contribution of Part II is the development of the AR2O procedure, a brand-new Arnoldi procedure with two levels of orthogonality for generating an orthonormal basis Qn for the purpose of model reduction of the QEP. It uses about a half of the memory required by the Arnoldi method, and by using two levels of orthogonality, it is very numerically robust. Numerical results are presented at the end to demonstrate the superiority of the AR2O method. |
