Iterative methods that collect information
about the coefficient matrix during the iteration process, and use
this to speed up convergence.
Backward error
The size of perturbations of the
coefficient matrix and of the right hand side of a linear
system , such that the computed iterate is the
solution of .
Band matrix
A matrix for which there are nonnegative
constants , such that if or . The
two constants , are called the left and right halfbandwidth
respectively.
Black box
A piece of software that can be used without
knowledge of its inner workings; the user supplies the input, and
the output is assumed to be correct.
BLAS
Basic Linear Algebra Subprograms; a set of commonly
occurring vector and matrix operations for dense linear algebra.
Optimized (usually assembly coded) implementations of the BLAS exist
for various computers; these will give a higher performance than
implementation in high level programming languages.
Block factorization
See: Block matrix operations.
Block matrix operations
Matrix operations expressed in terms of
submatrices.
Breakdown
The occurrence of a zero divisor in an iterative
method.
Cholesky decomposition
Expressing a symmetric matrix as a
product of a lower triangular matrix and its transpose ,
that is, .
Condition number
See: Spectral condition number.
Convergence
The fact whether or not, or the rate at which, an
iterative method approaches the solution of a linear system.
Convergence can be
Linear: some measure of the distance
to the solution decreases by a constant factor in each iteration.
Superlinear: the measure of the
error decreases by a growing factor.
Smooth: the measure of the error
decreases in all or most iterations, though not necessarily by the
same factor.
Irregular: the measure of the error
decreases in some iterations and increases in others. This
observation unfortunately does not imply anything about the ultimate
convergence of the method.
Stalled: the measure of the error
stays more or less constant during a number of iterations. As above,
this does not imply anything about the ultimate convergence of the
method.
Dense matrix
Matrix for which the number of zero elements is
too small to warrant specialized algorithms to exploit these zeros.
Diagonally dominant matrix
See: Matrix properties
Direct method
An algorithm that produces the solution to a
system of linear equations in a number of operations that is
determined a priori by the size of the system. In exact arithmetic,
a direct method yields the true solution to the system. See:
Iterative method.
Distributed memory
See: Parallel computer.
Divergence
An iterative method is said to diverge if it does
not converge in a reasonable number of iterations, or if some
measure of the error grows unacceptably. However, growth of the
error as such is no sign of divergence: a method with irregular
convergence behavior may ultimately converge, even though the error
grows during some iterations.
Domain decomposition method
Solution method for linear systems
based on a partitioning of the physical domain of the differential
equation. Domain decomposition methods typically involve (repeated)
independent system solution on the subdomains, and some way of
combining data from the subdomains on the separator part of the
domain.
Field of values
Given a matrix , the field of values is the
set . For symmetric matrices this is the range
.
Fill
A position that is zero in the original matrix but not
in an exact factorization of . In an incomplete factorization,
some fill elements are discarded.
Forward error
The difference between a computed iterate and the
true solution of a linear system, measured in some vector norm.
Halfbandwidth
See: Band matrix.
Ill-conditioned system
A linear system for which the
coefficient matrix has a large condition number. Since in many
applications the condition number is proportional to (some power of)
the number of unknowns, this should be understood as the constant of
proportionality being large.
IML++
A mathematical template library in C++
of iterative method for solving linear systems.
Incomplete factorization
A factorization obtained by discarding
certain elements during the factorization process (`modified' and
`relaxed' incomplete factorization compensate in some way for
discarded elements). Thus an incomplete factorization of a
matrix will in general satisfy ; however, one hopes
that the factorization will be close enough to to function
as a preconditioner in an iterative method.
Iterate
Approximation to the solution of a linear system in any
iteration of an iterative method.
Iterative method
An algorithm that produces a sequence of
approximations to the solution of a linear system of equations; the
length of the sequence is not given a priori by the size of the
system. Usually, the longer one iterates, the closer one is able to
get to the true solution. See: Direct method.
Krylov sequence
For a given matrix and vector , the
sequence of vectors , or a finite initial part of
this sequence.
Krylov subspace
The subspace spanned by a Krylov sequence.
LAPACK
A mathematical library of linear algebra routine for
dense systems solution and eigenvalue calculations.
Lower triangular matrix
Matrix for which
if .
factorization
A way of writing a matrix as a product
of a lower triangular matrix and a unitary matrix , that is,
.
factorization / decomposition
Expressing a matrix
as a product of a lower triangular matrix and an upper
triangular matrix , that is, .
-Matrix
See: Matrix properties.
Matrix norms
See: Norms.
Matrix properties
We call a square matrix
Symmetric
if for all , .
Positive definite
if it satisfies for all nonzero
vectors .
Diagonally dominant
if ; the
excess amount is called
the diagonal dominance of the matrix.
An -matrix
if for , and it is
nonsingular with for all , .
Message passing
See: Parallel computer.
Multigrid method
Solution method for linear systems based on
restricting and extrapolating solutions between a series of nested
grids.
Modified incomplete factorization
See: Incomplete
factorization.
Mutually consistent norms
See: Norms.
Natural ordering
See: Ordering of unknowns.
Nonstationary iterative method
Iterative method that has
iteration-dependent coefficients.
Normal equations
For a nonsymmetric or indefinite (but
nonsingular) system of equations , either of the related
symmetric systems () and (; ). For complex , is replaced with in the above
expressions.
Norms
A function is called a vector norm
if
for all , and only if .
for all , .
for all , .
The same properties hold for matrix norms. A matrix norm and a
vector norm (both denoted ) are called a mutually
consistent pair if for all matrices and vectors
Ordering of unknowns
For linear systems derived from a partial
differential equation, each unknown corresponds to a node in the
discretization mesh. Different orderings of the unknowns correspond
to permutations of the coefficient matrix. The convergence speed of
iterative methods may depend on the ordering used, and often the
parallel efficiency of a method on a parallel computer is strongly
dependent on the ordering used. Some common orderings for
rectangular domains are:
The natural ordering; this is the consecutive numbering by
rows and columns.
The red/black ordering; this is the numbering where all nodes
with coordinates for which is odd are numbered
before those for which is even.
The ordering by diagonals; this is the ordering where nodes
are grouped in levels for which is constant. All nodes in
one level are numbered before the nodes in the next level.
For matrices from problems on less regular domains, some common
orderings are:
The Cuthill-McKee ordering; this starts from one point, then
numbers its neighbors, and continues numbering points that are
neighbors of already numbered points. The Reverse Cuthill-McKee
ordering then reverses the numbering; this may reduce the amount
of fill in a factorization of the matrix.
The Minimum Degree ordering; this orders the matrix rows by
increasing numbers of nonzeros.
Parallel computer
Computer with multiple independent processing
units. If the processors have immediate access to the same memory,
the memory is said to be shared; if processors have private memory
that is not immediately visible to other processors, the memory is
said to be distributed. In that case, processors communicate by
message-passing.
Pipelining
See: Vector computer.
Positive definite matrix
See: Matrix properties.
Preconditioner
An auxiliary matrix in an iterative method that
approximates in some sense the coefficient matrix or its inverse.
The preconditioner, or preconditioning matrix, is applied in every
step of the iterative method.
Red/black ordering
See: Ordering of unknowns.
Reduced system
Linear system obtained by eliminating certain
variables from another linear system. Although the number of
variables is smaller than for the original system, the matrix of a
reduced system generally has more nonzero entries. If the original
matrix was symmetric and positive definite, then the reduced system
has a smaller condition number.
Relaxed incomplete factorization
See: Incomplete factorization.
Residual
If an iterative method is employed to solve for in
a linear system , then the residual corresponding to a
vector is .
Search direction
Vector that is used to update an iterate.
Shared memory
See: Parallel computer.
Simultaneous displacements, method of
Jacobi method.
Sparse matrix
Matrix for which the number of zero elements is
large enough that algorithms avoiding operations on zero elements
pay off. Matrices derived from partial differential equations
typically have a number of nonzero elements that is proportional to
the matrix size, while the total number of matrix elements is the
square of the matrix size.
Spectral condition number
The product
where and denote the largest and
smallest eigenvalues, respectively. For linear systems derived from
partial differential equations in 2D, the condition number is
proportional to the number of unknowns.
Spectral radius
The spectral radius of a matrix is
.
Spectrum
The set of all eigenvalues of a matrix.
Stationary iterative method
Iterative method that performs in
each iteration the same operations on the current iteration vectors.
Stopping criterion
Since an iterative method computes
successive approximations to the solution of a linear system, a
practical test is needed to determine when to stop the iteration.
Ideally this test would measure the distance of the last iterate to
the true solution, but this is not possible. Instead, various other
metrics are used, typically involving the residual.
Storage scheme
The way elements of a matrix are stored in the
memory of a computer. For dense matrices, this can be the decision
to store rows or columns consecutively. For sparse matrices, common
storage schemes avoid storing zero elements; as a result they
involve indices, stored as integer data, that indicate where the
stored elements fit into the global matrix.
Successive displacements, method of
Gauss-Seidel method.
Symmetric matrix
See: Matrix properties.
Template
Description of an algorithm, abstracting away from
implementational details.
Tune
Adapt software for a specific application and computing
environment in order to obtain better performance in that case only.
itemize
Upper triangular matrix
Matrix for which
if .
Vector computer
Computer that is able to process consecutive
identical operations (typically additions or multiplications)
several times faster than intermixed operations of different types.
Processing identical operations this way is called `pipelining' the
operations.