Robust Krylov Subspace Methods Based on Multiple Lanczos Procedure

Krylov子空间方法被广泛用于科学和工程应用中出现的大型解析线性方程组的迭代求解。标准的Krylov子空间方法是基于单启动Lanczos过程(SSLP)或Arnoldi过程而发展起来的。自从多个启动Lanczos过程(MSLP)被发明以来，MSLP对SSLP具有良好的稳健性。求解多右端线性方程组的块Krylov子空间方法是由MSLP发展而来的。然而，对于具有单一右端的系统，从MSLP导出Krylov子空间方法的研究还很少。当然，多个右手边包括单一右手边作为其特例。然而，PI期望当我们专注于单个右侧的情况时，可以获得更好的方法。Tony Chan和PI最近在这个方向上进行了第一次尝试，并分别开发了ML(N)BiCGSTAB和ML(N)BiCGSTAB方法。本课题的目标是：(1)将现有的标准方法从SSLP推广到MSLP；(2)降低ML(N)BiCGSTAB的存储需求；(3)提高ML(N)BiCG的健壮性。这是朝着实现PI开发并行Krylov子空间方法的长期目标迈出的下一步。PI对ML(N)BiCGSTAB和无转置MSLP算法的初步研究证明了所提目标的可行性。实现这些目标所采用的方法是基于采用从SSLP导出BiCG和从BiCG导出BiCGSTAB(N)的某些方法。结果将用工业数据库进行广泛的检验，例如Harwell-Boeing稀疏矩阵集合。如果成功，这项研究将具有重要意义，因为它将极大地提高现有方法的稳健性，从而显著降低计算时间和成本。它还允许开发更健壮的并行Krylov子空间方法，例如，通过将操作重新调度为并行。本研究也将为课堂学习和论文研究提供理想的课题。此外，PI还曾参与怀俄明大学化学和石油工程的研究，研究如何从燃烧废气中去除氮氧化物。该项目的结果方法将促进未来的合作，因为届时将有更多的稳健算法可用于求解由合作研究产生的PDE模型。

Krylov subspace methods are widely used for the iterative solution of largesparse linear systems that arise in scientific and engineering applications.The standard Krylov subspace methods have been developed based on either thesingle 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-handside as its special case. The PI, however, expects that finer methods can beobtained when we focus on the single right-hand side case. Tony Chan and the PIrecently made the first attempt in this direction and methods named ML(n)BiCGand ML(n)BiCGSTAB, respectively, were developed. This project continues thistrend and aims at (i) generalizing the existing standard methods from SSLPto 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 andthe 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 willdramatically improve the robustness of the existing methods and, as a result,significantly drive down the time and cost in computation. It also allows forthe 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 participatedin research in Chemical and Petroleum Engineering, University of Wyoming, onremoving nitrogen oxides from combustion exhaust streams. The resultingmethods of the project will promote the collaboration in future because more robustalgorithms will then be available to use in solving the PDE modelsarising from the collaborative study.