Refined Lanczos Type Methods For Computing A Partial Singular Value Decomposition Of A Large Matrix

This thesis presents some algorithms for large scale singular value problems and investigates their convergence and restart issues. It consists of six chapters.First we introduces the background of large scale singular value problems and basic numerical algorithms and the state of this subject. Finally, we describe the work of this thesis.Chapter One gives the main results of projection methods and shows that classic projection methods have convergence problem, that is, approximate eigenvectors may fail to converge. Instead refined projection methods proposed by Jia can overcome this problem.In Chapter Two, we study some properties of the Ritz pairs of an argumented matrix with respect to a kind of special subspaces. It is proved that the projected eigenproblem can be reduced to a half dimensional singular value problem. As an important application, this equivalence allows one to compute a partial SVD of a large scale matrix and refined shifts for use within an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL), so that the computational cost and the storage requirement can be saved significantly.In Chapter Three we investigates the lower bidiagonalization Lanczos method and show that the method may encounter some convergence problems. We analyze the convergence of the method, showing why it may converge erratically and even may fail to converge. To correct this possible nonconvergence and improve the method, we propose a refined bidiagonalization Lanczos method and apply the implicitly restarting technique due to Sorensen to the method. We then develop an implicitly restarted refined bidiagonalization Lanczos algorithm (IRRBL). We propose a new selection of shifts for use within IRRBL, called refined shifts, and present a reliable and efficient algorithm for computing the refined shifts. Numerical experiments show that IRRBL can perform better than the implicitly restarted bidiagonalization Lanczos algorithm (IRBL) proposed by LarsenIn Chapter Four, we discuss the upper bidiagonalization Lanczos method and its refined version, analyze their convergence and compare the upper and lower bidiagonalization Lanczos methods.In Chapter Five we investigate the harmonic bidiagonalization Lanczos algorithm for computing interior singular values and analyze its convergence. Theoretical analysis shows that harmonic Ritz values converge, and harmonic approximate singular vectors also converge if the desired harmonic Ritz values are well separated from other harmonic Ritz values. A selection of shifts, called harmonic shifts, is proposed. Numerical results comfirm the efficency of the new algorithm.In Chapter Six we are devoted to some future work. The first is how to compare the refined upper and lower bidiagonalization Lanczos method. The second is how to apply the refined idea to the harmonic bidiagonalization Lanczos method to correct its deficiency.