Stable Algorithms for Large Sparse Eigenvalue Problems

In this dissertation, we consider the symmetric eigenvalue problem and the buckling eigenvalue problem. We study existing algorithms and propose stable variants for both eigenvalue problems.We first analyze Hotelling's deflation for the symmetric eigenvalue problem $Ax=\lambda x$, where $A$ is a symmetric matrix. Hotelling's deflation is a technique to displace computed eigenvalues of $A$. It is combined with an eigensolver to compute a partial eigendecomposition of $A$. Numerical stability of Hotelling's deflation is not well understood. In this dissertation, we derive computable upper bounds on the loss of orthogonality of computed eigenvectors and on the backward error norm of computed eigenpairs. From the upper bounds, we identify crucial quantities associated with the shifts and derive sufficient conditions for the backward stability of Hotelling's deflation. Based on these results, we propose a shift selection scheme for stabilizing Hotelling's deflation.Next we consider the buckling eigenvalue problem $Kx=\lambda K_Gx$, where the matrix $K$ is positive semi-definite, the matrix $K_G$ is indefinite, and the matrices $K$ and $K_G$ share a common nullspace. When $K$ is positive definite, the shift-invert Lanczos method is a widely accepted method for the buckling eigenvalue problem. However, in our case, there are two issues associated with the method. First, the shift-invert operator $(K - \sigma K_G)^{-1}$ does not exist or is ill-conditioned. Second, the Lanczos vectors fall rapidly into the nullspace of $K$. The inner product induced by $K$ leads to rapid growth of the Lanczos vectors in norm. The large norms introduce large round-off errors to the orthogonalization process, leading to loss of accuracy of compute solutions and even break down of the method. In this dissertation, we address these issues by generalizing the buckling spectral transformation to the singular pencil $K - \lambda K_G$ and regularizing the inner product to bound the norms of the Lanczos vectors. We propose a shift-invert Lanczos method for the buckling eigenvalue problem and develop a validation scheme using inertias