Chapter 19
Linear Algebraic Solvers and Eigenvalue Analysis
Henk A. van der Vorst
Utrecht University, Utrecht, The Netherlands
1 Introduction 551
2 Mathematical Preliminaries 551
3 Direct Methods for Linear Systems 553
4 Preconditioning 560
5 Incomplete LU Factorizations 562
6 Methods for the Complete Eigenproblem 567
7 Iterative Methods for the Eigenproblem 571
Notes 574
References 575
1 INTRODUCTION
In this chapter, an overview of the most widely used
numerical methods for the solution of linear systems of
equations and for eigenproblems is presented.
For linear systems Ax = b, with A a real square non-
singular n × n matrix, direct solution methods and iterative
methods are discussed. The direct methods are variations
on Gaussian elimination. The iterative methods are the so-
called Krylov projection–type methods, and they include
popular methods such as Conjugate Gradients, MINRES,
Bi-Conjugate Gradients, QMR, Bi-CGSTAB, and GMRES.
Iterative methods are often used in combination with
the so-called preconditioning operators (easily invertible
approximations for the operator of the system to be solved).
We will give a brief overview of the various preconditioners
that exist.
For the eigenproblems of the type Ax = λx,theQR
method, which is often considered to be a direct method
Encyclopedia of Computational Mechanics, Edited by Erwin
Stein, Ren
´
e de Borst and Thomas J.R. Hughes. Volume 1: Funda-
mentals.
2004 John Wiley & Sons, Ltd. ISBN: 0-470-84699-2.
because of its very fast convergence, is discussed. Strictly,
speaking, there are no direct methods for the eigenprob-
lem; all methods are necessarily iterative. The QR method
is expensive for larger values of n, and for these larger
values, a number of iterative methods, including the Lanc-
zos method, Arnoldi’s method, and the Jacobi–Davidson
method are presented.
For a general background on linear algebra for numerical
applications, see Golub and Van Loan (1996) and Stewart
(1998). Modern iterative methods for linear systems are
discussed in van der Vorst (2003). A basic introduction
with simple software is presented in Barrett et al. (1994).
A complete overview of algorithms for eigenproblems,
including pointers to software, is given in Bai et al. (2000).
Implementation aspects for high-performance computers
are discussed in detail in Dongarra et al. (1998).
Some useful state-of-the-art papers have appeared; we
mention papers on the history of iterative methods by Golub
and van der Vorst (2000) and Saad and van der Vorst
(2000). An overview on parallelizable aspects of sparse
matrix techniques is presented in Duff and van der Vorst
(1999). A state-of-the-art overview for preconditioners is
presented in Benzi (2002).
The purpose of this chapter is to make the reader familiar
with the ideas and the usage of iterative methods. We expect
that guided with sufficient knowledge about the background
of iterative methods, one will be able to make a proper
choice for a particular class of problems. It will also provide
guidance on how to tune these methods, in particular, for
the selection or construction of effective preconditioners.
2 MATHEMATICAL PRELIMINARIES
In this section, some basic notions and notations on linear
systems and eigenproblems have been collected.
剩余25页未读，继续阅读
评论0