5
$\begingroup$

I have a linear system whose matrix that is diagonally dominant, non-symmetric, but banded. Since the band-radius is 2 (producing only 5 variables per equation), a banded direct solver (gaussian elimination without pivoting) should be fairly fast to produce a solution. I was just wondering if there is a way to parallelize a banded gaussian elimination?

$\endgroup$
6
$\begingroup$

From what I have seen from your other question, your half-bandwidth is not actually two, as one of your diagonals is roughly $\sqrt{n}$ entries away from the main diagonal.

With that said, even if you really did have an $O(1)$ bandwidth, I would have pointed you to the general literature on parallel sparse-direct solvers, as $O(1)$ bandwidth can be thought of as a special case where the separators for nested-dissection can be trivially found.

In particular, I recommend chapter 4 of Anshul Gupta's dissertation, Analysis and Design of Scalable Parallel Algorithms for Scientific Computing. I found that chapter, along with Liu's review paper, sufficient to implement a scalable sparse-direct $LDL^T$ factorization without pivoting. I would start with those papers before looking into adding pivoting.

All of the machinery for the general sparse-direct case essentially reduces to the cyclic reduction algorithm that Heath discusses in @Allan P. Engsig-Karup's answer.

$\endgroup$
1
$\begingroup$

Cyclic reduction algorithm should be feasible. See for example http://www.cse.illinois.edu/courses/cs554/notes/09_tridiagonal_8up.pdf.

$\endgroup$

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.