Symbolic Generation of an Optimal Crout Algorithm for Sparse Systems of Linear Equations

Abstract

An efficient implementation of the Crout elimination method in solving large sparse systems of linear algebraic equations of arbitrary structure is described. A computer program, GNSO, by symbolic processing, generates another program, SOLVE, which represents the optimal reduced Crout algorithm in the sense that only nonzero elements are stored and operated on. The method presented is particularly powerful when a system of fixed sparseness structure must be solved repeatedly with different numerical values. In practical examples, the execution of SOLVE was observed to be typically N times as fast as that of the full Crout algorithm, where N is the order of the system. © 1970, ACM. All rights reserved.