Iterative solution methods

This presentation is intended to review the state-of-the-art of iterative methods for solving large sparse linear systems such as arising in finite difference and finite element approximations of boundary value problems. However, in order to keep this review within reasonable bounds, we only review those methods for which an algebraic analysis has been achieved. We first review the basic principles and components of iterative solution methods and describe in more detail the main devices used to design preconditioners, showing how the present day complex preconditioners are built through additive and/or multiplicative composition of simpler ones. We also note that acceleration methods may sometimes be viewed, and thus used, as preconditioners. Next, using approximate factorizations as basic framework, we show how their development led to the study of so-called modified methods and why attention then shifted to specific orderings, of multilevel type. Finally we show how the successful development of multigrid and hierarchical basis methods prompted the introduction of equivalent algebraic techniques: besides recursive orderings, an additional step called stabilization by polynomial preconditioning that plays here the role of the W-cycles of the multigrid method and an algebraic version of V-cycles with smoothing. (C) 2004 IMACS. Published by Elsevier B.V. All rights reserved.