John Travis
Mississippi College
When solving many practical problems involving linear systems, it is the case that the resulting matrix A may contain a significant number of zero entries. This happens often when solving (for example) differential equation problems and when determining the coefficients for cubic splines. These zeros can be exploited to develop algorithms for solving $Ax=b$ using only $O(n)$ calculations and signficantly less storage requirements. These algorithms build off of the matrix factorization techniques that put $A = LU$ and then storing all of the matrices not by horizontal rows and vertical columns but by focusing on "diagonals".
Below, let's consider a case when A is tridiagonal...that is only has nonzero entries on the main diagonal and on the diagonals one above and one below.
n = 7 A = 17 8 0 0 0 0 0 2 17 9 0 0 0 0 0 1 11 9 0 0 0 0 0 6 11 8 0 0 0 0 0 4 13 4 0 0 0 0 0 1 19 9 0 0 0 0 0 5 19 b = 4 4 5 10 7 2 3 n = 7 A = 17 8 0 0 0 0 0 2 17 9 0 0 0 0 0 1 11 9 0 0 0 0 0 6 11 8 0 0 0 0 0 4 13 4 0 0 0 0 0 1 19 9 0 0 0 0 0 5 19 b = 4 4 5 10 7 2 3 
Notice all of the zeros off of these three diagonals. Since they are zeros that won't change using Gaussian Elimination then let's not even store them. To do so, let's just store the values in the three diagonal into three long vectors. In essence, this means the row values in each of these vectors will be correct but the column points will be messed up. Indeed, let's store
$A_{k+1,k}$ into band$(k+1,1)$
$A_{k,k}$ into band$(k,2)$
$A_{k,k+1}$ into band$(k,3)$
which would give the following storage for the matrix above:
Here is the original A: A = 17 8 0 0 0 0 0 2 17 9 0 0 0 0 0 1 11 9 0 0 0 0 0 6 11 8 0 0 0 0 0 4 13 4 0 0 0 0 0 1 19 9 0 0 0 0 0 5 19 Here it is using banded storage: band = 0 17 8 2 17 9 1 11 9 6 11 8 4 13 4 1 19 9 5 19 0 Here is the original A: A = 17 8 0 0 0 0 0 2 17 9 0 0 0 0 0 1 11 9 0 0 0 0 0 6 11 8 0 0 0 0 0 4 13 4 0 0 0 0 0 1 19 9 0 0 0 0 0 5 19 Here it is using banded storage: band = 0 17 8 2 17 9 1 11 9 6 11 8 4 13 4 1 19 9 5 19 0 
Notice that the required memory storage for the matrix A is now $O(3n)$ rather than $O(n^2)$.
We can now modify our existing factorization, forward solving, and backward solving routines to utilize this triadiagonal structure and storage scheme.

mat_factored = 0.00000 17.00000 0.47059 2.00000 16.05882 0.56044 1.00000 10.43956 0.86211 6.00000 5.82737 1.37283 4.00000 7.50867 0.53272 1.00000 18.46728 0.48735 5.00000 16.56326 0.00000 Solving using y = 0.235294 0.219780 0.457895 1.244581 0.269246 0.093720 0.152832 yields x = 0.050496 0.392695 0.308535 0.889021 0.258997 0.019237 0.152832 with bAx = ans = 0 0 0 0 0 0 0 mat_factored = 0.00000 17.00000 0.47059 2.00000 16.05882 0.56044 1.00000 10.43956 0.86211 6.00000 5.82737 1.37283 4.00000 7.50867 0.53272 1.00000 18.46728 0.48735 5.00000 16.56326 0.00000 Solving using y = 0.235294 0.219780 0.457895 1.244581 0.269246 0.093720 0.152832 yields x = 0.050496 0.392695 0.308535 0.889021 0.258997 0.019237 0.152832 with bAx = ans = 0 0 0 0 0 0 0 
Now, modify the routines above to handle a 5diagonal system with two above and two below the main diagonal.
