NTRS - NASA Technical Reports Server

Back to Results
Parallel tridiagonal equation solversThree parallel algorithms were compared for the direct solution of tridiagonal linear systems of equations. The algorithms are suitable for computers such as ILLIAC 4 and CDC STAR. For array computers similar to ILLIAC 4, cyclic odd-even reduction has the least operation count for highly structured sets of equations, and recursive doubling 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, cyclic odd-even reduction appears to be the most preferable algorithm for all cases.
Document ID
Document Type
Technical Memorandum (TM)
Stone, H. S. (NASA Ames Research Center Moffett Field, CA, United States)
Date Acquired
September 3, 2013
Publication Date
April 1, 1974
Subject Category
Report/Patent Number
Distribution Limits
Work of the US Gov. Public Use Permitted.

Available Downloads

NameType 19740024891.pdf STI