Page 239 - Compact Numerical Methods For Computers

Left-overs 227

To measure efficiency of an algorithm, we could time the execution. This is
generally quite difficult with a time-shared machine and is in any case highly
dependent on the compiler or interpreter in use as well as on a number of
programming details, and may be affected quite markedly by special hardware
features of some machines. Therefore, a measure of work done is needed which
does not require reference to the machine and I have chosen to use equivalent
function evaluations (efe’s). This is the number of function evaluations required to
minimise a function plus, in the case of algorithms requiring derivatives, the
number of function evaluations which would have been required to approximate
the derivatives numerically. For a problem of order n, a program requiring ig
gradient evaluations and ifn function evaluations is then assigned
efe=(n+l)*ig+ifn (18.29)

equivalent function evaluations. I use the factor (n+1) rather than n because of
the particular structure of my programs. The use of equivalent function evalua-
tions, and in particular the choice of multiplier for ig, biases my appraisal against
methods using derivatives, since by and large the derivatives are not n times more
work to compute than the function. Hillstrom (1976) presents a more comprehen-
sive approach to comparing algorithms for function minimisation, though in the
end he is still forced to make some subjective judgements.
Having decided to use equivalent function evaluations as the measure of
efficiency, we still have a problem in determining how to use them, since the
omission of some problems for each of the methods means that a method which
has successfully solved a problem involving many parameters (the maximum in
any of the tests was 20, but most were of order five or less) may appear less
efficient than another method which was unable to tackle this problem. To take
account of this, we could determine the average number of equivalent function
evaluations to convergence per parameter, either by averaging this quantity over
the successful applications of a method or by dividing the total number of efe’s for
all successful cases by the total number of parameters involved. In practice, it was
decided to keep both measures, since their ratio gives a crude measure of the
performance of algorithms as problem order increases.
To understand this, consider that the work required to minimise the function in
any algorithm is proportional to some power, a, of the order n, thus
a
w =pn . (18.30)
The expected value of the total work over all problems divided by the total
number of parameters is approximated by

(18.31)

The average of w/n over all problems, on the other hand, is approximately

(18.32)