# Level scheduling of triangular sparse matrices

Assume one has a triangular sparse matrix and want to solve $Lx=b$ where $b$ and $L$ are known. This can be done easily by using forward substitution when $L$ is a lower triangular matrix. Forward substitution is highly sequential and hard to implement in parallel. I have read some articles about level scheduling where $L$ is reordered so that different levels appear which can be solved in parallel. A good reference seems to be the book of Saad where also the forward substitution with level scheduling is explained.

But I do not really get how the level scheduling is performed and the vector $q$ is filled. Could someone please provide an example or something?

• Even if parallelized, the problem as stated is intrinsically BLAS2 and your opportunities for speedup might be limited (you're probably already memory-bound, adding more processors won't change this). That said, solving by multiple right hand sides is BLAS3, and does require some thought/strategy to parallelize, so I do think the question is worth asking and answering. – rchilton1980 Aug 8 '18 at 16:06
• Memory bound code still needs to be parallel to realize full system bandwidth. – Reid.Atcheson Aug 8 '18 at 16:12
• On many contemporary x86_64 desktop systems, one or two (of 8 or even 16) cores can easily saturate the memory bandwidth. There's not a lot of benefit to parallelizing operations like matrix-vector multiplication on such systems. – Brian Borchers Aug 10 '18 at 1:29
• "the book of Saad" is a particularly bad reference/citation... – Jakub Klinkovský Sep 25 '18 at 19:28