Quarterly of Applied Mathematics

Quarterly of Applied Mathematics

Online ISSN 1552-4485; Print ISSN 0033-569X



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

References [Enhancements On Off] (What's this?)

  • [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

Similar Articles

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

American Mathematical Society