Article

Free access

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

Author:

Martin L. GrissAuthors Info & Claims

ACM '74: Proceedings of the 1974 annual conference - Volume 1

Pages 105 - 111

https://doi.org/10.1145/800182.810388

Published: 01 January 1974 Publication History

PDF eReader

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)

Google Scholar

[2]

HEARN, A.C., REDUCE 2 User's Manual, Second Edition, University of Utah Computational Physics Group Report No. UCP-19, March 1973

Google Scholar

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

Google Scholar

[4]

McCLELLAN, M.T., "A Comparison of Algorithms for the Exact Solution of Linear Equations", University of Maryland Technical Report No. TR-290 (1974)

Google Scholar

[5]

TEWARSON, R P., "Sparse Matrices", Vol. 99 of Mathematics in Science and Engineering, Academic Press, 1973

Google Scholar

[6]

MOSES, J., "Solution of Systems of Polynomial Equations by Elimination", CACM 9 (1966),634-6376a. HOROWlTZ,E., "The Application of Symbolic Mathematics to a Singular Perturbation Problem", Proc. ACM72, Boston(1972) 816-825.

Digital Library

Google Scholar

[7]

HEARN, A.C., "REDUCE 2: A System and Language for Algebraic Manipulation", Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, ACM, New York (1971) 128-133

Digital Library

Google Scholar

[8]

. TOBEY, R.G., "Experience with FORMAC Algorithm Design", CACM 9 (1966),589-597

Digital Library

Google Scholar

[9]

GRANT, J., UCLA,(private communication)

Google Scholar

[10]

HEARN, A.C., (Private communication)

Google Scholar

[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).

Google Scholar

[12]

GRISS, M.L., "The Output of Large Expressions in REDUCE", University of Utah Computational Physics Group Operating Note No. 14,(June 1974).

Google Scholar

Cited By

View all

McClellan M(1977)The Exact Solution of Linear Equations with Rational Function CoefficientsACM Transactions on Mathematical Software10.1145/355719.3557203:1(1-25)Online publication date: 1-Mar-1977
https://dl.acm.org/doi/10.1145/355719.355720
Griss MJoseph EWhite J(1975)The REDUCE system for computer algebraProceedings of the 1975 annual conference10.1145/800181.810335(261-262)Online publication date: 1-Jan-1975
https://dl.acm.org/doi/10.1145/800181.810335

Index Terms

The algebraic solution of large sparse systems of linear equations using REDUCE 2
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

Solution of Sparse Underdetermined Systems of Linear Equations

The problem of computing the minimum-norm solution to a sparse, underdetermined system of linear equations is considered. An algorithm is developed which is based on orthogonal factorization. The algorithm is generalized to cope with systems which are ...
On Asymptotics in Case of Linear Index-2 Differential-Algebraic Equations

Asymptotic properties of solutions of general linear differential-algebraic equations (DAEs) and those of their numerical counterparts are discussed. New results on the asymptotic stability in the sense of Lyapunov as well as on contractive index-2 DAEs ...
On the numerical solution of differential-algebraic equations with index-2

In this paper, numerical solution of differential-algebraic equations (DAEs) with index-2 is considered. An index reduction for DAE with index-2 is suggested. First index-2 system is reduced to index-1 system. Then we have applied the method for solving ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM '74: Proceedings of the 1974 annual conference - Volume 1

January 1974

379 pages

ISBN:9781450374828

DOI:10.1145/800182

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1974

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
282
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

McClellan M(1977)The Exact Solution of Linear Equations with Rational Function CoefficientsACM Transactions on Mathematical Software10.1145/355719.3557203:1(1-25)Online publication date: 1-Mar-1977
https://dl.acm.org/doi/10.1145/355719.355720
Griss MJoseph EWhite J(1975)The REDUCE system for computer algebraProceedings of the 1975 annual conference10.1145/800181.810335(261-262)Online publication date: 1-Jan-1975
https://dl.acm.org/doi/10.1145/800181.810335

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Solution of Sparse Underdetermined Systems of Linear Equations

On Asymptotics in Case of Linear Index-2 Differential-Algebraic Equations

On the numerical solution of differential-algebraic equations with index-2

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations