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.