I am trying to find an efficient way to solve linear systems for the case of sparse symmetric positive definite matrices which have a banded structure except for the case of a few "outliers" that are outside the band. The matrix sizes i'm dealing with are about 2000x2000 or less in size. They are square.
Sometimes, the matrices have relatively small bandwidth (for instance, bandwidth of 9) and have a structure that looks like this:
My understanding is that when the matrix looks like this, the most efficient way to solve this is to use a banded Gaussian elimination. Is this correct?
Other times, though, the bandwidth of the matrix looks much worse, but only do to a few outliers, like this:
Notice that the matrix is still very banded, except for the few outliers which cause the bandwidth to be much larger. I have tried using bandwidth-reducing reordering algorithms like Symmetric reverse Cuthill-McKee, but those only slightly reduce the bandwidth. Is there a better way to solve these cases efficiently?