A Parallel Algorithm for Solving General Tridiagonal Equations

A parallel algorithm for the solution of the general tridiagonal system is presented. The method is based on an efficient implementation of Cramer’s rule, in which the only divisions are by the determinant of the matrix. Therefore, the algorithm is defined without pivoting for any nonsingular system. $O(n)$ storage is required for n equations and $O(\log n)$ operations are required on a parallel computer with n processors. $O(n)$ operations are required on a sequential computer. Experimental results are presented from both the CDC 7600 and CRAY-1 computers.