Page 102 - Compact Numerical Methods For Computers

The Choleski decomposition 91
finding seemed to be reversed, probably because these latter machines are run as
interpreters, that is, they evaluate the code as they encounter it in a form of
simultaneous translation into machine instructions whereas a compiler makes the
translation first then discards the source code. The Healy and Price routines most
likely are slowed down by the manner in which their looping is organised,
requiring a backward jump in the program. On a system which interprets, this is
likely to require a scan of the program until the appropriate label is found in the
code and it is my opinion that this is the reason for the more rapid execution of
algorithm 7 in interpreter environments. Such examples as these serve as a
warning that programs do show very large changes in their relative, as well as
absolute, performance depending on the hardware and software environment in
which they are run.
Algorithm 7 computes the triangular factor L column by column. Row-by-row
development is also possible, as are a variety of sequential schemes which perform
the central subtraction in STEP 4 in piecemeal fashion. If double-precision arith-
metic is possible, the forms of the Choleski decomposition which compute the
right-hand side of (7.8) via a single accumulation as in algorithm 7 have the
advantage of incurring a much smaller rounding error.

Example 7.1. The Choleski decomposition of the Moler matrix
The Moler matrix, given by

A = min(i, j) – 2 for i j
ij
A = i
ii

has the decomposition
A = LL T

where
0 for j > i

L ij = 1 for i = j
-1 for j < i.

Note that this is easily verified since

for i j
for i = j.
On a Data General NOVA operating in arithmetic having six hexadecimal digits
-5
(that is, a machine precision of 16 ) the correct decomposition was observed for
Moler matrices of order 5, 10, 15, 20 and 40. Thus for order 5, the Moler matrix