Solving Sparse Triangular Linear Systems on Parallel Computers

This paper describes and compares three parallel algorithms for solving sparse triangular systems of equations. These methods involve some preprocessing overhead and are primarily of interest in solving many systems with the same coefficient matrix. The first approach is to use a fixed blocksize and form the inverse of the diagonal blocks. The second approach is to use a variable blocksize and reorder the unknowns so that the diagonal blocks are diagonal matrices. We call the latter technique level scheduling because of how it is represented in the adjacency graph, and we consider both row-wise and jagged diagonal storage for the offdiagonal blocks. These techniques are analyzed for general parallel computers and experiments are presented for the eight-processor Alliant FX/8.