Previous: Overview of the BLAS
Up: Contents
Next: Notation
Previous Page: Overview of the BLAS
Next Page: Notation
- Adaptive methods
- 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.
- Choleski 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.
- 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.
- 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.
- Vector norms
- See: Norms.
Previous: Overview of the BLAS
Up: Contents:
Next: Notation
Previous Page: Overview of the BLAS
Next Page: Notation