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?

  • $\begingroup$ 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. $\endgroup$ – rchilton1980 Aug 8 '18 at 16:06
  • 1
    $\begingroup$ Memory bound code still needs to be parallel to realize full system bandwidth. $\endgroup$ – Reid.Atcheson Aug 8 '18 at 16:12
  • 1
    $\begingroup$ 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. $\endgroup$ – Brian Borchers Aug 10 '18 at 1:29
  • $\begingroup$ "the book of Saad" is a particularly bad reference/citation... $\endgroup$ – Jakub Klinkovský Sep 25 '18 at 19:28

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.

  • $\begingroup$ Explicit reordering of the original matrix may have other drawbacks, e.g. multi-colouring generally goes against the fill-in minimization in the (incomplete) LU factorization. Depending on the problem, multi-colouring may be actually less efficient than level-scheduling, so I think it's worth answering the original question. $\endgroup$ – Jakub Klinkovský Sep 25 '18 at 19:42
  • $\begingroup$ Actually, explicit re-ordering is what's happening in all classical LU algorithms. Finding levels is more or less multi-frontal. Complete minimization is probably NP complete, but minimum degree does a reasonable job. And then of course one uses a multi-frontal version of that, which gives you parallelism. $\endgroup$ – Victor Eijkhout Sep 26 '18 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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