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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
Cyclic reduction algorithm should be feasible. See for example http://www.cse.illinois.edu/courses/cs554/notes/09_tridiagonal_8up.pdf.
answered Jan 18 '12 at 17:28
