The influence of relaxed supernode partitions on the multifrontal method

Reviewer: Michael Donoho Fry

The authors show how to solve large, sparse, positive definite systems of linear equations on a Cray X-MP a little faster without using a lot more memory. With its intimidating title, this paper is unlikely to draw a large audience outside of specialists in this research, but others can benefit from reading it. The paper begins with some of the history of two rival algorithms, the “multifrontal method” and the “general sparse method.” The multifrontal method had disadvantages that have since been overcome, so that it now runs two to three times as fast as the general sparse method. The improvements that overcame these disadvantages were presented in an earlier paper by Ashcraft [1]. Matrix factorization takes place in steps that trace a postorder traversal of an “elimination tree.” Expensive overhead can be reduced by collecting the tree's nodes into “supernodes.” Why is this effort to gain a few more percentage points of performance worth investigation__?__ Supercomputers spend a lot of their productive time solving this type of system of equations, but that only explains specialists' interest. The authors employ a simple idea. Back off from shrinking the problem. Make the problem a little bigger, requiring a little more memory and a few million more arithmetic operations, but arrange it so that more of the arithmetic can use the vector architecture of the machine and run at 100–125 megaflops rather than at the 8–<__?__Pub Caret>10 megaflops of scalar arithmetic. The authors do not pretend to have invented this idea themselves; they simply record the thinking that went into one use of it. The partitioning into supernodes permits more vector arithmetic. The authors give statistics on test runs so the reader can judge the success of the effort. They also invite the reader to explore other avenues, including other criteria for partitioning nodes and alternative multiprocessor implementations. The paper and its bibliography offer a well-motivated entry point for readers interested in learning about vector architecture and how matrix algorithms are developed for it. It is not easy reading, but it is accessible to a larger audience than its title would suggest.