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 at 16:06
  • 1
    Memory bound code still needs to be parallel to realize full system bandwidth. – Reid.Atcheson Aug 8 at 16:12
  • 1
    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 at 1:29

You can try to discover parallelism in L and U, but a better approach is to reorder the original matrix. Luby & Jones/Plassman describe this scheme: you can generate a multi-colouring in parallel, and then in the solution every colour has all processors concurrently active.

  • I will have a look. Thanks:) – vydesaster Aug 11 at 21:01

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.