The algebraic solution of large sparse systems of linear equations using REDUCE 2

ABSTRACT

This paper discusses some of the problems encountered during the solution of a large system of sparse linear equations with algebraic coefficients, using REDUCE 2. Of particular importance is intermediate expression swell, which ultimately uses up all the available storage, and produces voluminous unreadable output. By optimally ordering the equations (optimal pivoting algorithms), and decomposing the intermediate expressions, so as to share common sub-expressions (“hash coded CONS”), a considerable saving in storage is achieved. By suitably renaming frequently used common sub-expressions, using the table built up above, and outputting these first, followed by the more complex expressions, a simplification in the output occurs. These techniques are general, and may be useful in any problem with large expressions to store and output.

REFERENCES

• 1: HUBBELL, S.P., University of Michigan. (Private Communication)
• 2: HEARN, A.C., REDUCE 2 User's Manual, Second Edition, University of Utah Computational Physics Group Report No. UCP-19, March 1973
• 3: BAREISS,E.H, "Sylvester's Identity and Multi-step Integer-Preserving Gaussian Elimination", MATH. COMP. 22 (1968),565-578. 3a. LIPSON, J.D.,"Symbolic Methods for the Solution of Linear Equations with applications to Flowgraphs", Proceedings of the 1968 Summer Institute of Symbolic Computation, IBM Programming Laboratory Report No. FSC 69-0312(1969)
• 4: McCLELLAN, M.T., "A Comparison of Algorithms for the Exact Solution of Linear Equations", University of Maryland Technical Report No. TR-290 (1974)
• 5: TEWARSON, R P., "Sparse Matrices", Vol. 99 of Mathematics in Science and Engineering, Academic Press, 1973
• 6: Ellis Horowitz, The application of symbolic mathematics to a singular perturbation problem, Proceedings of the ACM annual conference, p.816-825, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805865]
• 7: Anthony C. Hearn, REDUCE 2: A system and language for algebraic manipulation, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.128-133, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806277]
• 8: R. G. Tobey, Experience with FORMAC algorithm design, Communications of the ACM, v.9 n.8, p.589-597, Aug. 1966 [doi>10.1145/365758.365773]
• 9: GRANT, J., UCLA,(private communication)
• 10: HEARN, A.C., (Private communication)
• 11: GENTLEMAN, W.M., "On the Evaluation of Symbolic Determinants", University of Waterloo Preprint (1972). 11a. HOROWITZ,E. and S. SAHNI, "On Computing the Exact Determinant of Matrices with Polynomial Entries", Cornell Tech. Report No. 5-72,(to appear in J.ACM).
• 12: GRISS, M.L., "The Output of Large Expressions in REDUCE", University of Utah Computational Physics Group Operating Note No. 14,(June 1974).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Theory

Keywords:
Algebraic computation, Linear equations, Sparse matrices, Symbolic manipulation