Gaussian Elimination on a Banded Matrix
, by Jeff Thorson
Two FORTRAN routines included in this paper can be used to solve
banded linear systems. The routines use a Gaussian elimination algorithm
tailored to the specific banded matrix. Instead of the n^3/s
multiples required to reduce a full matrix, a banded matrix can be
reduced in about nm^2/4 multiples, where n is the dimension of the
matrix and m is its bandwidth. Only the nonzero diagonals of the matrix
need to be stored. Algorithm 2 does no pivoting. Algorithm 3 performs
partial pivoting. partial pivoting is inherently stabler than no pivoting
at all, though the difference in output between the two algorithms is
probably negligible for regular wave equation operators. The algorithm
listings contain all relevant documentation for their use.
STANFORD