How to Efficiently Solve a Tridiagonal Matrix with Fringes?

[maka89]

Hello everyone!

I am trying to solve a large system of linear equations. The form of the matrix is A = T + F. T is basically a tridiagonal matrix and F has two "lines" of numbers running parallel to the diagonal but at some distance. Basically like this one, but not symmetric, nor is it diagonally dominant.

Questions:
Is there any efficient algorithm to solve this kind of matrix?

Is there any way to turn the matrix into a diagonally dominant one, so that a straight forward iterative method could be used?

Could one make a custom iterative method, that does not require diagonal dominance? Would $\overline{x}_{i+1} = T^{-1}(\overline{b}-F \overline{x}_{i})$ work?

 

[SteamKing]

There are routines designed to solve sparse, banded matrices.

http://en.wikipedia.org/wiki/Sparse_matrix

http://en.wikipedia.org/wiki/Preconditioner

I would suggest you look at the routines SPARSE 1.3 and SPARSE-BLAS on netlib as these are collections of routines designed to deal with sparse matrices:

http://www.netlib.org/liblist.html

There is also a proprietary set of routines called SPARSPAK which is available from the U of Waterloo in Canada.

In general, these routines will optimize storing the sparse matrix (since most of the elements are zero, a considerable savings in memory space can be obtained) and also apply pre-conditioning to improve the accuracy of the solution.