Studies in numerical linear algebra
Ming Gu · 1993
We discuss three sets of problems in numerical linear algebra: algorithms for modified symmetric eigenproblems, relative perturbation theory for symmetric eigenproblems, and the existence of and algorithms for a new rank-revealing QR factorization. In Part I we discuss algorithms for modified symmetric eigenproblems. We present an algorithm for computing the eigendecomposition of a symmetric rank-one modification of a symmetric matrix whose eigendecomposition is known. Previous algorithms for this problem suffer a potential loss of orthogonality among the computed eigenvectors, unless extended precision arithmetic is used. Our algorithm is based on a novel and stable method for computing the eigenvectors. It does not require extended precision yet is as efficient as previous algorithms. Based on this algorithm, we present algorithms for the symmetric tridiagonal eigenproblem, the bidiagonal singular value decomposition, and updating and downdating the singular value decomposition. We also present a modified version of the fast multipole method of Carrier, Greengard and Rokhlin to speed up these algorithms stably. In Part II we discuss relative perturbation theory for symmetric eigenproblems. We study the effects of component-wise relative perturbations of a symmetric matrix on its eigenvalues and of a general matrix on its singular values. We characterize a class of matrices whose eigenvalues or singular values incur small relative changes under such perturbations. In a well-defined sense our results are optimal up to a small constant factor. In Part III we discuss rank-revealing factorizations. Given a matrix M, we show that there exists a permutation $\Pi$ and an integer k such that, in the QR factorization $$M \Pi = Q\left(\sp{A\sb{k}} \sbsp{C\sb{k}}{B\sb{k}}\right),$$the rank of M is revealed by a sufficiently large and well-conditioned square matrix $A\sb{k}$ with minimum column dimension. In addition, $C\sb{k}$ is sufficiently small and $B\sb{k}$ is linearly dependent on $A\sb{k}$ with bounded coefficients. We discuss the properties of and relate existing rank-revealing QR algorithms to such factorizations. We present an efficient algorithm for computing such factorizations.