The Solution of Tridiagonal Linear Systems on the CDC STAR 100 Computer

Abstract

The problem of solving tridmgonal linear systems on vector computers is considered. In particular, implementations of several direct and lterative methods are given for the Control Data Corporatlon STAR-100 computer. The direct methods considered are Gaussian elimination, a parallel method due to Stone, and cyclic reduction; the iteratlve methods considered are Jacobi's method, successive overrelaxaUon, and a parallel method due to Traub. In addition, timing formulas for the methods based on current information are included to provide a basis for comparison In general, the direct methods are found to be superior to the iterative methods. The choice of direct methods depends on the size of the system, but for more than 125 equations, cyclic reduction is the fastest algorithm.