Parallel Tridiagonal Equation Solvers

Abstract

The arithmetic complexity of three parallel algorithms for the direct solution of tndtagonal linear systems of equations Is compared. The algorithms are suitable for computers such as ILLIAC IV and CDC STAR. For array computers slmdar to ILLIAC IV, the cychc odd-even reduction algorithm has the least operation count for highly structured sets of equations, and the recursive doubling algorithm has the least count for relatively unstructured sets of equations. Since the difference in operation counts for these two algorithms is not substantial, their relative running times may be more related to overhead operations, which are not measured in this paper. The third algorithm, based on Buneman's Poisson solver, has more arithmetic operations than the others and appears to be the least favorable. For pipeline computers similar to CDC STAR, the cychc odd-even reduction algorithm appears to be the most preferable algorithm for all cases. When the tridiagonal system satisfies a strong diagonal dominance condition, the intermediate values computed by the cychc odd-even reduction algorithm form a rapidly convergent sequence, and thus the algorithm can be terminated early when values are correct to within machine accuracy. The convergence is linear until off-diagonal terms fall below one-third the magnitude of the diagonal element, at which pomt the convergence becomes quadratic. The quadratic convergence is superior to the linear convergence reported by Traub for several parallel lteratlve tndmgonal solvers.