Modeling speedup in parallel sparse matrix factorization

This paper is an attempt to explain the observed performance of sparse matrix factorization algorithms on parallel computers. In particular, we examine whether the disappointing performance of these algorithms is due to insufficient parallelism in the problem or to the architectural characteristics of existing parallel computers. Through a series of theoretical models of increasing realism, we first determine upper and lower bounds on the speedup that can be expected in practice for this problem, and end with a parameterized model that is capable of reproducing the full range of behavior within these bounds, including the speedups actually observed in practice. This model suggests that the current limits on speedup in sparse factorization are due to poor communication performance of the present generation of parallel computer architectures rather than to a lack of parallelism in the problem.