The Study Of Numerical Algorithms For Symmetric Generalized Eigenvalue Problems

Symmetric generalized eigenvalue problems arise in many science computing and engineering applications, such as dynamic analysis of structures, structural vibration, electronic structure calculations, quantum chemistry, circuit network, chemical reaction, macro-economical balance. Typically, these problems are large and sparse, and frequently only a few of the eigenpairs are of interest. Therefore, traditional methods such as the QZ algorithm may not be considered. Moreover, it may be impractical to apply shift-and-invert Lanczos, a favored method for problems of this type, due to difficulties in applying the inverse of the shifted matrix.With these difficulties in mind, Golub and Ye developed an inverse free Krylov subspace algorithm for the symmetric generalized eigenvalue problem. This method does not rely on shift-and-invert transformations for convergence acceleration, but rather a preconditioner is used. The algorithm suffers, however, in the presence of multiple or clustered eigenvalues. Also, it is only applicable to the location of extreme eigenvalues.In this dissertation, we studied the faster algorithms for symmetric generalized eigenvalue problems. Firstly, we presented a refined variant of the inverse free Krylov subspace method, to avoid applying complex preconditioning techniques for the problem. Secondly, we introduced a refined shifted inverse free Krylov subspace algorithm for interior eigenvalues and their corresponding eigenvectors based on spectral transformation. Also, we analyze the theory of convergence. For accelerating convergence and computing the p smallest eigenvalues and their corresponding eigenvectors simultaneously of the problem, we develop a refined shifted block inverse free Krylov subspace algorithm. Based on the block Arnoldi process that generates an B-orthogonal basis of a matrix Krylov subspace. It is proved that this algorithm can guarantee the convergence if the corresponding Ritz values do. Numerical experiments show that the refined algorithm is more efficient than the inverse free Krylove subspace. Finally, the research work of this dissertation is summarized. This dissertation includes four chapters. which is organized as follows:Firstly, the research background and research status of Krylov subspace for generalized eigenvalue problems are given, as well as the preliminary knowledge. Furthermore, the main contents of this paper are briefed. In the second chapter, a refined variant of the inverse free Krylov subspace method for symmetric generalize eigenvalue problems is proposed, a prior error estimate for the refined Ritz vector is given which shows that the refined Ritz vector converges once the deviation of the eigenvector form the trial Krylov subspace goes to zero. Numerical experiments are given to show the efficiency of the method.In the third chapter, to accelerate convergence and compute interior eingenpairs, we present a refined block inverse free Krylov subspace algorithm. Based on the block Arnoldi process that generates an B-orthogonal basis of a matrix Krylov subspace. It is proved that this algorithm can guarantee the convergence if the corresponding Ritz values do. Numerical experiments show that the algorithm is more efficient than the refined algorithm.Finally, the research work of this dissertation is summarized and the future research directions based on this work are discussed.