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

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**(1959), 1–24. MR**0104337**, https://doi.org/10.1090/S0033-569X-1959-0104337-1**[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 University 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**(1956), 1014–1021. MR**0083457**, https://doi.org/10.1090/S0002-9939-1956-0083457-1**[9]**Oystein Ore,*Theory of graphs*, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR**0150753****[10]**Merrill M. Flood,*The traveling-salesman problem*, Operations Res.**4**(1956), 61–75. MR**0078639****[11]**T. S. Motzkin,*The assignment problem*, Proceedings of Symposia in Applied Mathematics. Vol. VI. Numerical analysis, Published by McGraw-Hill Book Company, Inc., New York, 1956 for the American Mathematical Society, Providence, R. I., 1956, pp. 109–125. MR**0090480****[12]**Richard Bellman,*Decision making in the face of uncertainty. I*, Naval Res. Logist. Quart.**1**(1954), 230–232 (1955). MR**0067446**, https://doi.org/10.1002/nav.3800010311

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