Page 60 - Compact Numerical Methods For Computers

Chapter 4

HANDLING LARGER PROBLEMS

4.1. INTRODUCTION
The previous chapter used plane rotations multiplying a matrix from the right to
orthogonalise its columns. By the essential symmetry of the singular-value decom-
position, there is nothing to stop us multiplying a matrix by plane rotations from
the left to achieve an orthogonalisation of its rows. The amount of work involved
2 2
is of order m n operations per sweep compared to mn for the columnwise
orthogonalisation (A is m by n), and as there are normally more rows than
columns it may seem unprofitable to do this. However, by a judicious combination
of row orthogonalisation with Givens’ reduction, an algorithm can be devised
which will handle a theoretically unlimited number of rows.

4.2. THE GIVENS’ REDUCTION
The above approach to the computation of a singular-value decomposition and
least-squares solution works very well on a small computer for relatively small
matrices. For instance, it can handle least-squares regression calculations invol-
ving up to 15 economic time series with 25 years of data in less than 2000 words of
main memory (where one matrix element occupies two words of storage). While
such problems are fairly common in economics, biological and sociological
phenomena are likely to have associated with them very large numbers of
observations, m, even though the number of variables, n, may not be large. Again,
T
the formation of the sum-of-squares and cross-products matrix A A and solution
via the normal equations (2.22) should be avoided. In order to circumvent the
difficulties associated with the storage of the whole of the matrix A, the Givens’
reduction can be used. A Givens’ transformation is simply a plane rotation which
transforms two vectors so that an element of one of them becomes zero. Consider
T T
two row vectors z and y and a pre-multiplying rotation:

(4.1)
where
c = cos f s = sin f (4.2)

and f is the angle of rotation. If Y is to be zero, then
1
–sz + cy = 0
1 1 (4.3)
so that the angle of rotation in this case is given by
tan f = s/c = y /z . (4.4)
1
l
49