Flexible Krylov Methods and Schwarz Preconditioners

Temple University, Philadelphia PA

Investigators

Abstract

title: Flexible Krylov methods and Schwarz preconditioners. Proposal Number: 0207525 Krylov 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.