NAG Library Chapter Introduction

F – Linear Algebra

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:

• Chapter F01 – Matrix Operations, Including Inversion
• Chapter F02 – Eigenvalues and Eigenvectors
• Chapter F03 – Determinants
• Chapter F04 – Simultaneous Linear Equations
• Chapter F05 – Orthogonalization
• Chapter F06 – Linear Algebra Support Routines
• Chapter F07 – Linear Equations (LAPACK)
• Chapter F08 – Least Squares and Eigenvalue Problems (LAPACK)
• Chapter F11 – Large Scale Linear Systems
• Chapter F12 – Large Scale Eigenproblems
• Chapter F16 – Further Linear Algebra Support Routines

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 routines for these operations themselves utilize lower level support routines, typically from Chapters F06 and F16. You will not normally need to be concerned with these support routines.

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 routines developed within that project are 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 routines do not compromise efficiency on conventional machines.

Chapters F11 and F12 contain routines for solving large scale problems, but a few earlier routines 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). For the three main problem areas listed above you generally have the choice of selecting a single routine to solve the problem, a so-called Black Box routine, or selecting more than one routine to solve the problem, such as a factorization routine followed by a solve routine, so-called General Purpose routines. The following sections indicate which chapters are relevant to particular problem areas.

The Black Box routines for solving linear equations of the form where $A$ is an $n$ by $n$ 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 routine from Chapter F01 or Chapter F03 and combining them with a solve routine in Chapter F04, or by selecting a factorization and a solve routine from Chapter F07. For large sparse problems, routines from Chapter F11 should be used. In addition there are routines to estimate condition numbers in Chapters F04 and F07, and routines to give error estimates in Chapters F02, F04 and F07.

There are routines 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 routine, you are recommended to consult the F04 Chapter Introduction in the first instance, although the decision trees will often in fact point to a routine in Chapters F07 or F11.

The Black Box routines for solving linear least squares problems of the form and $A$ is an $m$ by $n$, possibly rank deficient, matrix, are to be found in Chapters F04 and F08. Such problems can also be solved by selecting one or more general purpose factorization routines from Chapters F02 or F08 and combining them with a solve routine in Chapter F04, which also contains a routine to compute covariance matrices, or Chapter F08. Linear least squares problems can also be solved by routines in the statistical Chapter G02.

In order to select the appropriate routine, 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 routines for solving linear equality constrained least squares problems, and the general Gauss–Markov linear model problem. Chapter E04 contains a routine to solve general linearly constrained linear least squares problems.

The Black Box routines for solving standard matrix eigenvalue problems of the form where $A$ is an $n$ by $n$ real or complex matrix, and generalized matrix eigenvalue problems of the form where $B$ is also an $n$ by $n$ matrix, are to be found in Chapters F02, F08 and F12. These eigenvalue problems can also be solved by a combination of General Purpose routines (which are mostly in Chapter F08, but a few are in Chapter F02).

There are routines to cater for various types of matrices, including general, symmetric or Hermitian, and banded and sparse matrices.

Similarly, the Black Box routines for finding singular values and/or singular vectors of an $m$ by $n$ real or complex matrix $A$ are to be found in Chapters F02 and F08, and such problems may also be solved by routines from Chapter F12, and by combining routines from Chapter F08.

In order to select the appropriate routine, you are recommended to consult Chapters F02 and F08 in the first instance.

Routines for matrix inversion are to be found in Chapters F01 and F07. You are recommended to consult Chapter F01 in the first instance, although the decision tree will often in fact point to a routine in Chapter F07. It should be noted that you are strongly encouraged not to use matrix inversion routines for the solution of linear equations, since these can be solved more efficiently and accurately using routines 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.

Routines to compute determinants of matrices are to be found in Chapter F03. You are recommended to consult Chapter F03 in the first instance.

Routines for various sorts of matrix operation are to be found in Chapter F01, including matrix transposition, addition and multiplication, and conversion between different matrix representation storage formats. Facilities for matrix manipulation can also be found in Chapter F06 (see next section).

Chapters F06 and F16 contain contain a variety of routines 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. Chapters F06 and F16 contain routines 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 routines in these chapters 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 routines, especially the BLAS, are extensively used by other NAG Library routines.

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