NAG Library Chapter Introduction
f – Linear Algebra
1
Introduction
The
f
Chapters of the Library are concerned with linear algebra and cover a large area. This general introduction is intended to help you decide which particular
f
Chapter is relevant to your problem. The following Chapters are currently available:
The principal problem areas addressed by the above Chapters are
- Systems of linear equations
- Linear least squares problems
- Eigenvalue and singular value problems
The solution of these problems usually involves several matrix operations, such as a matrix factorization followed by the solution of the factorized form, and the functions for these operations themselves utilize lower level support functions, typically from
Chapter f16.
You will not normally need to be concerned with these support functions.
NAG has been involved in a project, called LAPACK (see
Anderson et al. (1999)), to develop a linear algebra package for modern high-performance computers, and the functions developed within that project are
being
incorporated into the Library as
Chapters f07 and
f08. It should be emphasized that, while the LAPACK project has been concerned with high-performance computers, the functions do not compromise efficiency on conventional machines.
Chapters f11 and
f12 contain functions for solving large scale problems, but a few earlier functions are still located in
Chapters f01,
f02 and
f04.
For background information on numerical algorithms for the solution of linear algebra problems see
Golub and Van Loan (1996).
In some problem areas you have
the choice of selecting a single function to solve the problem, a so-called
Black Box function, or selecting more than one function to solve the problem, such as a factorization function followed by a solve function, so-called
General Purpose functions. The following sections indicate which chapters are relevant to particular problem areas.
2
Linear Equations
The Black Box functions for solving linear equations of the form
where
is an
by
real or complex nonsingular matrix, are to be found in
Chapters f04 and
f07. Such equations can also be solved by selecting a general purpose factorization function from
Chapter f01
and combining them with a solve function in
Chapter f04, or by selecting a factorization and a solve function from
Chapter f07. For large sparse problems, functions from
Chapter f11 should be used. In addition there are functions to estimate condition numbers
and functions to give error estimates in
Chapters f02,
f04 and
f07.
There are functions to cater for a variety of types of matrix, including general, symmetric or Hermitian, symmetric or Hermitian positive definite, banded, skyline and sparse matrices.
In order to select the appropriate function, you are recommended to consult the
f04 Chapter Introduction in the first instance, although the decision trees will often in fact point to a function in
Chapters f07 or
f11.
3
Linear Least Squares
Functions
for solving linear least squares problems of the form
and
is an
by
, possibly rank deficient, matrix,
can
be solved by selecting one or more general purpose factorization functions from
Chapters f02 or
f08 and combining them with a solve function in
Chapter f04.
Linear least squares problems can also be solved by functions in the statistical
Chapter g02.
In order to select the appropriate function, you are recommended to consult the
f04 Chapter Introduction in the first instance, but if you have additional statistical requirements you may prefer to consult
Section 2.2 in the g02 Chapter Introduction.
Chapter f08 also contains functions for solving linear equality constrained least squares problems, and the general Gauss–Markov linear model problem.
Chapter e04 contains a function to solve general linearly constrained linear least squares problems.
4
Eigenvalue Problems and Singular Value Problems
The Black Box functions for solving standard matrix eigenvalue problems of the form
where
is an
by
real or complex matrix, and generalized matrix eigenvalue problems of the form
where
is also an
by
matrix, are to be found in
Chapters f02,
f08 and
f12. These eigenvalue problems can also be solved by a combination of General Purpose functions
in
Chapter f08.
There are functions to cater for various types of matrices, including general, symmetric or Hermitian and banded.
Similarly, the Black Box functions for finding singular values and/or singular vectors of an
by
real or complex matrix
are to be found in
Chapters f02 and
f08, and such problems may also be solved by functions from
Chapter f12, and by combining functions from
Chapter f08.
In order to select the appropriate function, you are recommended to consult
Chapters f02 and
f08 in the first instance.
5
Inversion and Determinants
Functions for matrix inversion are to be found in
Chapter f07.
It should be noted that you are strongly encouraged not to use matrix inversion functions for the solution of linear equations, since these can be solved more efficiently and accurately using functions directed specifically at such problems. Indeed many problems, which superficially appear to be matrix inversion, can be posed as the solution of a system of linear equations and this is almost invariably preferable.
Functions to compute determinants of matrices are to be found in
Chapter f03. You are recommended to consult
Chapter f03 in the first instance.
6
Support Functions
Chapter f16 contains
contain a variety of functions to perform elementary algebraic operations involving scalars, vectors and matrices, such as setting up a plane rotation, performing a dot product and computing a matrix norm.
Chapter f16 contains
functions that meet the specification of the BLAS (Basic Linear Algebra Subprograms) (see
Lawson et al. (1979),
Dodson et al. (1991),
Dongarra et al. (1988),
Dongarra et al. (1990) and
Blackford et al. (2002)). The functions in
this chapter
will not normally be required by the general user, but are intended for use by those who require to build specialist linear algebra modules. These functions, especially the BLAS, are extensively used by other NAG C Library functions.
7
References
Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J J, Du Croz J J, Greenbaum A, Hammarling S, McKenney A and Sorensen D (1999) LAPACK Users' Guide (3rd Edition) SIAM, Philadelphia
Blackford L S, Demmel J, Dongarra J J, Duff I S, Hammarling S, Henry G, Heroux M, Kaufman L, Lumsdaine A, Petitet A, Pozo R, Remington K and Whaley R C (2002) An updated set of Basic Linear Algebra Subprograms (BLAS) ACM Trans. Math. Software 28 135–151
Dodson D S, Grimes R G and Lewis J G (1991) Sparse extensions to the Fortran basic linear algebra subprograms ACM Trans. Math. Software 17 253–263
Dongarra J J, Du Croz J J, Duff I S and Hammarling S (1990) A set of Level 3 basic linear algebra subprograms ACM Trans. Math. Software 16 1–28
Dongarra J J, Du Croz J J, Hammarling S and Hanson R J (1988) An extended set of FORTRAN basic linear algebra subprograms ACM Trans. Math. Software 14 1–32
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Lawson C L, Hanson R J, Kincaid D R and Krogh F T (1979) Basic linear algebra supbrograms for Fortran usage ACM Trans. Math. Software 5 308–325