Optimal elimination for sparse symmetric systems as a graph problem.
William R. Spillers, Norris Hickerson · Quarterly of Applied Mathematics · 1968
The optimal (requiring the minimum number of multiplications) ordering of a sparse symmetric system of linear algebraic equations to be used with Gaussian elimination is first developed as a graph problem which is then treated using the functional equation techniques of dynamic programming. A simple algorithm is proposed as an alternative to the more lengthy procedures of dynamic programming and this algorithm is shown to be effective for systems whose graphs are “grids".