This chapter is concerned with basic linear algebra methods which perform elementary algebraic operations involving scalars, vectors and matrices. It includes methods which conform to the specifications of the BLAS (Basic Linear Algebra Subprograms).
A number of the methods in this chapter meet the specification of the Basic Linear Algebra Subprograms (BLAS) as described in Lawson et al. (1979), Dodson et al. (1991), Dongarra et al. (1988) and Dongarra et al. (1990). The first reference describes a set of methods concerned with operations on scalars and vectors: these will be referred to here as the Level-0 and the Level-1 BLAS; the second reference describes a set of methods concerned with operations on sparse vectors: these will be referred to here as the Level-1 Sparse BLAS; the third reference describes a set of methods concerned with matrix-vector operations: these will be referred to here as the Level-2 BLAS; and the fourth reference describes a set of methods concerned with matrix-matrix operations: these will be referred to here as the Level-3 BLAS.
More generally we refer to the scalar methods in the chapter as Level-0 methods, to the vector methods as Level-1 methods, to the matrix-vector and matrix methods as Level-2 methods, and to the matrix-matrix methods as Level-3 methods. The terminology reflects the number of operations involved. For example, a Level-2 method involves operations for an matrix.
Many of the methods in other chapters of the Library call the methods in this chapter, and in particular a number of the BLAS are called. These methods are usually called by the BLAS name and so, for correct operation of the Library, it is essential that you do not attempt to link your own versions of these methods. If you are in any doubt about how to avoid this, please consult your computer centre or the NAG Response Centre.
The BLAS names are used in order to make use of efficient implementations of the methods when these exist. Such implementations are stringently tested before being used, to ensure that they correctly meet the specification of the BLAS, and that they return the desired accuracy (see, for example, Dodson et al. (1991), Dongarra et al. (1988) and Dongarra et al. (1990)).
Most of the methods in this chapter implement straightforward scalar, vector and matrix operations that need no further explanation beyond a statement of the purpose of the method. In this section we give some additional background information to those few cases where additional explanation may be necessary. A sub-section is devoted to each topic.
There are a number of methods in the chapter concerned with setting up and applying plane rotations. This section discusses the real case and the next section looks at the complex case. For further background information see Golub and Van Loan (1996).
A plane rotation matrix for the plane, , is an orthogonal matrix that is different from the unit matrix only in the elements , , and . If we put
then, in the real case, it is usual to choose so that
An exception is method (F06FPF not in this release) which applies the so-called symmetric rotation for which
The application of plane rotations is straightforward and needs no further elaboration, so further comment is made only on the construction of plane rotations.
The most common use of plane rotations is to choose and so that for given and ,
In such an application the matrix is often termed a Givens rotation matrix. There are two approaches to the construction of real Givens rotations in F06 class.
The BLAS method (F06AAF not in this release), see Lawson et al. (1979) and Dodson and Grimes (1982), computes , and as
The value defined as
is also computed and this enables and to be reconstructed from the single value as
The other F06 class methods for constructing Givens rotations are based on the computation of the tangent, . is computed as
where and is the small positive value returned by x02am. The values of and are then computed or reconstructed via as
where is the machine precision. Note that is always non-negative in this scheme and that the same expressions are used in the initial computation of and from and as in any subsequent recovery of and via . This is the approach used by many of the NAG Library methods that require plane rotations. is computed simply as
You need not be too concerned with the above detail, since methods are provided for setting up, recovering and applying such rotations.
Another use of plane rotations is to choose and so that for given , and
In such an application the matrix is often termed a Jacobi rotation matrix. The method that generates a Jacobi rotation ( (F06BEF not in this release)) first computes the tangent and then computes and via as described above for the Givens rotation.
In the complex case a plane rotation matrix for the plane, is a unitary matrix and, analogously to the real case, it is usual to choose so that
where denotes the complex conjugate of .
The BLAS (see Lawson et al. (1979)) do not contain a method for the generation of complex rotations, and so the methods in F06 class are all based upon computing and via in an analogous manner to the real case. can be chosen to have either real, or real and there are methods for both cases.
When is real then it is non-negative and the transformation
is such that if is real then is also real.
When is real then the transformation
is such that if is real then is also real.
There are a number of methods in the chapter concerned with setting up and applying Householder transformations. This section discusses the real case and the next section looks at the complex case. For further background information see Golub and Van Loan (1996).
A real elementary reflector, , is a matrix of the form
where is a scalar and is a vector, and is both symmetric and orthogonal. In the methods in F06 class, is expressed in the form
because in many applications and are not contiguous elements. The usual use of elementary reflectors is to choose and so that for given and
Such a transformation is often termed a Householder transformation. There are two choices of and available in F06 class.
The first form of the Householder transformation is compatible with that used by LINPACK (see Dongarra et al. (1979)) and has
This choice makes satisfy
The second form, and the form used by many of the NAG Library methods, has
In both cases the special setting
is used by the methods to flag the case where .
Note that while there are methods to apply an elementary reflector to a vector, there are no methods available in F06 class to apply an elementary reflector to a matrix. This is because such transformations can readily and efficiently be achieved by calls to the matrix-vector Level 2 BLAS methods. For example, to form for a given matrix
and so we can call a matrix-vector product method to form and then call a rank-one update method to form . Of course, we must skip the transformation when has been set to zero.
A complex elementary reflector, , is a matrix of the form
where denotes the complex conjugate of , and is both Hermitian and unitary. For convenience in a number of applications this definition can be generalized slightly by allowing to be complex and so defining the generalized elementary reflector as
for which is still unitary, but is no longer Hermitian.
The F06 class methods choose and so that
and this reduces to (12) with the choice (16) when and are real. This choice is used because and can now be chosen so that in the Householder transformation (14) we can make
and, as in the real case,
Rather than returning and as separate parameters the F06 class methods return the single complex value defined as
Obviously and can be recovered as
The special setting
is used to flag the case where , and
is used to flag the case where
and in this case actually contains the value of . Notice that with both (18) and (21) we merely have to supply rather than in order to represent .
Dodson D S and Grimes R G (1982) Remark on Algorithm 539 ACM Trans. Math. Software 8 403–404
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
Dongarra J J, Moler C B, Bunch J R and Stewart G W (1979) LINPACK Users' Guide SIAM, Philadelphia
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