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).

Syntax

C#
public static class F06
Visual Basic
Public NotInheritable Class F06
Visual C++
public ref class F06 abstract sealed
F#
[<AbstractClassAttribute>]
[<SealedAttribute>]
type F06 =  class end

Background to the Problems

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 On2 operations for an n×n matrix.

The Use of BLAS Names

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)).

Background Information

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.

Real plane rotations

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 i,j plane, Rij, is an orthogonal matrix that is different from the unit matrix only in the elements rii, rjj, rij and rji. If we put
R=riirijrjirjj, (1)
then, in the real case, it is usual to choose Rij so that
R=-cs-sc,  c=cosθ,  s=sinθ.
An exception is method (F06FPF not in this release) which applies the so-called symmetric rotation for which
R=c-ss-c. (2)
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 c and s so that for given a and b,
-cs-scab=d0. (3)
In such an application the matrix R 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 c, s and d as
d=σa2+b21/2,
c=a/d,d0,1,d=0,   s=b/d,d0,0,d=0, (4)
where σ=signa,a>bsignb,ab.
The value z defined as
z=s,s<c  or  c=01/c,0<cs (5)
is also computed and this enables c and s to be reconstructed from the single value z as
c=0,z=11-z21/2,z<11/z,z>1   s=1,z=1z,z<11-c21/2,z>1.
The other F06 class methods for constructing Givens rotations are based on the computation of the tangent, t=tanθ. t is computed as
t=0,b=0b/a,ba.flmax,b0signb/a.flmax,b>a.flmaxsignb.flmax,b0,a=0 (6)
where flmax=1/flmin and flmin is the small positive value returned by x02am. The values of c and s are then computed or reconstructed via t as
c=1/1+t21/2,epst1/eps1,t<eps1/t,t>1/eps   s=c.t,epst1/epst,t<epssignt,t>1/eps (7)
where eps is the machine precision. Note that c is always non-negative in this scheme and that the same expressions are used in the initial computation of c and s from a and b as in any subsequent recovery of c and s via t. This is the approach used by many of the NAG Library methods that require plane rotations. d is computed simply as
d=c.a+s.b.
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 c and s so that for given x, y and z 
-cs-scxyyzc-ss-c=a00b. (8)
In such an application the matrix R is often termed a Jacobi rotation matrix. The method that generates a Jacobi rotation ( (F06BEF not in this release)) first computes the tangent t and then computes c and s via t as described above for the Givens rotation.

Complex plane rotations

In the complex case a plane rotation matrix for the i,j plane, Rij is a unitary matrix and, analogously to the real case, it is usual to choose Rij so that
R=-c-s--sc,  c2+s2=1, (9)
where a- denotes the complex conjugate of a.
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 c and s via t=b/a in an analogous manner to the real case. R can be chosen to have either c real, or s real and there are methods for both cases.
When c is real then it is non-negative and the transformation
-cs--scab=d0 (10)
is such that if a is real then d is also real.
When s is real then the transformation
-c-s-scab=d0 (11)
is such that if b is real then d is also real.

Elementary real (Householder) reflections

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, P, is a matrix of the form
P=I-μuuT,  μuTu=2, (12)
where μ is a scalar and u is a vector, and P is both symmetric and orthogonal. In the methods in F06 class, u is expressed in the form
u=ζz,  ζ​ a scalar (13)
because in many applications ζ and z are not contiguous elements. The usual use of elementary reflectors is to choose μ and u so that for given α and x 
Pαx=β0,  α​ and ​β​ scalars. (14)
Such a transformation is often termed a Householder transformation. There are two choices of μ and u 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
μ=1/ζ. (15)
This choice makes ζ satisfy
1ζ2.
The second form, and the form used by many of the NAG Library methods, has
μ=1 (16)
which makes
1ζ2.
In both cases the special setting
ζ=0 (17)
is used by the methods to flag the case where P=I.
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 PA for a given matrix
PA=I-μuuTA=A-μuuTA=A-μubT,  b=ATu, (18)
and so we can call a matrix-vector product method to form b=ATu and then call a rank-one update method to form A-μubT. Of course, we must skip the transformation when ζ has been set to zero.

Elementary complex (Householder) reflections

A complex elementary reflector, P, is a matrix of the form
P=I-μuuH,  μuHu=2,  μ​ real,
where uH denotes the complex conjugate of uT, and P 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
P=I-μuuH,  μ2uHu=μ+μ- (19)
for which P is still unitary, but is no longer Hermitian.
The F06 class methods choose μ and ζ so that
Reμ=1,  Imζ=0 (20)
and this reduces to (12) with the choice (16) when μ and u are real. This choice is used because μ and u can now be chosen so that in the Householder transformation (14) we can make
Imβ=0
and, as in the real case,
1ζ2.
Rather than returning μ and ζ as separate parameters the F06 class methods return the single complex value θ defined as
θ=ζ+i.Imμ,  i=-1.
Obviously ζ and μ can be recovered as
ζ=Reθ,  μ=1+i.Imθ.
The special setting
θ=0
is used to flag the case where P=I, and
Reθ0,  Imθ0
is used to flag the case where
P=γ00I,  γ​ a scalar (21)
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 PH.

References

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

Inheritance Hierarchy

System..::..Object
  NagLibrary..::..F06

See Also