Robust Krylov Subspace Methods Based on Multiple Lanczos Procedure

基于多Lanczos过程的鲁棒Krylov子空间方法

• 批准号: 0314152
• 负责人: Manchung Yeung
• 金额: $ 7.38万
• 依托单位: University of Wyoming
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-07-15 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0314152&HistoricalAwards=false
• 关键词: Robust; Krylov; Subspace; Methods; Based

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.

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