Pairwise reduction for the direct, parallel solution of sparse, unsymmetric sets of linear equations
Timothy A. Davis, Edward S. Davidson · IEEE Transactions on Computers · 1988
A paradigm for concurrent computing is explored in which a group of autonomous, asynchronous processes shares a common memory space and cooperates to solve a single problem. The processes synchronize with only a few others at a time; barrier synchronization is not permitted except at the beginning and end of the computation. The paradigm maps directly to a shared-memory multiprocessor with efficient synchronization primitives and is applied to the solution of a large, sparse system of linear equations. The algorithm, called pairwise solve (or PSolve), is presented with several variants to address some of the limitations of previous algorithms. On the Alliant FX/8, PSolve is faster than Gaussian elimination and two common sparse matrix algorithms.>