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 (Declaration)
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= rii rij rji rjj ,

(1)

then, in the real case, it is usual to choose Rij so that

R= -c s -s c , c=cos⁡θ, s=sin⁡θ.

An exception is method (f06fp not in this release) which applies the so-called symmetric rotation for which

R= c -s s -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,

-c s -s c a b = d 0 .

(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 (f06aa 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, d≠0, 1, d=0, s= b/d, d≠0, 0, d=0,

(4)

where σ= sign⁡a, a>b sign⁡b, a≤b .

The value z defined as

z= s, s<c or c=0 1/c, 0<c≤s

(5)

is also computed and this enables c and s to be reconstructed from the single value z as

c= 0, z=1 1-z21/2, z<1 1/z, z>1 s= 1, z=1 z, z<1 1-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=0 b/a, b≤a.flmax,b≠0 signb/a.flmax, b>a.flmax signb.flmax, b≠0,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, eps≤t≤1/eps 1, t<eps 1/t, t>1/eps s= c.t, eps≤t≤1/eps t, t<eps sign⁡t, 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

-c s -s c x y y z c -s s -c = a 0 0 b .

(8)

In such an application the matrix R is often termed a Jacobi rotation matrix. The method that generates a Jacobi rotation ( (f06be 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- -s c , 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

-c s- -s c a b = d 0

(10)

is such that if a is real then d is also real.

When s is real then the transformation

-c- s -s c a b = d 0

(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

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