Algorithms and perturbation theory for matrix eigenvalue problems and the singular value decomposition

This dissertation is about algorithmic and theoretical developments for eigenvalue problems in numerical linear algebra. The first part of this dissertation proposes algorithms for two important matrix decompositions, the symmetric eigenvalue decomposition and the singular value decomposition. Recent advances and changes in computational architectures have made it necessary for basic linear algebra algorithms to be well-adapted for parallel computing. A few decades ago, an algorithm was considered faster if it required fewer arithmetic operations. This is not the case anymore, and now it is vital to minimize both arithmetic and communication when designing algorithms that are well-suited for high performance scientific computing. Unfortunately, for the above two matrix decompositions, no known algorithm minimizes communication without needing significantly more arithmetic. The development of such algorithms is the main theme of the first half of the dissertation. Our algorithms have great potential as the future approach to computing these matrix decompositions. The second part of this dissertation explores eigenvalue perturbation theory. Besides being of theoretical interest, perturbation theory is a useful tool that plays important roles in many applications. For example, it is frequently employed in the stability analysis of a numerical algorithm, for examining whether a given problem is well-conditioned under perturbation, or for bounding errors of a computed solution. However, there are a number of phenomena that still cannot be explained by existing theory. We make contributions by deriving refined eigenvalue perturbation bounds for Hermitian block tridiagonal matrices and generalized Hermitian eigenproblems, giving explanations for the perturbation behavior of a multiple generalized eigenvalue, presenting refined eigenvector perturbation bounds, and developing new Gerschgorin-type eigenvalue inclusion sets.