Flexible Krylov Methods and Schwarz Preconditioners

建议数：0207525Krylov子空间方法是目前解线性代数方程组的主要迭代方法，特别是对于那些由微分方程组离散化产生的迭代方法。这些方法的优点部分来自于预条件算子的使用，预条件算子是改变线性系统的光谱属性的矩阵(或算子)。近年来，一些研究人员(包括PI)提出并分析了Krylov方法，其中允许预条件因子从一个(外部)步骤改变到下一个步骤。具体地说，预条件函数本身可以是Krylov方法。这些内-外方法中的一些已经在实验中被证明是有效的。作为该项目的一部分，建议对这类一般的内外方法进行详细的分析。这一分析应该让我们对这些方法有一个理解，并指出如何思考新的内外方法。所有这些方法都将进行实验，并与重新启动的方法进行比较。不精确Krylov子空间方法指的是每一步的矩阵-向量乘法不是精确执行的情况。这种情况出现在许多应用中，包括分块矩阵和每一步Schur补的近似。一些研究人员的实验表明，随着迭代的进行，可以允许不精确度增加。我们建议详细研究这一现象，以提供对这一现象的理解，并设计出在计算中使用的不精确量的界限。在过去的几年里，我们发展了一种新的加法和乘法Schwarz方法的代数公式。这些方法被广泛地应用于工业、科学和工程应用中，被用作(并行)解微分方程组的固定的预条件。这一新的表述使我们能够利用丰富的线性代数理论来研究这些方法。这一新理论补充了通常用于这些方法的分析理论。例如，我们最近完成了对限制性加性Schwarz(RAS)预条件算子的分析，但没有得到解析收敛的结果。在本项目的第二部分，建议进一步使用这个新的公式来分析其他Schwarz变体。

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.