A Comparison of Algorithms for the Exact Solution of Linear Equations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Comparison of Algorithms for the Exact Solution of Linear Equations

Full text

Pdf (698 KB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 3 , Issue 2 (June 1977) table of contents

Pages: 147 - 158

Year of Publication: 1977

ISSN:0098-3500

Author

Michael T. McClellan

Department of Computer Science, University of Maryland, College Park, MD

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 2

Additional Information:

references cited by index terms peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/355732.355735 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BAREISS, E.H. Sylvester's identity and multistep integer-preserving Gaussian elimination. Math. Comput. 22, 103 (July 1968), 565-578.
	2	BAREISS, E.H. Computational solutions of matrix problems over an integral domain. J. Inst. Math. Appl. 10 (1972), 68-104.
	3	BAREISS, E.H., AND MAZUKELLI, D. Multistep elimination over commutative rings. Rep. ANL-7898, Argonne Nat. Lab., Argonne, Ill., April 1972.
	4	W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
	5	CABAY, S., AND LAM, P.L. Congruence techniques for the solution of integer systems of linear equations. Submitted to a technical journal.
	6	COLLINS, G.E. The SAC-1 polynomial system. Tech. Rep. 115, Comptr. Sci. Dep., U. of Wisconsin, Madison, WIN., March 1971.
	7	George E. Collins, The SAC-1 system: An introduction and survey, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.144-152, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806279]
	8	George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
	9	COLLINS, G.E. The SAC-1 polynomial GCD and resultant system. Tech. Rep. 145, Comptr. Sci. Dep., U. of Wisconsin, Madison, WIN., Feb. 1972.
	10	COLLINS, G.E, AND McCLELLAN, M.T. The SAC-1 polynomial linear algebra system. Tech. Rep. No. 154, Comptr. Sc~. Dep., U. of Wisconsin, Madison, WIN., April 1972.
	11	COLLINS, G.E. Computer algebra of polynomials and rational functions. Am. Math. Monthly 80, 7 (Aug.-Sept 1973), 725-755.
	12	Martin L. Griss, The algebraic solution of large sparse systems of linear equations using REDUCE 2, Proceedings of the 1974 annual conference, p.105-111, January 1974 [doi>10.1145/800182.810388]
	13	Martin L. Griss, The Algebraic Solution of Sparse Linear Systems via Minor Expansion, ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.31-49, March 1976 [doi>10.1145/355666.355668]
	14	HOWELL, J A., AND GREGORY, R.T. An algorithm for solving linear algebraic equations using residue arithmetic. BIT 9 (1969), 200-234, 324-337.
	15	E. Horowitz , S. Sahni, On Computing the Exact Determinant of Matrices with Polynomial Entries, Journal of the ACM (JACM), v.22 n.1, p.38-50, Jan. 1975 [doi>10.1145/321864.321868]
	16	KNUTtt, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 1968.
	17	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	18	LIPsON, J.D. Symbolic methods for the computer solution of linear equations with applications to flowgraphs Proc. 1968 Summer Inst. Symbolic Math. Comput. R. Tobey, Ed. IBM Fed Syst. Div., Gaithersburg, Md., pp. 233-303, June 1969.
	19	McCLELLAN, M.T. The exact solution of systems of linear equations with polynomial coefficients. Ph.D. Th., Tech. Rep. 136, Comptr. Sci. Dep., U. of Wisconsin, Madison, WIN., Sept. 1971; available as PB204590, NTIS, Springfield, Va.
	20	Michael T. McClellan, The Exact Solution of Systems of Linear Equations with Polynomial Coefficients, Journal of the ACM (JACM), v.20 n.4, p.563-588, Oct. 1973 [doi>10.1145/321784.321787]
	21	McCLELLAN, M.T. A comparison of algorithms for the exact solution of linear equations. Comptr. Sci. Tech. Rep. TR-290, U. of Maryland, College Park, Md., Jan. 1974.
	22	Michael T. McClellan, The Exact Solution of Linear Equations with Rational Function Coefficients, ACM Transactions on Mathematical Software (TOMS), v.3 n.1, p.1-25, March 1977 [doi>10.1145/355719.355720]
	23	RALSTON, A. A F~rst Course in Numerical Analysis. McGraw-Hill, New York, 1965.

CITED BY 2

	S. Cabay , T. P. L. Lam, Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.386-397, Dec. 1977
	Stanley Cabay , Bart Domzy, Systems of linear equations with dense univariate polynomial coefficients, Journal of the ACM (JACM), v.34 n.3, p.646-660, July 1987

INDEX TERMS

Primary Classification:
G. Mathematics of Computing

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Computations on polynomials

G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.3 Numerical Linear Algebra
Subjects: Linear systems (direct and iterative methods)
G.1.5 Roots of Nonlinear Equations
Subjects: Polynomials, methods for

General Terms:
Algorithms, Design, Theory

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player