Some Numerical Algorithms For Large Nonsymmetric Eigenvalue Problems

Some Numerical Algorithms for Large Nonsymmetric EigenvalueProblemsLarge scale eigenvalue problems are of increasing importance in scientific and engineering computing. Considerable progress has been made over the past decades towards the numerical solution of large scale nonsymmetric problems. However, there is still a great deal to be done. The work of this thesis focuses on the following.In Chapter 1 we introduce the background of large scale eigenproblems and basic numerical algorithms for solving them. We also review the state of the art of this subject briefly.The ABLE method can be used to compute eigentriplets of large scale non-Hermitian matrices. However, theoretical results given in Chapter 2 show that there is no guarantee for the Ritz vectors obtained by this method to converge even if the subspace is good enough. In order to deal with this problem, we introduce two approxi-mate refined ABLE methods in which we use quasi-refined Ritz vectors and semi-refined Ritz vectors to approximate the desired eigenvectors,respectively. Furthermore, for the sake of storage limitations and amount of computations, restarting techniques are often required in practice. A scheme advocated by Morgan for restarting is generalized to the ABLE method, and a dynamic thick restarted semi-refined ABLE algorithm is coined. The relationships between the new approximations and the Ritz vectors are analyzed. Theoretical analysis says that both the new methods can circumvent the possible danger that exists in the classical one in some degree. Numerical experiments illustrate that the new algorithms are often more powerful and attractive than their counterparts.The shift-and-invert Arnoldi method is popular for computing a few eigenvalues near a given target point and the associated eigenvectors of large nonsymmetric matrix pencils. However, theoretical analysis reveals that this method may suffer from the drawback of possible nonconverging Ritz vectors. In order to circumvent this difficulty, inChapter 3 we propose a novel strategy that uses new approximate eigenvectors to take the place of Ritz vectors, and the convergence of the resulting approximations can be guaranteed in theory. Another merit of such a strategy is that it exploits some useful eigen-information contained in the wasted (m + l)th basis vector vm+i in some degree, so it may be favorable when m is small. Numerical experiments are reported on the new algorithm and its counterparts, they show that the former is often superior to the latter.The approximate eigenvectors or Ritz vectors gained by the block Arnoldi method may converge very slowly and even fail to converge even if Ritz values do. In order to improve the quality of the Ritz vectors, in Chapter 4 a strategy proposed by Jia and Eisner is generalized to the block Arnoldi version. In the novel method, we use new modified approximate eigenvector obtained from a linear combination of Ritz vector and the available (m + l}th block basis vector Vm+i. In fact, the new approximation is nothing but the refined Ritz vector in the (p + l)-dimensional space spanned by Ritz vector and the columns of Vm+i- The resulting block Arnoldi algorithm is not only better than the standard m-step one both in theory and in practice but also cheaper than the standard (m + l)-step one. The relationships between the residual norms of Ritz pairs and those of new approximate eigenpairs are analyzed, and the convergence properties of the new method is also studied, they say that the novel method may deal with the problem of nonconverging Ritz vectors to some extent. We carry out some numerical examples which illustrate the new algorithm is more efficient and work better than its counterparts.