NAG FL Interface
F07 (Lapacklin)
Linear Equations (LAPACK)

Settings help

FL Name Style:


FL Specification Language:


1 Scope of the Chapter

This chapter provides routines for the solution of systems of simultaneous linear equations, and associated computations. It provides routines for
Routines are provided for both real and complex data.
For a general introduction to the solution of systems of linear equations, you should turn first to the F04 Chapter Introduction. The decision trees, in Section 4 in the F04 Chapter Introduction, direct you to the most appropriate routines in Chapters F04 or F07 for solving your particular problem. In particular, Chapters F04 and F07 contain Black Box (or driver) routines which enable some standard types of problem to be solved by a call to a single routine. Where possible, routines in Chapter F04 call Chapter F07 routines to perform the necessary computational tasks.
There are two types of driver routines in this chapter: simple drivers which just return the solution to the linear equations; and expert drivers which also return condition and error estimates and, in many cases, also allow equilibration. The simple drivers for real matrices have names of the form F07_AF (D__SV) and for complex matrices have names of the form F07_NF (Z__SV). The expert drivers for real matrices have names of the form F07_BF (D__SVX) and for complex matrices have names of the form F07_PF (Z__SVX).
The routines in this chapter (Chapter F07) handle only dense and band matrices (not matrices with more specialised structures, or general sparse matrices).
The routines in this chapter have all been derived from the LAPACK project (see Anderson et al. (1999)). They have been designed to be efficient on a wide range of high-performance computers, without compromising efficiency on conventional serial machines.

2 Background to the Problems

This section is only a brief introduction to the numerical solution of systems of linear equations. Consult a standard textbook, for example Golub and Van Loan (1996) for a more thorough discussion.

2.1 Notation

We use the standard notation for a system of simultaneous linear equations:
Ax=b (1)
where A is the coefficient matrix, b is the right-hand side, and x is the solution. A is assumed to be a square matrix of order n.
If there are several right-hand sides, we write
AX=B (2)
where the columns of B are the individual right-hand sides, and the columns of X are the corresponding solutions.
We also use the following notation, both here and in the routine documents:
x^ a computed solution to Ax=b, (which usually differs from the exact solution x because of round-off error)
r = b-Ax^ the residual corresponding to the computed solution x^
x= maxi |xi| the -norm of the vector x
x1 = j=1 n |xj| the 1-norm of the vector x
A = maxi j |aij| the -norm of the matrix A
A1 = maxj i=1 n |aij| the 1-norm of the matrix A
|x| the vector with elements |xi|
|A| the matrix with elements |aij|
Inequalities of the form |A||B| are interpreted component-wise, that is |aij||bij| for all i,j.

2.2 Matrix Factorizations

If A is upper or lower triangular, Ax=b can be solved by a straightforward process of backward or forward substitution.
Otherwise, the solution is obtained after first factorizing A, as follows.
General matrices (LU factorization with partial pivoting)
A=PLU  
where P is a permutation matrix, L is lower-triangular with diagonal elements equal to 1, and U is upper-triangular; the permutation matrix P (which represents row interchanges) is needed to ensure numerical stability.
Symmetric positive definite matrices (Cholesky factorization)
A=UTU   or   A=LLT  
where U is upper triangular and L is lower triangular.
Symmetric positive semidefinite matrices (pivoted Cholesky factorization)
A=PUTUPT  or  A=PLLTPT  
where P is a permutation matrix, U is upper triangular and L is lower triangular. The permutation matrix P (which represents row-and-column interchanges) is needed to ensure numerical stability and to reveal the numerical rank of A.
Symmetric indefinite matrices (Bunch–Kaufman factorization)
A = PUD UT PT   or   A = PLD LT PT  
where P is a permutation matrix, U is upper triangular, L is lower triangular, and D is a block diagonal matrix with diagonal blocks of order 1 or 2; U and L have diagonal elements equal to 1, and have 2×2 unit matrices on the diagonal corresponding to the 2×2 blocks of D. The permutation matrix P (which represents symmetric row-and-column interchanges) and the 2×2 blocks in D are needed to ensure numerical stability. If A is in fact positive definite, no interchanges are needed and the factorization reduces to A=UDUT or A=LDLT with diagonal D, which is simply a variant form of the Cholesky factorization.

2.3 Solution of Systems of Equations

Given one of the above matrix factorizations, it is straightforward to compute a solution to Ax=b by solving two subproblems, as shown below, first for y and then for x. Each subproblem consists essentially of solving a triangular system of equations by forward or backward substitution; the permutation matrix P and the block diagonal matrix D introduce only a little extra complication:
General matrices ( LU factorization)
Ly=PTb Ux=y  
Symmetric positive definite matrices (Cholesky factorization)
UTy=b Ux=y   or   Ly=b LTx=y  
Symmetric indefinite matrices (Bunch–Kaufman factorization)
PUDy=b UTPTx=y   or   PLDy=b LTPTx=y  

2.4 Sensitivity and Error Analysis

2.4.1 Normwise error bounds

Frequently, in practical problems the data A and b are not known exactly, and it is then important to understand how uncertainties or perturbations in the data can affect the solution.
If x is the exact solution to Ax=b, and x+δx is the exact solution to a perturbed problem (A+δA)(x+δx)=(b+δb), then
δx x κ(A) (δA A +δb b )+(second-order terms)  
where κ(A) is the condition number of A defined by
κ(A) = A.A-1 . (3)
In other words, relative errors in A or b may be amplified in x by a factor κ(A). Section 2.4.2 discusses how to compute or estimate κ(A).
Similar considerations apply when we study the effects of rounding errors introduced by computation in finite precision. The effects of rounding errors can be shown to be equivalent to perturbations in the original data, such that δA A and δb b are usually at most p(n)ε, where ε is the machine precision and p(n) is an increasing function of n which is seldom larger than 10n (although in theory it can be as large as 2n-1).
In other words, the computed solution x^ is the exact solution of a linear system (A+δA)x^=b+δb which is close to the original system in a normwise sense.

2.4.2 Estimating condition numbers

The previous section has emphasized the usefulness of the quantity κ(A) in understanding the sensitivity of the solution of Ax=b. To compute the value of κ(A) from equation (3) is more expensive than solving Ax=b in the first place. Hence it is standard practice to estimate κ(A), in either the 1-norm or the -norm, by a method which only requires O(n2) additional operations, assuming that a suitable factorization of A is available.
The method used in this chapter is Higham's modification of Hager's method (see Higham (1988)). It yields an estimate which is never larger than the true value, but which seldom falls short by more than a factor of 3 (although artificial examples can be constructed where it is much smaller). This is acceptable since it is the order of magnitude of κ(A) which is important rather than its precise value.
Because κ(A) is infinite if A is singular, the routines in this chapter actually return the reciprocal of κ(A).

2.4.3 Scaling and Equilibration

The condition of a matrix and hence the accuracy of the computed solution, may be improved by scaling; thus if D1 and D2 are diagonal matrices with positive diagonal elements, then
B = D1 A D2  
is the scaled matrix. A general matrix is said to be equilibrated if it is scaled so that the lengths of its rows and columns have approximately equal magnitude. Similarly a general matrix is said to be row-equilibrated (column-equilibrated) if it is scaled so that the lengths of its rows (columns) have approximately equal magnitude. Note that row scaling can affect the choice of pivot when partial pivoting is used in the factorization of A.
A symmetric or Hermitian positive definite matrix is said to be equilibrated if the diagonal elements are all approximately equal to unity.
For further information on scaling and equilibration see Section 3.5.2 of Golub and Van Loan (1996), Section 7.2, 7.3 and 9.8 of Higham (1988) and Section 5 of Chapter 4 of Wilkinson (1965).
Routines are provided to return the scaling factors that equilibrate a matrix for general, general band, symmetric and Hermitian positive definite and symmetric and Hermitian positive definite band matrices.

2.4.4 Componentwise error bounds

A disadvantage of normwise error bounds is that they do not reflect any special structure in the data A and b – that is, a pattern of elements which are known to be zero – and the bounds are dominated by the largest elements in the data.
Componentwise error bounds overcome these limitations. Instead of the normwise relative error, we can bound the relative error in each component of A and b:
maxijk (|δaij| |aij| ,|δbk| |bk| ) ω  
where the component-wise backward error bound ω is given by
ω= maxi |ri| (|A|.|x^|+|b|)i .  
Routines are provided in this chapter which compute ω, and also compute a forward error bound which is sometimes much sharper than the normwise bound given earlier:
x-x^ x |A-1|.|r| x .  
Care is taken when computing this bound to allow for rounding errors in computing r. The norm |A-1|.|r| is estimated cheaply (without computing A-1) by a modification of the method used to estimate κ(A).

2.4.5 Iterative refinement of the solution

If x^ is an approximate computed solution to Ax=b, and r is the corresponding residual, then a procedure for iterative refinement of x^ can be defined as follows, starting with x0=x^:
In Chapter F04, routines are provided which perform this procedure using additional precision to compute r, and are thus able to reduce the forward error to the level of machine precision.
The routines in this chapter do not use additional precision to compute r, and cannot guarantee a small forward error, but can guarantee a small backward error (except in rare cases when A is very ill-conditioned, or when A and x are sparse in such a way that |A|.|x| has a zero or very small component). The iterations continue until the backward error has been reduced as much as possible; usually only one iteration is needed.

2.5 Matrix Inversion

It is seldom necessary to compute an explicit inverse of a matrix. In particular, do not attempt to solve Ax=b by first computing A-1 and then forming the matrix-vector product x=A-1b; the procedure described in Section 2.3 is more efficient and more accurate.
However, routines are provided for the rare occasions when an inverse is needed, using one of the factorizations described in Section 2.2.

2.6 Packed Storage Formats

Routines which handle symmetric matrices are usually designed so that they use either the upper or lower triangle of the matrix; it is not necessary to store the whole matrix. If the upper or lower triangle is stored conventionally in the upper or lower triangle of a two-dimensional array, the remaining elements of the array can be used to store other useful data.
However, that is not always convenient, and if it is important to economize on storage, the upper or lower triangle can be stored in a one-dimensional array of length n(n+1)/2 or a two-dimensional array with n(n+1)/2 elements; in other words, the storage is almost halved.
The one-dimensional array storage format is referred to as packed storage; it is described in Section 3.3.2. The two-dimensional array storage format is referred to as Rectangular Full Packed (RFP) format; it is described in Section 3.3.3. They may also be used for triangular matrices.
Routines designed for these packed storage formats perform the same number of arithmetic operations as routines which use conventional storage. Those using a packed one-dimensional array are usually less efficient, especially on high-performance computers, so there is then a trade-off between storage and efficiency. The RFP routines are as efficient as for conventional storage, although only a small subset of routines use this format.

2.7 Band and Tridiagonal Matrices

A band matrix is one whose nonzero elements are confined to a relatively small number of subdiagonals or superdiagonals on either side of the main diagonal. A tridiagonal matrix is a special case of a band matrix with just one subdiagonal and one superdiagonal. Algorithms can take advantage of bandedness to reduce the amount of work and storage required. The storage scheme used for band matrices is described in Section 3.3.4.
The LU factorization for general matrices, and the Cholesky factorization for symmetric and Hermitian positive definite matrices both preserve bandedness. Hence routines are provided which take advantage of the band structure when solving systems of linear equations.
The Cholesky factorization preserves bandedness in a very precise sense: the factor U or L has the same number of superdiagonals or subdiagonals as the original matrix. In the LU factorization, the row-interchanges modify the band structure: if A has kl subdiagonals and ku superdiagonals, then L is not a band matrix but still has at most kl nonzero elements below the diagonal in each column; and U has at most kl+ku superdiagonals.
The Bunch–Kaufman factorization does not preserve bandedness, because of the need for symmetric row-and-column permutations; hence no routines are provided for symmetric indefinite band matrices.
The inverse of a band matrix does not in general have a band structure, so no routines are provided for computing inverses of band matrices.

2.8 Block Partitioned Algorithms

Many of the routines in this chapter use what is termed a block partitioned algorithm. This means that at each major step of the algorithm a block of rows or columns is updated, and most of the computation is performed by matrix-matrix operations on these blocks. The matrix-matrix operations are performed by calls to the Level 3 BLAS (see Chapter F06), which are the key to achieving high performance on many modern computers. See Golub and Van Loan (1996) or Anderson et al. (1999) for more about block partitioned algorithms.
The performance of a block partitioned algorithm varies to some extent with the block size – that is, the number of rows or columns per block. This is a machine-dependent argument, which is set to a suitable value when the Library is implemented on each range of machines. You do not normally need to be aware of what value is being used. Different block sizes may be used for different routines. Values in the range 16 to 64 are typical.
On some machines there may be no advantage from using a block partitioned algorithm, and then the routines use an unblocked algorithm (effectively a block size of 1), relying solely on calls to the Level 2 BLAS (see Chapter F06 again).
The only situation in which you need some awareness of the block size is when it affects the amount of workspace to be supplied to a particular routine. This is discussed in Section 3.4.3.

2.9 Mixed Precision LAPACK Routines

Some LAPACK routines use mixed precision arithmetic in an effort to solve problems more efficiently on modern hardware. They work by converting a double precision problem into an equivalent single precision problem, solving it and then using iterative refinement in double precision to find a full precision solution to the original problem. The method may fail if the problem is too ill-conditioned to allow the initial single precision solution, in which case the routines fall back to solve the original problem entirely in double precision. The vast majority of problems are not so ill-conditioned, and in those cases the technique can lead to significant gains in speed without loss of accuracy. This is particularly true on machines where double precision arithmetic is significantly slower than single precision.

3 Recommendations on Choice and Use of Available Routines

3.1 Available Routines

Tables 1 to 8 in Section 3.5 show the routines which are provided for performing different computations on different types of matrices. Tables 1 to 4 show routines for real matrices; Tables 5 to 8 show routines for complex matrices. Each entry in the table gives the NAG routine name and the LAPACK double precision name (see Section 3.2).
Routines are provided for the following types of matrix:
For each of the above types of matrix (except where indicated), routines are provided to perform the following computations:
  1. (a)(except for RFP matrices) solve a system of linear equations (driver routines);
  2. (b)(except for RFP matrices) solve a system of linear equations with condition and error estimation (expert drivers);
  3. (c)(except for triangular matrices) factorize the matrix (see Section 2.2);
  4. (d)solve a system of linear equations, using the factorization (see Section 2.3);
  5. (e)(except for RFP matrices) estimate the condition number of the matrix, using the factorization (see Section 2.4.2); these routines also require the norm of the original matrix (except when the matrix is triangular) which may be computed by a routine in Chapter F06;
  6. (f)(except for RFP matrices) refine the solution and compute forward and backward error bounds (see Sections 2.4.4 and 2.4.5); these routines require the original matrix and right-hand side, as well as the factorization returned from (a) and the solution returned from (b);
  7. (g)(except for band and tridiagonal matrices) invert the matrix, using the factorization (see Section 2.5);
  8. (h)(except for tridiagonal, symmetric indefinite, triangular and RFP matrices) compute scale factors to equilibrate the matrix (see Section 2.4.3).
Thus, to solve a particular problem, it is usually only necessary to call a single driver routine, but alternatively two or more routines may be called in succession. This is illustrated in the example programs in the routine documents.

3.2 NAG Names and LAPACK Names

As well as the NAG routine name (beginning F07), Tables 1 to 8 show the LAPACK routine names in double precision.
The routines may be called either by their NAG names or by their LAPACK names. When using the NAG Library, the double precision form of the LAPACK name must be used (beginning with D- or Z-).
References to Chapter F07 routines in the manual normally include the LAPACK double precision names, for example, f07adf.
The LAPACK routine names follow a simple scheme (which is similar to that used for the BLAS in Chapter F06). Most names have the structure XYYZZZ, where the components have the following meanings:
Thus the routine dgetrf performs a triangular factorization of a real general matrix in double precision; the corresponding routine for a complex general matrix is zgetrf.

3.3 Matrix Storage Schemes

In this chapter the following different storage schemes are used for matrices:
These storage schemes are compatible with those used in Chapter F06 (especially in the BLAS) and Chapter F08, but different schemes for packed or band storage are used in a few older routines in Chapters F01, F02, F03 and F04.
In the examples below, * indicates an array element which need not be set and is not referenced by the routines. The examples illustrate only the relevant part of the arrays; array arguments may of course have additional rows or columns, according to the usual rules for passing array arguments in Fortran 77.

3.3.1 Conventional storage

The default scheme for storing matrices is the obvious one: a matrix A is stored in a two-dimensional array a, with matrix element aij stored in array element a(i,j) .
If a matrix is triangular (upper or lower, as specified by the argument uplo), only the elements of the relevant triangle are stored; the remaining elements of the array need not be set. Such elements are indicated by * or in the examples below.
For example, when n=4:
uplo Triangular matrix A Storage in array a
'U' ( a11 a12 a13 a14 a22 a23 a24 a33 a34 a44 ) a11 a12 a13 a14 a22 a23 a24 a33 a34 a44
'L' ( a11 a21 a22 a31 a32 a33 a41 a42 a43 a44 ) a11 a21 a22 a31 a32 a33 a41 a42 a43 a44
Routines which handle symmetric or Hermitian matrices allow for either the upper or lower triangle of the matrix (as specified by uplo) to be stored in the corresponding elements of the array; the remaining elements of the array need not be set.
For example, when n=4:
uplo Hermitian matrix A Storage in array a
'U' ( a11 a12 a13 a14 a¯12 a22 a23 a24 a¯13 a¯23 a33 a34 a¯14 a¯24 a¯34 a44 ) a11 a12 a13 a14 a22 a23 a24 a33 a34 a44
'L' ( a11 a¯21 a¯31 a¯41 a21 a22 a¯32 a¯42 a31 a32 a33 a¯43 a41 a42 a43 a44 ) a11 a21 a22 a31 a32 a33 a41 a42 a43 a44

3.3.2 Packed storage

Symmetric, Hermitian or triangular matrices may be stored more compactly, if the relevant triangle (again as specified by uplo) is packed by columns in a one-dimensional array. In this chapter, as in Chapters F06 and F08, arrays which hold matrices in packed storage, have names ending in P. For a matrix of order n, the array must have at least n(n+1)/2 elements. So:
For example:
uplo Triangle of matrix A Packed storage in array ap
'U' ( a11 a12 a13 a14 a22 a23 a24 a33 a34 a44 ) a11 a12 a22 a13 a23 a33 a14 a24 a34 a44
'L' ( a11 a21 a22 a31 a32 a33 a41 a42 a43 a44 ) a11 a21 a31 a41 a22 a32 a42 a33 a43 a44
Note that for real symmetric matrices, packing the upper triangle by columns is equivalent to packing the lower triangle by rows; packing the lower triangle by columns is equivalent to packing the upper triangle by rows. (For complex Hermitian matrices, the only difference is that the off-diagonal elements are conjugated.)

3.3.3 Rectangular Full Packed (RFP) Storage

The rectangular full packed (RFP) storage format offers the same savings in storage as the packed storage format (described in Section 3.3.2), but is likely to be much more efficient in general since the block structure of the matrix is maintained. This structure can be exploited using block partition algorithms (see Section 2.8) in a similar way to matrices that use conventional storage.
Figure f07intro-rfp
Figure 1
Figure 1 gives a graphical representation of the key idea of RFP for the particular case of a lower triangular matrix of even dimensions. In all cases the original triangular matrix of stored elements is separated into a trapezoidal part and a triangular part. The number of columns in these two parts is equal when the dimension of the matrix is even, n=2k, while the trapezoidal part has k+1 columns when n=2k+1. The smaller part is then transposed and fitted onto the trapezoidal part forming a rectangle. The rectangle has dimensions 2k+1 and q, where q=k when n is even and q=k+1 when n is odd.
For routines using RFP there is the option of storing the rectangle as described above (transr='N') or its transpose (transr='T', for real a) or its conjugate transpose (transr='C', for complex a).
As an example, we first consider RFP for the case n=2k with k=3.
If transr='N', then ar holds a as follows:
If transr='T', then ar in both uplo cases is just the transpose of ar as defined when transr='N'.
uplo Triangle of matrix A Rectangular Full Packed matrix AR
transr='N' transr='T'
'U' ( 00 01 02 03 04 05 11 12 13 14 15 22 23 24 25 33 34 35 44 45 55 ) 03 04 05 13 14 15 23 24 25 33 34 35 00 44 45 01 11 55 02 12 22 03 13 23 33 00 01 02 04 1424 3444 11 12 05 1525 35 4555 22
'L' ( 00 10 11 20 21 22 30 31 32 33 40 41 42 43 44 50 51 52 53 54 55 ) 33 43 53 00 44 54 10 11 55 20 21 22 30 31 32 40 41 42 50 51 52 33 00 10 20 30 40 50 43 44 11 21 31 41 51 53 54 55 22 32 42 52
Now we consider RFP for the case n=2k+1 and k=2.
If transr='N'. ar holds a as follows:
If transr='T'. ar in both uplo cases is just the transpose of ar as defined when transr='N'.
uplo Triangle of matrix A Rectangular Full Packed matrix AR
transr='N' transr='T'
'U' ( 00 01 02 03 04 11 12 13 14 22 23 24 33 34 44 ) 02 03 04 12 13 14 22 23 24 00 33 34 01 11 44 02 12 22 00 01 03 13 23 33 11 04 14 24 34 44
'L' ( 00 10 11 20 21 22 30 31 32 33 40 41 42 43 44 ) 00 33 43 10 11 44 20 21 22 30 31 32 40 41 42 00 10 20 30 40 50 33 11 21 31 41 51 43 44 22 32 42 52
Explicitly, in the real matrix case, ar is a one-dimensional array of length n(n+1)/2 and contains the elements of a as follows:
for uplo='U' and transr='N',
aij is stored in ar( (2k+1) (i-1) + j + k + 1 ) , for 1jk and 1ij, and
aij is stored in ar( (2k+1) (j-k-1) + i ) , for k<jn and 1ij;
for uplo='U' and transr='T',
aij is stored in ar( q (j+k) +i ) , for 1jk and 1ij, and
aij is stored in ar( q (i-1) + j - k ) , for k<jn and 1ij;
for uplo='L' and transr='N',
aij is stored in ar( (2k+1) (j-1) +i +k -q +1 ) , for 1jq and jin, and
aij is stored in ar( (2k+1) (i-k-1) +j-q ) , for q<jn and jin;
for uplo='L' and transr='T',
aij is stored in ar( q (i+k-q) +j ) , for 1jq and 1in, and
aij is stored in ar( q (j-1-q) +i-k ) , for q<jn and 1in.
In the case of complex matrices, the assumption is that the full matrix, if it existed, would be Hermitian. Thus, when transr='N', the triangular portion of a that is, in the real case, transposed into the notional (2k+1)×q RFP matrix is also conjugated. When transr='C' the notional q×(2k+1) RFP matrix is the conjugate transpose of the corresponding transr='N' RFP matrix. Explicitly, for complex a, the array ar contains the elements (or conjugated elements) of a as follows:
for uplo='U' and transr='N',
a¯ij is stored in ar( (2k+1) (i-1) + j + k + 1 ) , for 1jk and 1ij, and
aij is stored in ar( (2k+1) (j-k-1) + i ) , for k<jn and 1ij;
for uplo='U' and transr='C',
aij is stored in ar( q (j+k) +i ) , for 1jk and 1ij, and
a¯ij is stored in ar( q (i-1) + j - k ) , for k<jn and 1ij;
for uplo='L' and transr='N',
aij is stored in ar( (2k+1) (j-1) +i +k -q +1 ) , for 1jq and jin, and
a¯ij is stored in ar( (2k+1) (i-k-1) +j-q ) , for q<jn and jin;
for uplo='L' and transr='C',
a¯ij is stored in ar( q (i+k-q) +j ) , for 1jq and 1in, and
aij is stored in ar( q (j-1-q) +i-k ) , for q<jn and 1in.

3.3.4 Band storage

A band matrix with kl subdiagonals and ku superdiagonals may be stored compactly in a two-dimensional array with kl+ku+1 rows and n columns. Columns of the matrix are stored in corresponding columns of the array, and diagonals of the matrix are stored in rows of the array. This storage scheme should be used in practice only if kl, kun, although the routines in Chapters F07 and F08 work correctly for all values of kl and ku. In Chapters F07 and F08 arrays which hold matrices in band storage have names ending in B.
To be precise, elements of matrix elements aij are stored as follows:
For example, when n=5, kl=2 and ku=1:
Band matrix A Band storage in array ab
( a11 a12 a21 a22 a23 a31 a32 a33 a34 a42 a43 a44 a45 a53 a54 a55 ) * a12 a23 a34 a45 a11 a22 a33 a44 a55 a21 a32 a43 a54 * a31 a42 a53 * *
The elements marked * in the upper left and lower right corners of the array ab need not be set, and are not referenced by the routines.
Note:  when a general band matrix is supplied for LU factorization, space must be allowed to store an additional kl superdiagonals, generated by fill-in as a result of row interchanges. This means that the matrix is stored according to the above scheme, but with kl+ku superdiagonals.
Triangular band matrices are stored in the same format, with either kl=0 if upper triangular, or ku=0 if lower triangular.
For symmetric or Hermitian band matrices with k subdiagonals or superdiagonals, only the upper or lower triangle (as specified by uplo) need be stored:
For example, when n=5 and k=2:
uplo Hermitian band matrix A Band storage in array ab
'U' ( a11 a12 a13 a¯12 a22 a23 a24 a¯13 a¯23 a33 a34 a35 a¯24 a¯34 a44 a45 a¯35 a¯45 a55 ) * * a13 a24 a35 * a12 a23 a34 a45 a11 a22 a33 a44 a55
'L' ( a11 a¯21 a¯31 a21 a22 a¯32 a¯42 a31 a32 a33 a¯43 a¯53 a42 a43 a44 a¯54 a53 a54 a55 ) a11 a22 a33 a44 a55 a21 a32 a43 a54 * a31 a42 a53 * *
Note that different storage schemes for band matrices are used by some routines in Chapters F01, F02, F03 and F04.

3.3.5 Unit triangular matrices

Some routines in this chapter have an option to handle unit triangular matrices (that is, triangular matrices with diagonal elements =1). This option is specified by an argument diag. If diag='U' (Unit triangular), the diagonal elements of the matrix need not be stored, and the corresponding array elements are not referenced by the routines. The storage scheme for the rest of the matrix (whether conventional, packed or band) remains unchanged.

3.3.6 Real diagonal elements of complex matrices

Complex Hermitian matrices have diagonal elements that are by definition purely real. In addition, complex triangular matrices which arise in Cholesky factorization are defined by the algorithm to have real diagonal elements.
If such matrices are supplied as input to routines in Chapters F07 and F08, the imaginary parts of the diagonal elements are not referenced, but are assumed to be zero. If such matrices are returned as output by the routines, the computed imaginary parts are explicitly set to zero.

3.4 Parameter Conventions

3.4.1 Option arguments

Most routines in this chapter have one or more option arguments, of type CHARACTER. The descriptions in Section 5 of the routine documents refer only to upper-case values (for example uplo='U' or 'L'); however, in every case, the corresponding lower-case characters may be supplied (with the same meaning). Any other value is illegal.
A longer character string can be passed as the actual argument, making the calling program more readable, but only the first character is significant. (This is a feature of Fortran 77.) For example:
Call dgetrs('Transpose',...)

3.4.2 Problem dimensions

It is permissible for the problem dimensions (for example, m in f07adf, n or nrhs in f07aef) to be passed as zero, in which case the computation (or part of it) is skipped. Negative dimensions are regarded as an error.

3.4.3 Length of work arrays

A few routines implementing block partitioned algorithms require workspace sufficient to hold one block of rows or columns of the matrix if they are to achieve optimum levels of performance — for example, workspace of size n×nb, where nb is the optimum block size. In such cases, the actual declared length of the work array must be passed as a separate argument lwork, which immediately follows work in the argument-list.
The routine will still perform correctly when less workspace is provided: it uses the largest block size allowed by the amount of workspace supplied, as long as this is likely to give better performance than the unblocked algorithm. On exit, work(1) contains the minimum value of lwork which would allow the routine to use the optimum block size; this value of lwork may be used for subsequent runs.
If lwork indicates that there is insufficient workspace to perform the unblocked algorithm, this is regarded as an illegal value of lwork, and is treated like any other illegal argument value (see Section 3.4.4), though work(1) will still be set as described above.
If you are in doubt how much workspace to supply and are concerned to achieve optimum performance, supply a generous amount (assume a block size of 64, say), and then examine the value of work(1) on exit.

3.4.4 Error-handling and the diagnostic argument INFO

Routines in this chapter do not use the usual NAG Library error-handling mechanism, involving the argument IFAIL. Instead they have a diagnostic argument info. (Thus they preserve complete compatibility with the LAPACK specification.)
Whereas IFAIL is an Input/Output argument and must be set before calling a routine, info is purely an Output argument and need not be set before entry.
info indicates the success or failure of the computation, as follows:
If the routine document specifies that the routine may terminate with info>0, then it is essential to test info on exit from the routine. (This corresponds to a soft failure in terms of the usual NAG error-handling terminology.) No error message is output.
All routines check that input arguments such as n or lda or option arguments of type CHARACTER have permitted values. If an illegal value of the ith argument is detected, info is set to -i, a message is output, and execution of the program is terminated. (This corresponds to a hard failure in the usual NAG terminology.)

3.5 Tables of Driver and Computational Routines

3.5.1 Real matrices

Each entry in the following tables, listing real matrices, gives:
Table 1
Routines for real general matrices
Type of matrix and storage scheme
Operation general general band general tridiagonal
driver f07aaf f07baf f07caf
expert driver f07abf f07bbf f07cbf
mixed precision driver f07acf
factorize f07adf f07bdf f07cdf
solve f07aef f07bef f07cef
scaling factors f07aff f07bff
condition number f07agf f07bgf f07cgf
error estimate f07ahf f07bhf f07chf
invert f07ajf
Table 2
Routines for real symmetric positive definite and positive semidefinite matrices
Type of matrix and storage scheme
Operation symmetric positive definite symmetric positive definite (packed storage) symmetric positive definite (RFP storage) symmetric positive definite band symmetric positive definite tridiagonal symmetric positive semidefinite
driver f07faf f07gaf f07haf f07jaf
expert driver f07fbf f07gbf f07hbf f07jbf
mixed precision f07fcf
factorize f07fdf f07gdf f07wdf f07hdf f07jdf f07kdf
solve f07fef f07gef f07wef f07hef f07jef
scaling factors f07fff f07gff f07hff
condition number f07fgf f07ggf f07hgf f07jgf
error estimate f07fhf f07ghf f07hhf f07jhf
invert f07fjf f07gjf f07wjf
Table 3
Routines for real symmetric indefinite matrices
Type of matrix and storage scheme
Operation symmetric indefinite symmetric indefinite (packed storage)
driver f07maf f07paf
expert driver f07mbf f07pbf
factorize f07mdf f07pdf
solve f07mef f07pef
condition number f07mgf f07pgf
error estimate f07mhf f07phf
invert f07mjf f07pjf
Table 4
Routines for real triangular matrices
Type of matrix and storage scheme
Operation triangular triangular (packed storage) triangular (RFP storage) triangular band
solve f07tef f07uef f07vef
condition number f07tgf f07ugf f07vgf
error estimate f07thf f07uhf f07vhf
invert f07tjf f07ujf f07wkf

3.5.2 Complex matrices

Each entry in the following tables, listing complex matrices, gives:
Table 5
Routines for complex general matrices
Type of matrix and storage scheme
Operation general general band general tridiagonal
driver f07anf f07bnf f07cnf
expert driver f07apf f07bpf f07cpf
mixed precision driver f07aqf
factorize f07arf f07brf f07crf
solve f07asf f07bsf f07csf
scaling factors f07atf f07btf
condition number f07auf f07buf f07cuf
error estimate f07avf f07bvf f07cvf
invert f07awf
Table 6
Routines for complex Hermitian positive definite and positive semidefinite matrices
Type of matrix and storage scheme
Operation Hermitian positive definite Hermitian positive definite (packed storage) Hermitian positive definite (RFP storage) Hermitian positive definite band Hermitian positive definite tridiagonal Hermitian positive semidefinite
driver f07fnf f07gnf f07hnf f07jnf
expert driver f07fpf f07gpf f07hpf f07jpf
mixed precision driver f07fqf
factorize f07frf f07grf f07wrf f07hrf f07jrf f07krf
solve f07fsf f07gsf f07wsf f07hsf f07jsf
scaling factors f07ftf f07gtf
condition number f07fuf f07guf f07huf f07juf
error estimate f07fvf f07gvf f07hvf f07jvf
invert f07fwf f07gwf f07wwf
Table 7
Routines for complex Hermitian and symmetric indefinite matrices
Type of matrix and storage scheme
Operation Hermitian indefinite symmetric indefinite (packed storage) Hermitian indefinite band symmetric indefinite tridiagonal
driver f07mnf f07nnf f07pnf f07qnf
expert driver f07mpf f07npf f07ppf f07qpf
factorize f07mrf f07nrf f07prf f07qrf
solve f07msf f07nsf f07psf f07qsf
condition number f07muf f07nuf f07puf f07quf
error estimate f07mvf f07nvf f07pvf f07qvf
invert f07mwf f07nwf f07pwf f07qwf
Table 8
Routines for complex triangular matrices
Type of matrix and storage scheme
Operation triangular triangular (packed storage) triangular (RFP storage) triangular band
solve f07tsf f07usf f07vsf
condition number f07tuf f07uuf f07vuf
error estimate f07tvf f07uvf f07vvf
invert f07twf f07uwf f07wxf

4 Functionality Index

Apply iterative refinement to the solution and compute error estimates,  
after factorizing the matrix of coefficients,  
complex band matrix   f07bvf
complex Hermitian indefinite matrix   f07mvf
complex Hermitian indefinite matrix, packed storage   f07pvf
complex Hermitian positive definite band matrix   f07hvf
complex Hermitian positive definite matrix   f07fvf
complex Hermitian positive definite matrix, packed storage   f07gvf
complex Hermitian positive definite tridiagonal matrix   f07jvf
complex matrix   f07avf
complex symmetric indefinite matrix   f07nvf
complex symmetric indefinite matrix, packed storage   f07qvf
complex tridiagonal matrix   f07cvf
real band matrix   f07bhf
real matrix   f07ahf
real symmetric indefinite matrix   f07mhf
real symmetric indefinite matrix, packed storage    f07phf
real symmetric positive definite band matrix   f07hhf
real symmetric positive definite matrix   f07fhf
real symmetric positive definite matrix, packed storage   f07ghf
real symmetric positive definite tridiagonal matrix   f07jhf
real tridiagonal matrix   f07chf
Compute error estimates,  
complex triangular band matrix   f07vvf
complex triangular matrix   f07tvf
complex triangular matrix, packed storage   f07uvf
real triangular band matrix   f07vhf
real triangular matrix   f07thf
real triangular matrix, packed storage   f07uhf
Compute row and column scalings,  
complex band matrix   f07btf
complex Hermitian positive definite band matrix   f07htf
complex Hermitian positive definite matrix   f07ftf
complex Hermitian positive definite matrix, packed storage   f07gtf
complex matrix   f07atf
real band matrix   f07bff
real matrix   f07aff
real symmetric positive definite band matrix   f07hff
real symmetric positive definite matrix   f07fff
real symmetric positive definite matrix, packed storage   f07gff
Condition number estimation,  
after factorizing the matrix of coefficients,  
complex band matrix   f07buf
complex Hermitian indefinite matrix   f07muf
complex Hermitian indefinite matrix, packed storage   f07puf
complex Hermitian positive definite band matrix   f07huf
complex Hermitian positive definite matrix   f07fuf
complex Hermitian positive definite matrix, packed storage   f07guf
complex Hermitian positive definite tridiagonal matrix   f07juf
complex matrix   f07auf
complex symmetric indefinite matrix   f07nuf
complex symmetric indefinite matrix, packed storage   f07quf
complex tridiagonal matrix   f07cuf
real band matrix   f07bgf
real matrix   f07agf
real symmetric indefinite matrix   f07mgf
real symmetric indefinite matrix, packed storage   f07pgf
real symmetric positive definite band matrix   f07hgf
real symmetric positive definite matrix   f07fgf
real symmetric positive definite matrix, packed storage   f07ggf
real symmetric positive definite tridiagonal matrix   f07jgf
real tridiagonal matrix   f07cgf
complex triangular band matrix   f07vuf
complex triangular matrix   f07tuf
complex triangular matrix, packed storage   f07uuf
real triangular band matrix   f07vgf
real triangular matrix   f07tgf
real triangular matrix, packed storage   f07ugf
LDLT factorization,  
complex Hermitian positive definite tridiagonal matrix   f07jrf
real symmetric positive definite tridiagonal matrix   f07jdf
LLT or UTU factorization,  
complex Hermitian positive definite band matrix   f07hrf
complex Hermitian positive definite matrix   f07frf
complex Hermitian positive definite matrix, packed storage   f07grf
complex Hermitian positive definite matrix, RFP storage   f07wrf
complex Hermitian positive semidefinite matrix   f07krf
real symmetric positive definite band matrix   f07hdf
real symmetric positive definite matrix   f07fdf
real symmetric positive definite matrix, packed storage   f07gdf
real symmetric positive definite matrix, RFP storage   f07wdf
real symmetric positive semidefinite matrix   f07kdf
LU factorization,  
complex band matrix   f07brf
complex matrix   f07arf
complex tridiagonal matrix   f07crf
real band matrix   f07bdf
real matrix   f07adf
real tridiagonal matrix   f07cdf
Matrix inversion,  
after factorizing the matrix of coefficients,  
complex Hermitian indefinite matrix   f07mwf
complex Hermitian indefinite matrix, packed storage   f07pwf
complex Hermitian positive definite matrix   f07fwf
complex Hermitian positive definite matrix, packed storage   f07gwf
complex Hermitian positive definite matrix, RFP storage   f07wwf
complex matrix   f07awf
complex symmetric indefinite matrix   f07nwf
complex symmetric indefinite matrix, packed storage   f07qwf
real matrix   f07ajf
real symmetric indefinite matrix   f07mjf
real symmetric indefinite matrix, packed storage   f07pjf
real symmetric positive definite matrix   f07fjf
real symmetric positive definite matrix, packed storage   f07gjf
real symmetric positive definite matrix, RFP storage   f07wjf
complex triangular matrix   f07twf
complex triangular matrix, packed storage   f07uwf
complex triangular matrix, RFP storage,  
expert driver   f07wxf
real triangular matrix   f07tjf
real triangular matrix, packed storage   f07ujf
real triangular matrix, RFP storage,  
expert driver   f07wkf
PLDLTPT or PUDUTPT factorization,  
complex Hermitian indefinite matrix   f07mrf
complex Hermitian indefinite matrix, packed storage   f07prf
complex symmetric indefinite matrix   f07nrf
complex symmetric indefinite matrix, packed storage   f07qrf
real symmetric indefinite matrix   f07mdf
real symmetric indefinite matrix, packed storage   f07pdf
Solution of simultaneous linear equations,  
after factorizing the matrix of coefficients,  
complex band matrix   f07bsf
complex Hermitian indefinite matrix   f07msf
complex Hermitian indefinite matrix, packed storage   f07psf
complex Hermitian positive definite band matrix   f07hsf
complex Hermitian positive definite matrix   f07fsf
complex Hermitian positive definite matrix, packed storage   f07gsf
complex Hermitian positive definite matrix, RFP storage   f07wsf
complex Hermitian positive definite tridiagonal  matrix   f07jsf
complex matrix   f07asf
complex symmetric indefinite matrix   f07nsf
complex symmetric indefinite matrix, packed storage   f07qsf
complex tridiagonal matrix   f07csf
real band matrix   f07bef
real matrix   f07aef
real symmetric indefinite matrix   f07mef
real symmetric indefinite matrix, packed storage   f07pef
real symmetric positive definite band matrix   f07hef
real symmetric positive definite matrix   f07fef
real symmetric positive definite matrix, packed storage   f07gef
real symmetric positive definite matrix, RFP storage   f07wef
real symmetric positive definite tridiagonal matrix   f07jef
real tridiagonal matrix   f07cef
expert drivers (with condition and error estimation):  
complex band matrix   f07bpf
complex Hermitian indefinite matrix   f07mpf
complex Hermitian indefinite matrix, packed storage   f07ppf
complex Hermitian positive definite band matrix   f07hpf
complex Hermitian positive definite matrix   f07fpf
complex Hermitian positive definite matrix, packed storage   f07gpf
complex Hermitian positive definite tridiagonal matrix   f07jpf
complex matrix   f07apf
complex symmetric indefinite matrix   f07npf
complex symmetric indefinite matrix, packed storage   f07qpf
complex tridiagonal matrix   f07cpf
real band matrix   f07bbf
real matrix   f07abf
real symmetric indefinite matrix   f07mbf
real symmetric indefinite matrix, packed storage   f07pbf
real symmetric positive definite band matrix   f07hbf
real symmetric positive definite matrix   f07fbf
real symmetric positive definite matrix, packed storage   f07gbf
real symmetric positive definite tridiagonal matrix   f07jbf
real tridiagonal matrix   f07cbf
simple drivers,  
complex band matrix   f07bnf
complex Hermitian indefinite matrix   f07mnf
complex Hermitian indefinite matrix, packed storage   f07pnf
complex Hermitian positive definite band matrix   f07hnf
complex Hermitian positive definite matrix   f07fnf
complex Hermitian positive definite matrix, packed storage   f07gnf
complex Hermitian positive definite matrix, using mixed precision   f07fqf
complex Hermitian positive definite tridiagonal matrix   f07jnf
complex matrix   f07anf
complex matrix, using mixed precision   f07aqf
complex symmetric indefinite matrix   f07nnf
complex symmetric indefinite matrix, packed storage   f07qnf
complex triangular band matrix   f07vsf
complex triangular matrix   f07tsf
complex triangular matrix, packed storage   f07usf
complex tridiagonal matrix   f07cnf
real band matrix   f07baf
real matrix   f07aaf
real matrix, using mixed precision   f07acf
real symmetric indefinite matrix   f07maf
real symmetric indefinite matrix, packed storage   f07paf
real symmetric positive definite band matrix   f07haf
real symmetric positive definite matrix   f07faf
real symmetric positive definite matrix, packed storage   f07gaf
real symmetric positive definite matrix, using mixed precision   f07fcf
real symmetric positive definite tridiagonal matrix   f07jaf
real triangular band matrix    f07vef
real triangular matrix   f07tef
real triangular matrix, packed storage   f07uef
real tridiagonal matrix   f07caf

5 Auxiliary Routines Associated with Library Routine Arguments

None.

6 Withdrawn or Deprecated Routines

None.

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
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Higham N J (1988) Algorithm 674: Fortran codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation ACM Trans. Math. Software 14 381–396
Wilkinson J H (1965) The Algebraic Eigenvalue Problem Oxford University Press, Oxford