Tridiagonal Matrix Algorithm - Variants

Variants

In some situations, particularly those involving periodic boundary conditions, a slightly perturbed form of the tridiagonal system may need to be solved:

\begin{align} a_1 x_{n} + b_1 x_1 + c_1 x_2 & = d_1, \\ a_i x_{i - 1} + b_i x_i + c_i x_{i + 1} & = d_i,\quad\quad i = 2,\ldots,n-1 \\ a_n x_{n-1} + b_n x_n + c_n x_1 & = d_n. \end{align}

In this case, we can make use of the Sherman-Morrison formula to avoid the additional operations of Gaussian elimination and still use the Thomas algorithm. The method requires solving a modified non-cyclic version of the system for both the input and a sparse corrective vector, and then combining the solutions. This can be done efficiently if both solutions are computed at once, as the forward portion of the pure tridiagonal matrix algorithm can be shared.

In other situations, the system of equations may be block tridiagonal (see block matrix), with smaller submatrices arranged as the individual elements in the above matrix system(e.g., the 2D Poisson problem). Simplified forms of Gaussian elimination have been developed for these situations.

The textbook Numerical Mathematics by Quarteroni, Sacco and Saleri, lists a modified version of the algorithm which avoids some of the divisions (using instead multiplications), which is beneficial on some computer architectures.

Read more about this topic:  Tridiagonal Matrix Algorithm

Famous quotes containing the word variants:

    “Nationalist pride, like other variants of pride, can be a substitute for self-respect.”
    —Eric Hoffer (1902–1983)