Recall that the solution to a
system of linear equations can be obtained by solving the
matrix problem Ax = b. A
tridiagonal system of
linear equations is simply one in which A is a
tridiagonal matrix.
A tridiagonal matrix is one in which all elements are zeroes, except at the diagonal, and two elements, one above and one below each element of the diagonal.
ie, A is:
+- -+
| d1 u1 0 0 0 ...... 0 |
| l2 d2 u2 0 0 ...... 0 |
| 0 l3 d3 u3 0 ...... 0 |
| 0 0 l4 d4 u4 ...... 0 |
| . |
| . |
| un-1 |
| 0 0 0.........0 ln dn |
+- -+
There are many ways to solve this system of equations. One can always use Gaussian elimination, of course. However, techniques such as odd-even reduction, can make solving this much less compuationally expensive.
Another way to solve this would be to reduce the problem to a linear recurrence, or prefix summing problem.