Sparse matrix computations on an FFP machine

The authors describe and analyze an algorithm for performing Gaussian elimination on sparse linear systems with a FFP machine, a small-grain parallel computer. Given an equation Ax=b, where A is an n×n matrix, the algorithm yields a permuted upper-triangular system, from which the authors obtain x by back-substitution. If A has e nonzero entries and if f fill-ins are created during elimination, then the algorithm solves the system in O(h×(e+f )) time, using O(e+f) processing elements. The parameter h is the height of the FFP machine´s connection network, which is O(log(e+f)). The algorithm makes no assumptions about the structure of A and requires no preprocessing. The pivot order can be given in advance, or it can be chosen at run-time by the Markowitz heuristic with only a linear increase in cost. Also presented are results of simulation on sample problems, both randomly generated and from the Boeing-Harwell set. The results of the simulations, in operation counts, are used to estimate the performance of an FFP machine hardware prototype