Page 24 - Compact Numerical Methods For Computers

14 Compact numerical methods for computers
because their day-to-day problems vary a great deal. I have deliberately avoided
including a great many algorithms in this volume because most users will likely be
their own implementors and not have a great deal of time to spend choosing,
coding, testing and, most of all, maintaining programs.
Another choice which has been made is that of only including algorithms which
are relatively ‘small’ in the sense that they fit into the machine all at once. For
instance, in the solution of the algebraic eigenvalue problem on large computers,
conventionally one reduces the matrix to a special form such as a tridiagonal or a
Hessenberg matrix, solves the eigenproblem of the simpler system then back-
transforms the solutions. Each of the three phases of this procedure could be
fitted into a small machine. Again, for the practitioner with a lot of matrices to
solve or a special requirement for only partial solution, such methods should be
employed. For the one-at-a-time users, however, there is three times as much
program code to worry about.
The lack of double-precision arithmetic on the machines I used to develop the
algorithms which are included has no doubt modified my opinions concerning
algorithms. Certainly, any algorithm requiring inner products of vectors, that is

(1.10)

cannot be executed as accurately without extended-precision arithmetic (Wilkin-
son 1963). This has led to my abandonment of algorithms which seek to find the
minimum of a function along a line by use of gradient information. Such
algorithms require the derivative along the line and employ an inner product to
compute this derivative. While these methods are distinctly unreliable on a
machine having only a single, low-precision arithmetic, they can no doubt be used
very effectively on other machines.
From the above discussion it will be evident that the principles guiding
algorithm selection have been:
(i) shortness of program which results from implementation and low storage
requirement, and
(ii) general utility of the method and importance of the problem which it solves.
To these points should be added:
(iii) proven reliability in a number of tests
(iv) the ease and speed with which a user can obtain useful results from the
algorithms.
The third point is very important. No program should be considered acceptable until
it has been tested fairly extensively. If possible, any method which gives solutions
that can be checked by computing diagnostics should compute such information
routinely. For instance, I have had users of my eigenvalue/eigenvector programs call
me to say, ‘Your program doesn’t work!’ In all cases to date they have been
premature in their judgement, since the residuals computed as a routine adjunct to
the eigensolution formation have shown the output to be reasonable even though it
might be very different from what the user expected. Furthermore, I have saved