Efficient Parallel Sparse Triangular Solution Using Selective Inversion
Padma Raghavan · Parallel Processing Letters · 1998
In a fully parallel sparse direct solver the matrix factors are first computed and then used in forward and back substitution steps to compute the solution. On message passing multiprocessors these substitution steps are not performed at high efficiency and pose a performance bottleneck for applications in which many systems with the same matrix are solved. We present a "selective inversion" scheme (SI) which computes inverses of a sequence of submatrices of the factor and uses these to replace substitution steps by more efficient distributed matrix-vector multiplications. Experiments on the Intel Paragon and the IBM-SP2 demonstrate that the scheme has ideal scaled efficiency for 1 – 128 processors and is significantly faster than the traditional approach. The cost of selective inversion is a small fraction of the factorization cost; it is approximately 6% of the factorization cost for the model, two and three dimensional five-point, finite-difference grids. On message-passing multiprocessors with high communication latency, the extra inversion cost is easily offset by reduced triangular solution time even for a relatively small number of right-hand-side vectors.