Efficient sparse matrix factorization on high performance workstations—exploiting the memory hierarchy

Reviewer: Andrew Donald Booth

The problem of solving sparse matrix problems on RISC workstations is considered in this interesting paper. The authors point out that recent technological advances make the use of desktop devices, if not timewise competitive with Cray-type supercomputers, at least a reasonable alternative. First, the authors point out that, on non-vector machines, the greatest cause of inefficiency is not arithmetic speed but memory access time. They then enumerate various methods for left and right looking and Cholesky factorization and present schematic pseudocode. A discussion of the details of cache memory use follows. Cache memory is of current interest because CPU speed has now far surpassed the speed of inexpensive memory chips. Most of the better 486 machines, for example, have between 64K and 256K of high-speed cache RAM as standard. The disadvantages appear, of course, when the cache does not contain the desired data, and the authors consider in detail how matrix factorization methods can best be tailored to available cache. The results of actual runs using the SPARSPAK test package, the proposed methods, and a DEC 3100 with a MIPS R2000 coprocessor are given. These results, presented in a series of tables, suggest that the methods proposed by the authors can effect a speed-up of as much as three times in suitable cases. Also, a series of graphs displays the improvement to be expected with an increase in cache size. A final comparison shows that the Cray Y-MP may be 60 times faster than the workstation. It must be pointed out, however, that the DEC workstation used is by no means state of the art; available technology improves on it by a factor of about three. This valuable paper will be of interest to anyone involved in numerical work with large matrices.