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".
Gabriel Kron, Diakoptics, Macdonald, London, 1963. (References to most of Kron’s work can be found in this collection.)
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
- J. Paul Roth, An application of algebraic topology: Kron’s method of tearing, Quart. Appl. Math. 17 (1959), 1–24. MR 104337, DOI https://doi.org/10.1090/S0033-569X-1959-0104337-1
W. R. Spillers, Network techniques applied to structures, The Matrix and Tensor Quarterly 15, 2 (1964)
W. R. Spillers, On diakoptics: tearing an arbitrary system, Quart. Appl. Math. 23, 2 (1965)
- Richard Bellman, Dynamic programming, Princeton University Press, Princeton, N. J., 1957. MR 0090477
Richard Bellman, Combinatorial processes and dynamic programming, Report P-1284, The RAND Corporation, February 24, 1958
- T. S. Motzkin and E. G. Straus, Some combinatorial extremum problems, Proc. Amer. Math. Soc. 7 (1956), 1014–1021. MR 83457, DOI https://doi.org/10.1090/S0002-9939-1956-0083457-1
- Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962. MR 0150753
- Merrill M. Flood, The traveling-salesman problem, Operations Res. 4 (1956), 61–75. MR 78639, DOI https://doi.org/10.1287/opre.4.1.61
- 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
- Richard Bellman, Decision making in the face of uncertainty. I, Naval Res. Logist. Quart. 1 (1954), 230–232 (1955). MR 67446, DOI https://doi.org/10.1002/nav.3800010311
Gabriel Kron, Diakoptics, Macdonald, London, 1963. (References to most of Kron’s work can be found in this collection.)
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
J. Paul Roth, An application of algebraic topology: Kron’s method of tearing, Quart. Appl. Math. 17, 1 (1959)
W. R. Spillers, Network techniques applied to structures, The Matrix and Tensor Quarterly 15, 2 (1964)
W. R. Spillers, On diakoptics: tearing an arbitrary system, Quart. Appl. Math. 23, 2 (1965)
Richard Bellman, Dynamic programming, Princeton Univ. Press, Princeton, N. J., 1957
Richard Bellman, Combinatorial processes and dynamic programming, Report P-1284, The RAND Corporation, February 24, 1958
T. S. Motzkin and E. G. Straus, Some combinatorial extremum problems, Proc. Amer. Math. Soc. 7, 1014–1021 (1956)
Oystein Ore, Theory of graphs, Amer. Math. Soc. Colloq. Publ., Vol. 38, Amer. Math. Soc., Providence, R. I., 1962
Merrell M. Flood, The traveling-salesman problem, J. Operations Research Society of America 4, 61 (1956)
T. S. Motzkin, The assignment problem, Proc. Sympos. Appl. Math. Vol. 6, Amer. Math. Soc, Providence, R. I., 1956
Richard Bellman, Decision making in the face of uncertainly—I, Naval Research Logistics Quart. (3) 1, 230–232 (1954)
Similar Articles
Retrieve articles in Quarterly of Applied Mathematics
with MSC:
65.35
Retrieve articles in all journals
with MSC:
65.35
Additional Information
Article copyright:
© Copyright 1968
American Mathematical Society
