Flexible Krylov Methods and Schwarz Preconditioners

灵活的 Krylov 方法和 Schwarz 预处理器

• 批准号: 0207525
• 负责人: Daniel Szyld
• 金额: $ 22.49万
• 依托单位: Temple University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-01 至 2005-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0207525&HistoricalAwards=false
• 关键词: Flexible; Krylov; Methods; Schwarz; Preconditioners

title: Flexible Krylov methods and Schwarz preconditioners.Proposal Number: 0207525Krylov subspace methods are nowadays the premier iterative methods for the solution of linear algebraic systems of equations, especially for those which arise from the discretization of differential equations. The strength of these methods derives in part by the use of preconditioners, which are matrices (or operators) changing the spectral properties of the linear system. In recent years, several researchers (including the PI), have proposed and analyzed Krylov methods in which the preconditioner is allowed to change from one (outer) step to the next. In particular, the preconditioner can be a Krylov method itself. Some of these inner-outer methods have been shown experimentally to work well. As part of this project, it is proposed to undertake a detailed analysis of general inner-outer methods of this kind. This analysis should give us an understanding of these methods, and also indicate how to think of new inner-outer methods. Experiments will be conducted with all these methods together with comparison with restarted ones. Inexact Krylov subspace methods refer to the situation where the matrix-vector multiplication at each step is not performed exactly. This situation appears in numerous applications, including block matrices and the approximation of Schur complements at each step. It was shown experimentally by some researchers that the amount of inexactness can be allowed to grow as the iterations progress. We propose to study this phenomenon in detail, both to provide an understanding of this phenomenon, and to devise bounds on the amount of inexactness to be used computationally. During the last few years we have developed a new algebraic formulation of additive and multiplicative Schwarz methods. These methods, which are used as fixed) preconditioners for the (parallel) solution of differential equations, are extensively used in industry, science and engineering applications. This new formulation allow us to study these methods using the rich theory of linear algebra. This new theory complements the analytical theory usually used for these methods. For example, we have recently completed the analysis of the Restrictive Additive Schwarz (RAS) preconditioner, for which there is no analytical convergence results.In the second part of this project, it is proposed to further use this new formulation to analyze other Schwarz variants.

标题：灵活的Krylov方法和施瓦茨预处理器。建议编号：0207525 Krylov子空间方法是当今求解线性代数方程组的首要迭代方法，特别是对于那些由微分方程离散化引起的问题。这些方法的强度部分来自于预处理器的使用，预处理器是改变线性系统的谱特性的矩阵（或算子）。近年来，一些研究人员（包括PI）提出并分析了Krylov方法，其中允许预条件子从一个（外部）步骤到下一个步骤发生变化。特别地，预处理器可以是Krylov方法本身。实验表明，这些内部-外部方法中的一些工作得很好。 作为该项目的一部分，建议对这种一般的内外方法进行详细分析。 这种分析应该使我们了解这些方法，并指出如何思考新的内外方法。实验将与所有这些方法一起进行，并与重新启动的比较。不精确Krylov子空间方法是指在每一步的矩阵-向量乘法不是精确执行的情况。这种情况出现在许多应用中，包括分块矩阵和Schur补的每一步近似。一些研究人员的实验表明，随着迭代的进行，不精确的数量可以增加。我们建议详细研究这一现象，既提供了一个理解这一现象，并设计计算使用的不精确量的界限。在过去的几年中，我们已经开发了一个新的代数制定的加法和乘法的施瓦茨方法。这些方法被广泛地用于工业、科学和工程应用中，它们被用作微分方程的（并行）解的（固定）预处理器。这种新的提法使我们能够使用丰富的线性代数理论来研究这些方法。这个新理论补充了通常用于这些方法的分析理论。例如，我们最近完成了对限制性加性施瓦茨（RAS）预条件子的分析，但没有分析收敛结果。在本项目的第二部分中，我们建议进一步使用这个新的公式来分析其他施瓦茨变体。