E-Book Overview
The first four chapters of this book give a comprehensive and unified theory of the Krylov methods. Many of these are shown to be particular examples ofthe block conjugate-gradient algorithm and it is this observation thatpermits the unification of the theory. The two major sub-classes of thosemethods, the Lanczos and the Hestenes-Stiefel, are developed in parallel asnatural generalisations of the Orthodir (GCR) and Orthomin algorithms. Theseare themselves based on Arnoldi's algorithm and a generalised Gram-Schmidtalgorithm and their properties, in particular their stability properties,are determined by the two matrices that define the block conjugate-gradientalgorithm. These are the matrix of coefficients and the preconditioningmatrix.In Chapter 5 the"transpose-free" algorithms based on the conjugate-gradient squared algorithm are presented while Chapter 6 examines the various ways in which the QMR technique has been exploited. Look-ahead methods and general block methods are dealt with in Chapters 7 and 8 while Chapter 9 is devoted to error analysis of two basic algorithms.In Chapter 10 the results of numerical testing of the more important algorithms in their basic forms (i.e. without look-ahead or preconditioning) are presented and these are related to the structure of the algorithms and the general theory. Graphs illustrating the performances of various algorithm/problem combinations are given via a CD-ROM.Chapter 11, by far the longest, gives a survey of preconditioning techniques. These range from the old idea of polynomial preconditioning via SOR and ILU preconditioning to methods like SpAI, AInv and the multigrid methods that were developed specifically for use with parallel computers. Chapter 12 is devoted to dual algorithms like Orthores and the reverse algorithms of Hegedus. Finally certain ancillary matters like reduction to Hessenberg form, Chebychev polynomials and the companion matrix are described in a series of appendices. ?·comprehensive and unified approach?·up-to-date chapter on preconditioners?·complete theory of stability?·includes dual and reverse methods?·comparison of algorithms on CD-ROM?·objective assessment of algorithms
E-Book Content
Krylov Solvers for Linear Algebraic Systems Charles George Broyden Maria Teresa Vespucci Elsevier KRYLOV SOLVERS FOR LINEAR ALGEBRAIC SYSTEMS Krylov Solvers STUDIES IN COMPUTATIONAL MATHEMATICS 11 Editors: C.K. CHUI Stanford University Stanford, CA, USA P. MONK University of Delaware Newark, DE, USA L. WUYTACK University of Antwerp Antwerp, Belgium ELSEVIER Amsterdam - Boston - Heidelberg - London - New York - Oxford - Paris San Diego - San Francisco - Singapore - Sydney - Tokyo KRYLOV SOLVERS FOR LINEAR ALGEBRAIC SYSTEMS Krylov Solvers Charles George BROYDEN University of Bologna Italy Maria Teresa VESPUCCI University of Bergamo Italy ELSEVIER 2004 Amsterdam - Boston - Heidelberg - London - New York - Oxford - Paris San Diego - San Francisco - Singapore - Sydney - Tokyo ELSEVIERB.V. Sara Burgerhartstraat 25 P.O. Box 211,1000 AE Amsterdam, The Netherlands ELSEVIER Inc. 525 B Street Suite 1900, San Diego CA 92101-4495, USA ELSEVIER Ltd. The Boulevard Langford Lane, Kidlington, Oxford OX5 1GB, UK ELSEVIER Ltd. 84 Theobalds Road London WC1X 8RR UK © 2004 Elsevier B.V. All rights reserved. This work is protected under copyright by Elsevier B.V., and the following terms and conditions apply to its use: Photocopying Single photocopies of single chapters may be made for personal use as allowed by national copyright laws. Permission of the Publisher and payment of a fee is required for all other photocopying, including multiple or systematic copying, copying for advertising or promotional purposes, resale, and all forms