A Survey of Robust Preconditioning Methods
Iterative solution methods can not yet be considered as having in general a robust behavior w.r.t. problem parameters and shape of elements. To be robust they need a robust preconditioning method. There are three classes of preconditioning methods: (i) Op
- PDF / 1,881,670 Bytes
- 20 Pages / 481.92 x 691.68 pts Page_size
- 60 Downloads / 202 Views
Computing © Springer-Verlag
200!
A Survey of Robust Preconditioning Methods O. Axelsson, Nijmegen Dedicated to Professor Tetsuro Yamamoto on the occasion of his 65th birthday Abstract Iterative solution methods can not yet be considered as having in general a robust behavior w.r. t. problem parameters and shape of elements. To be robust they need a robust preconditioning method. There are three classes of preconditioning methods: (i) Operator based splitting methods, (ii) Element matrix based splitting methods and (iii) Global matrix based splitting methods. Already important results have been achieved but work is still ongoing in the construction of such preconditioners. The paper gives a background to the methods and gives some more detailed examples of some of the methods when used for symmetric and positive definite matrices.
AMS Subject Classifications: 65FlO, 65F50, CR: G1.3. Key Words: Systems of linear equations, conjugate gradient method, preconditioning methods, condition numbers.
1. Classification of Preconditioning Methods Let A be a given nonsingular operator or matrix. Frequently A is a differential operator for a boundary value problem or a corresponding finite element matrix. By a preconditioning B we refer to a matrix or operator splitting, A = B - R to be used in an iterative solution method for the equation Ax = b, to improve either the spectral radius of B-iR, the condition number of the matrix B-iA or, more generally, to improve its distribution of eigenvalues to enable a faster rate of convergence. Here B is an operator which, in some way, is much easier to solve systems with than with A. There are three major classes of preconditioning or splitting methods: a) Operator splitting or defect-correction methods.
Here a simpler but more readily solvable operator is used as preconditioner or corrector for the given operator. Often it suffices to perform a few iteration steps without sacrificing approximation order of the given operator, which is then used in the computation of the defect only. A well known example of such a method is defect-correction with a monotone correction operator, such as an upwind approximation for convection-diffuG. Alefeld et al. (eds.), Topics in Numerical Analysis © Springer-Verlag/Wien 2001
o. Axelsson
30
sion problems. Another example is the preconditioner derived from separate displacement orderings for systems ofPDEs as arises for linear elasticity theory problems. See Section 3 for a detailed description. A similar, but algebraically constructed type of method is based on deletion of positive off-diagonal matrix entries and diagonal compensation of them. The so derived matrix can then be preconditioned more easily by some other method, which requires M-matrices, for instance. See [2, 26, 27] for further details. b) Element mesh based preconditioners. Here one utilizes a sequence of meshes (sometimes only two levels) in a successive refinement method. The matrix is partitioned in two by two blocks corresponding to the partitioning of nodes on each level in
Data Loading...
