Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. Part I: Theory
Author(s): de Sturler, Eric
Liesen, Jörg
Type: Research Paper
Abstract: We study block diagonal preconditioners and an efficient variant of constraint preconditioners for general two-by-two block linear systems with zero (2,2) block. We derive block diagonal preconditioners from a splitting of the (1,1)-block of the matrix. From the resulting preconditioned system we derive a smaller, so-called `related' system that yields the solution of the original problem. Solving the related system corresponds to an efficient implementation of constraint preconditioning. We analyze the properties of both classes of preconditioned matrices, in particular their spectrum. Using analytical results we show that the related system matrix has the more favorable spectrum, which in many applications translates into faster convergence for Krylov subspace methods. We show that fast convergence depends mainly on the quality of the splitting, a topic for which a substantial body of theory exists. Our analysis also provides a number of new relations between block-diagonal preconditioners and constraint preconditioners. For constrained problems, solving the the related system produces iterates that satisfy the constraints exactly, just as for systems with a constraint preconditioner. Finally, for the Lagrange multiplier formulation of a constrained optimization problem we show how scaling nonlinear constraints can dramatically improve the convergence for linear systems in a Newton iteration. Our theoretical results are confirmed by numerical experiments on a constrained optimization problem.
Subject(s): saddle point systems
indefinite systems
eigenvalue bounds
Krylov subspace methods
constrained optimization
Issue Date: 5-Oct-2003
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 65F10 Iterative methods for linear systems
65F15 Eigenvalues, eigenvectors
65D18 Computer graphics and computational geometry
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2003, 36
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 18.05 MB
DownloadShow Preview
Format: Postscript | Size: 14.35 MB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.