Sparse Matrix Factorization on SIMD Parallel Computers

Massively parallel SIMD computers, in principle, should be good platforms for performing direct factorization of large, sparse matrices. However, the high arithmetic speed of these machines can easily be overcome by overhead in intra- and inter-processor data motion. Furthermore, load balancing is difficult for an “unstructured” sparsity pattern that cannot be dissected conveniently into equal-size domains. Nevertheless, some progress has been made recently in LU and QR factorization of unstructured sparse matrices, using some familiar concepts from vector-supercomputer implementations (elimination trees, supernodes, etc.) and some new ideas for distributing the computations across many processors. This paper describes programs based on the standard data-parallel computing model, as well as those using a SIMD machine to implement a dataflow paradigm