As is explained in Section 5, the algorithm inplemented by `algo' is designed to be simple and clear, not efficient. Surprisingly, this algorithm is in fact reasonably practical, once the modification suggested in Exercise 20 is made. It does, however, have major shortcomings as a method of doing examples in Matlab. The numbers involved in the computations may become so large that Matlab cannot retain all their digits and the calculations become incorrect.
(Matlab is designed to compute very accurately and effectively with approximations to real numbers, not with integers. It does handle integers up to about 14 digits long. When your numbers become too large, Matlab will begin displaying them in scientific notation, with decimal points and exponents. You may want to enter the instruction `format rat' at the Matlab prompt, which will cause numbers in all subsequent computations to be displayed as integers, unless they contain a large number of digits, in which case they will not be shown at all, and their presence will be noted by an asterisk.)
The numbers in the upper left mxn corner of a matrix in `hat format' may become very large when `algo' is applied, but usually only at the intermediate stages of the calculation; when the algorithm terminates, the intries in this corner will not be too large in most cases. However, the matrices M and N in the upper right and lower left corner tend to grow and keep growing, quickly exceeding Matlab's capacity. Therefore, if M and N are needed as well as D, this algorithm is quite impractical even if the computations are being done with a system, like Mathematica or Maple, designed to deal with large integers.
An alternative algorithm is implemented by the Matlab function `algo2'. Instead of restricting itself to additions and subtractions of adjacent rows and columns, `algo2' uses the full range of operations provided by `rcop'. The actual algorithm embodied in `algo2' will not be explained here. All that matters is that the algorithm performs `rcop' operations on the first m rows and the first n columns of a matrix in hat format, it always terminates with a diagonal matrix in the upper left mxn corner, and the numbers do not become too large.Try to write out a precise description of the algorithm embodied in `algo2' by applying it to specific examples (like `algo', it operates on matrices in hat format) and observing what steps it takes.
Return to Chapter 2.