Transformations

Back to: Main contents.

Contents

Householder Transformations (The House suite)
Pivoting (the Pivot suite)
Plane rotations (the Rot suite)
Swapping Rows and Columns (the Swap suite)
Decompositions are computed by transforming the elements of a matrix. Since it is impossible for Jampack to cover all possible decompositions, the packages has suites implementing the more commonly used transformations.

Householder Transformations (The House suite)

Back to: Main contents, Top of section.

A Householder transformation is a unitary matrix of the form

U = I - uuH,
where uHu = 2. The vector u is said to generate the Householder transformation u.

For any vector x there is a generating vector u such that

Ux = se1,
where s is a scalar and e1 is the vector whose first component is one and whose other components are zero. Thus the Householder transformation U introduces zeros into the last components of x.

If the vector x is embedded in a matrix A, then the Householder transformation will introduce zeros into A. Specifically, if A has the form 

|a a a a a a a|
|a x a a a a a|
|a x a a a a a|
|a x a a a a a|
|a x a a a a a|
|a a a a a a a|
and we embed the matrix U above in an identity matrix 
|1 0 0 0 0 0|
|0 u u u u 0|
|0 u u u u 0|
|0 u u u u 0|
|0 u u u u 0|
|0 0 0 0 0 1|
then the product of the two has the form 
|1 0 0 0 0 0| |a a a a a a a|   |a a a a a a a|
|0 u u u u 0| |a x a a a a a|   |a s a a a a a|
|0 u u u u 0| |a x a a a a a| = |a 0 a a a a a|
|0 u u u u 0| |a x a a a a a|   |a 0 a a a a a|
|0 u u u u 0| |a x a a a a a|   |a 0 a a a a a|
|0 0 0 0 0 1| |a a a a a a a|   |a a a a a a a|

Similarly a postmultiplication by a Householder transformation can introduce zeros into the rows of A.

The House suite contains method to generate and apply Householder transformations. There are two methods to generate a Householder transformation. The first,

public static Z1 genc(Zmat A, int r1, int r2, int c)
generates a Householder transformation that on premultiplication introduces zeros into a column of A. Its calling sequence and effect are illustrated by the following diagram. 
      c
      |
   |a a a a a a a|     |a a a a a a|
r1-|a x a a a a a|     |a s a a a a|
   |a x a a a a a|     |a 0 a a a a|
   |a x a a a a a| --> |a 0 a a a a|
r2-|a x a a a a a|     |a 0 a a a a|
   |a a a a a a a|     |a a a a a a|
Here r1, r2, and c specify the part of the matrix from which the Householder transformation is generated. The elements denoted by x's are overwritten by the results of the transformation, but the matrix A is otherwise unaltered. The generating vector is returned as a Z1 of length r2-r1+1.

The method

public static Z1 genr(Zmat A, int r, int c1, int c2)
generates a Householder transformation that on postmultiplication introduces zeros into a row of A. Its calling sequence and effect are illustrated by the following diagram. 
     c1    c2  
     |     |
  |a a a a a a|     |a a a a a a|
r-|a x x x x a|     |a s 0 0 0 a|
  |a a a a a a|     |a a a a a a|
  |a a a a a a| --> |a a a a a a|
  |a a a a a a|     |a a a a a a|
  |a a a a a a|     |a a a a a a|
Here r, c2, and c2 specify the part of the matrix from which the Householder transformation is generated. The elements denoted by x's are overwritten by the results of the transformation, but the matrix A is otherwise unaltered. The generating vector is returned as a Z1 of length c2-c1+1.

A Householder transformation can premultiply or postmultiply a matrix. Either operation requires a Z1 work array. Consequently, the methods for applying Householder transformations come in two varieties: one in which the user furnishes the array and the other in which it is generated by the by the method.

The methods

public static Zmat ua(Z1 u, Zmat A, int r1, int r2, int c1, int c2, Z1 v)

public static Zmat ua(Z1 u, Zmat A, int r1, int r2, int c1, int c2)

premultiply the Householder transformation generate by u into the submatrix of A marked by x's below. 
        c1  c2
        |   |
   |a a a a a a|
r1-|a a x x x a|
   |a a x x x a|
   |a a x x x a|
r2-|a a x x x a|
   |a a a a a a|
If r1>r2 or c1>c2, the methods do nothing, which is useful in handling boundary conditions. The Z1 v must be at least r2-r1+1 in length. The methods throw a JampackException if u or v are too short.

The methods

public static Zmat au(Z1 u, Zmat A, int r1, int r2, int c1, int c2, Z1 v)

public static Zmat au(Z1 u, Zmat A, int r1, int r2, int c1, int c2)

postmultiply the Householder transformation generate by u into the submatrix of A illustrated above. If r1>r2 or c1>c2, the methods do nothing. The Z1 v must be at least c2-c1+1 in length. The methods throw a JampackException if u or v are too short.

Pivoting (the Pivot suite)

Back to: Main contents, Top of section.

The Pivot suite contains methods to perform a sequence of interchanges to a matrix. The pivot sequence is specified by an integer array pvt[], which determines a permutation as follows. Here bx is the base index of the matrix in question. 

for (k=0; k<pvt.length; k++)
   swap row k+bx and row pvt[k]+bx;

The method for applying pvt to the rows of a is

public static Zmat row(Zmat A, int pvt[])

The suite also contains a method for performing the inverse pivot sequence 

for(k=pvt.length-1; k>=0; k--)
   swap row k+bx and row pvt[k]+bx;
to the rows of A.
public static Zmat rowi(Zmat A, int pvt[])
Routines for column pivoting will be added later.

Plane rotations (the Rot suite)

Back to: Main contents, Top of section.

The Rot suite generates and applies plane rotations. A 2x2 plane rotation is a unitary matrix of the form 

P = |   c      s|
    |-conj(s)  c|
where c is real and |c|2+|s|2 = 1. The number c is the cosine of the rotation and the number s is the sine.

Given a 2-vector whose components are x and y, there is plane rotation P such that 

P|x| =  |   c      s||x| = |z|
 |y|    |-conj(s)  c||y|   |0|

Plane rotations may be premultiplied into a matrix A to combine two rows of A. For example, let x, y, c, s, and z be as above, and let 

    |1    0     0 0 0|
    |0    c     0 s 0|
P = |0    0     1 0 0|
    |0 -conj(s) 0 c 0|
    |0    0     0 0 0|
Then if 
    |a a a a a|
    |a x a a a|
A = |a a a a a|
    |a y a a a|
    |a a a a a|
the matrix PA has the form 
    |a a a a a|
    |b z b b b|
B = |a a a a a|
    |b 0 b b b|
    |a a a a a|
The elements denoted by "a" are unchanged by the transformation. Thus a plane rotation can be used to introduce a zero into a matrix at the cost of altering two rows of the matrix.

Similarly there is a plane rotation such that 

|x y||   c      s||x| = |z 0|
     |-conj(s)  c||y|
If P has the form above and A is of the form 
    |a a a a a|
    |a x a y a|
A = |a a a a a|
    |a a a a a|
    |a a a a a|
then B = AP has the form 
    |a b a b a|
    |a z a 0 a|
B = |a b a b a|
    |a b a b a|
    |a b a b a|
Thus postmultiplication by a plane rotation can also be used to introduce zeros into a matrix.

The Rot suite consists of data fields defining a plane rotation and static functions to generate and apply the rotations. The defining fields are

public double c
The cosine of the rotation

public double sr
The real part of the sine of the rotation

public double si
The imaginary part of the sine of the rotation

public double zr
The real part of the first component of the transformed vector

public double si
The imaginary part of the first component of the transformed vector

The methods that generate rotations satisfying 

|   c      s||x| = |z|
|-conj(s)  c||y|   |0|
are called genc (c for column). They come in two varieties. One returns the required Rot. The other initializes a Rot in the calling sequence. This second variety is necessary to prevent certain rotation-intensive computations from being dominated by the generation of new Rots.

public static Rot genc(double xr, double xi, double yr, double yi)
public static void genc(double xr, double xi, double yr, double y, Rot P)
Generates a rotation from the complex numbers x = xr+i*xi and y = yr+i*yi.

public static Rot genc(double x, double y)
public static void genc(, double x, double y, Rot P)
Generates a real rotation from x and y.

public static Rot genc(Zmat A, int i1, int i2, int j)
public static void genc(Zmat A, int i1, int i2, intj, Rot P)
Generates a rotation from the elements x=ai1,j and y=ai2,j. The element ai1,j is overwritten by z and ai2,j is overwritten by zero.
The methods that generate rotations satisfying 
|x y||   c      s||x| = |z 0|
     |-conj(s)  c||y|
are called genr. They also come in pairs.

public static Rot genr(double xr, double xi, double yr, double yi)
public static void genr(double xr, double xi, double yr, double yi, Rot P)
Generates a rotation from the numbers x = xr+i*xi and y = yr+i*xi.

public static Rot genr(double x, double y)
public static void genr(double x, double y, Rot P)
Generates a real rotation from x and y.

public static Rot genr(Zmat A, int i, int j1, int j2)
public static void genr(Zmat A, int i, int j1, int j2, Rot P)
Generates a rotation from the elements x=ai,j1 and y=ai,j2. The element ai,j1 is overwritten by z and ai,j2 is overwritten by zero.
There are four methods to apply a rotation to a matrix.

public static void pa(Rot P, Zmat A, int i1, int i2, int j1, int j2)
Multiplies rows (i1,j1:j2) and (i2,j1:j2) of A by P.

public static void pha(Rot P, Zmat A, int i1, int i2, int j1, int j2)
Multiplies rows (i1,j1:j2) and (i2,j1:j2) of A by PH.

public static void ap(Zmat A, Rot P, int i1, int i2, int j1, int j2)
Multiplies columns (i1:i2,j1) and A(i2:i2,j1) of A by P.

public static void aph(Zmat A, Rot P, int i1, int i2, int j1, int j2)
Multiplies columns (i1:i2,j1) and A(i2:i2,j1) of A by PH.

Swapping Rows and Columns (the Swap suite)

Back to: Main contents, Top of section.

The Swap suite has two routines for swapping rows or columns of a matrix.

public static void rows(Zmat A, int r1, int r2)
Interchanges rows r1 and r2 of A.
Throws JampackException if r1 or r2 is out of range.

public static void cols(Zmat A, int c1, int c2)
Interchanges columns c1 and c2 of A.
Throws JampackException of c1 or c2 is out of range.