Practical efficacy of parallel back substitution

Question

The fact that the back substitution is not done in parallel is not important, because it uses a negligible amount of computer time when N is large, compared to the forward elimination.

This is a citation from this book (page 204) when discussing the implementation of parallel solution of linear systems using Gaussian elimination. I suspect that in practice people do parallelize back substitution and a brief googling shows that such algorithms exist. So the questions are:

1. When parallel back substitution is reasonable and when it is not?
2. What is the most effective parallel back substitution algorithm so far?

Answer 1

You are right that, if there are only $O(1)$ right-hand sides available to be simultaneously solved, then triangular solves are not very scalable. However, if there are $p$ processes and $O(p)$ right-hand sides, then scalable algorithms exist since each right-hand side is independent.

I believe that the current gold standard for parallel triangular solves with a single right-hand side is this paper by Joshi et al.. Fast scalable triangular solves are important to many algorithms, especially when an approximate factorization is embedded in a Krylov algorithm, as one or more triangular systems will need to be solved at every iteration. One effective trick is to explicitly invert the triangular matrices of the factors so that the triangular solves become triangular matrix-vector multiplications (see selective inversion).