文档介绍：Sparse Direct Methods: An Introduction
J. A. Scott
Department putation and Information, Rutherford Appleton Laboratory,
Chilton, Didcot, Oxon OX11 0RA, England. (J.******@)
Abstract. The solution of large-scale linear systems lies at the heart of pu-
tations in science, engineering, industry, and (more recently) this paper, we
give a brief introduction to direct methods based on Gaussian elimination for the solu-
tion of such discuss the methods with reference to the sparse direct solvers
that are available in the Harwell Subroutine briefly consider large sparse
eigenvalue problems and show how the efficient solution of such problems depends upon
the efficient solution of sparse linear systems.
1 Introduction
Sparse matrices arise in very many application areas, including such diverse
fields as structural analysis, chemical engineering, surveying, and economics. A
matrix is sparse if many of its coefficients are zero and there is an advantage
in exploiting the zeros. In this paper, we present a brief introduction to direct
methods for the solution of large sparse linear systems of equations
Ax = b. (1)
We are concerned with methods that are based on Gaussian elimination. That
is, pute an LU factorization of a permutation of A
PAQ = LU,
where P and Q are permutation matrices and L and U are lower and upper
triangular matrices, respectively. These factors are used to solve the system (1)
through the forward elimination
Ly = Pb
followed by the back substitution
Uz = y.
The required solution x is then the permuted vector x = Qz. When A is sym-
metric positive definite, it is normal to use the Cholesky factorization
PAPT = LLT .
H. Dreyssé (Ed.): Workshop 1998, LNP 535, pp. 401−415, 1999.
Springer-Verlag Berlin Heidelberg 1999
402 . Scott
For more general symmetric matrices, the factorization
PAPT = LDLT ,
is more appropriate. For a stable position in the indefinite case, t