The solution of unsymmetric tridiagonal Toeplitz systems by the strides reduction algorithm (Q1323644)

The authors develop a cyclic reduction method for the fast numerical solution of unsymmetric constant tridiagonal Toeplitz linear systems which occur repeatedly in the solution of the implicit finite difference equations derived from linear first order hyperbolic equations under a variety of boundary conditions. This algorithm consists of successive reduction of the system to similar systems in a `stride of 2' with the first reduction stage being different from the remaining stages and also yields savings in storage and time. Also a reduction algorithm with `a stride of 3' is presented. This algorithm has the advantage that for the unsymmetric case all the reduction stages are identical. The methods discussed are shown to be viable parallel algorithms with the enhanced parallel stride of three as the most efficient one.