What is the best algorithm for solving a band-diagonal matrix?

Question

I'm trying to figure out the best way to solve a pentadiagonal matrix. Is there something faster than gaussian elimination?

Answer 1

You should do an LU or Cholesky decomposition of the matrix, depending on if your matrix is Hermitian positive definite or not, and then do back substitution with the factors. This is essentially just Gaussian elimination, but tends to have better numerical properties. I recommend using LAPACK since those implementations tend to be the fastest and the most robust. Look at the _GBSV routines, where the blank is one of s, d, c, z, depending on your number type.

Edit: In case you're asking if there is an algorithm faster than the factor/solve (Gaussian elimination) method, no there is not. A specialized factorization routine for a banded matrix takes about 4n*k^2 operations (k is the bandwidth), while the backward substitution takes about 6*n*k operations. Thus, for fixed bandwidth, you cannot do better than linear time in n.