# Practical efficacy of parallel back substitution

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?

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.