Robust Krylov Subspace Methods Based on Multiple Lanczos Procedure

University Of Wyoming, Laramie WY

Investigators

Abstract

Krylov subspace methods are widely used for the iterative solution of large sparse linear systems that arise in scientific and engineering applications. The standard Krylov subspace methods have been developed based on either the single starting Lanczos procedure (SSLP) or Arnoldi procedure. Since the multiple starting Lanczos procedure (MSLP) was invented, the superior robustness of MSLP to SSLP has been demonstrated through a variety of applications. Block Krylov subspace methods for solving linear systems with multiple right-hand sides have been derived from MSLP. However, there has been rare study of deriving Krylov subspace methods from MSLP for systems with a single right-hand side. Of course, multiple right-hand sides includes the single right-hand side as its special case. The PI, however, expects that finer methods can be obtained when we focus on the single right-hand side case. Tony Chan and the PI recently made the first attempt in this direction and methods named ML(n)BiCG and ML(n)BiCGSTAB, respectively, were developed. This project continues this trend and aims at (i) generalizing the existing standard methods from SSLP to MSLP; (ii) reducing the storage requirement of ML(n)BiCGSTAB; (iii) improving the robustness of ML(n)BiCG. This is the next step toward attainment of the PI's long-term goal of developing parallel Krylov subspace methods. The feasibility of the proposed aims have been demonstrated by the PI's preliminary studies of ML(n)BiCGSTAB and of a transpose-free MSLP algorithm. The approaches employed to attain the aims are based on certain ways of adapting the derivation of BiCG from SSLP and the derivation of the BiCGSTAB(n) from BiCG. The results will be tested extensively with industrial databases, for example, the Harwell-Boeing Sparse Matrix Collection. If successful, the research proposed will be significant because it will dramatically improve the robustness of the existing methods and, as a result, significantly drive down the time and cost in computation. It also allows for the development of more robust parallel Krylov subspace methods, for example, by rescheduling the operations into parallelism. The research will also provide ideal topics for class learning and thesis research. Moreover, the PI once participated in research in Chemical and Petroleum Engineering, University of Wyoming, on removing nitrogen oxides from combustion exhaust streams. The resulting methods of the project will promote the collaboration in future because more robust algorithms will then be available to use in solving the PDE models arising from the collaborative study.