Optimal elimination for sparse symmetric systems as a graph problem.

Authors:
W. R. Spillers and Norris Hickerson

Journal:
Quart. Appl. Math. **26** (1968), 425-432

MSC:
Primary 65.35

DOI:
https://doi.org/10.1090/qam/233497

MathSciNet review:
233497

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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".

**[1]**Gabriel Kron,*Diakoptics*, Macdonald, London, 1963. (References to most of Kron's work can be found in this collection.)**[2]**Franklin H. Branin,*The relation between Kron's method and the classical methods of network analyses*, IRE WESCON Convention Record, Part 2, 1959, pp. 1-29**[3]**J. Paul Roth,*An application of algebraic topology: Kron's method of tearing*, Quart. Appl. Math.**17**, 1 (1959) MR**0104337****[4]**W. R. Spillers,*Network techniques applied to structures*, The Matrix and Tensor Quarterly**15**, 2 (1964)**[5]**W. R. Spillers,*On diakoptics: tearing an arbitrary system*, Quart. Appl. Math.**23**, 2 (1965)**[6]**Richard Bellman,*Dynamic programming*, Princeton Univ. Press, Princeton, N. J., 1957 MR**0090477****[7]**Richard Bellman,*Combinatorial processes and dynamic programming*, Report P-1284, The RAND Corporation, February 24, 1958**[8]**T. S. Motzkin and E. G. Straus,*Some combinatorial extremum problems*, Proc. Amer. Math. Soc.**7**, 1014-1021 (1956) MR**0083457****[9]**Oystein Ore,*Theory of graphs*, Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, R. I., 1962 MR**0150753****[10]**Merrell M. Flood,*The traveling-salesman problem*, J. Operations Research Society of America**4**, 61 (1956) MR**0078639****[11]**T. S. Motzkin,*The assignment problem*, Proc. Sympos. Appl. Math. Vol. 6, Amer. Math. Soc, Providence, R. I., 1956 MR**0090480****[12]**Richard Bellman,*Decision making in the face of uncertainly*--I, Naval Research Logistics Quart. (3)**1**, 230-232 (1954) MR**0067446**

Retrieve articles in *Quarterly of Applied Mathematics*
with MSC:
65.35

Retrieve articles in all journals with MSC: 65.35

Additional Information

DOI:
https://doi.org/10.1090/qam/233497

Article copyright:
© Copyright 1968
American Mathematical Society