Direct Solutions of Large, Sparse Linear Systems

A comparison is made of the merits of three popular algorithms for direct solutions of large, sparse matrices Gaussian Elimination, LU Decomposition, and Gauss-Jordan Reduction. A mathematical theory discussion explains the algorithms and predicts their performance for arbitrary and strongly structured matrices. Particular emphasis is placed on solution accuracy and the efficient use of core space. The same test problems are used to analyze the Gaussian Elimination algorithm programmed by this student. From a study of the performance of several Gaussian solution strategies, a new strategy is developed which offers the user a range of options for his particular programming needs. The salient points of this strategy include some stability features of partial pivoting and some array optimization similar to minimum row minimum column pivoting. The final Gaussian Elimination program is enhanced by a new packing scheme which is highly suited for the CDC 6600 computer many arrays can be compacted into a single array by subdividing the long computer word structure. A final qualitative comparison is presented from which an optimal solution method is proposed and further study recommended.