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.