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.

Log in or registerto write something here or to contact authors.