Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations

Full text

Pdf (873 KB)

Source

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

Pages: 386 - 397

Year of Publication: 1977

ISSN:0098-3500

Authors

S. Cabay	Department of Computing Science, University of Alberta, Edmonton, Canada T6G 2E1
T. P. L. Lam	Department of Computing Science, University of Alberta, Edmonton, Canada T6G 2E1

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 39, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

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/355759.355765 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. Computational solutions of matrix problems over an integral domain. Y. Inst. Math. Applic. 10 (1972), 68-104.
	2	BORODIN, A., AND MUNRO, I. The Computational Complexity of Algebraic and Numeric Problems. Elsevier, New York, 1975.
	3	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]
	4	Stanley Cabay, Exact solution of linear equations, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.392-398, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806310]
	5	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 [doi>10.1145/355759.355765]
	6	S. Charmonman , J. L. Wagener, On structured programming in FORTRAN, ACM SIGNUM Newsletter, v.10 n.1, p.21-23, January 1975 [doi>10.1145/1053191.1053195]
	7	W. M. Gentleman , S. C. Johnson, Analysis of algorithms, a case study: Determinants of polynomials, Proceedings of the fifth annual ACM symposium on Theory of computing, p.135-141, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804044]
	8	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]
	9	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]
	10	Jo Ann Howell, Algorithm 406: exact solution of linear equations using residue arithmetic [F4], Communications of the ACM, v.14 n.3, p.180-184, March 1971 [doi>10.1145/362566.362572]
	11	T. E. Hull, Would you believe structured Fortran?, ACM SIGNUM Newsletter, v.8 n.4, p.13-16, October 1973 [doi>10.1145/1052646.1052652]
	12	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	13	MAZUKELLI, D. Multistep elimination over commutative rings. Ph.D. Th., Dept. of Math., Northwestern U., Evanston, Ill., 1972.
	14	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]
	15	Michael T. McClellan, A Comparison of Algorithms for the Exact Solution of Linear Equations, ACM Transactions on Mathematical Software (TOMS), v.3 n.2, p.147-158, June 1977 [doi>10.1145/355732.355735]
	16	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]
	17	SCHbNHAO~, A. Schnelle Berechnung yon Kettenbruchentwicklungen. Acta Inforrnatica I (1971), 139-144.
	18	SHAPIRO, G. Gauss elimination for singular matrices. Math. Comput. 17 (1963), 441-445.
	19	YUN, D.Y.Y. The Hensel lemma in symbolic manipulation. Ph.D. Th., Dept. of Math., M.I.T., Cambridge, Mass., 1973.

CITED BY 8

	Gilles Villard, Computation of the Smith normal form of polynomial matrices, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.209-217, July 06-08, 1993, Kiev, Ukraine
	Peter Alfeld , David J. Eyre, The exact analysis of sparse rectangular linear systems, ACM Transactions on Mathematical Software (TOMS), v.17 n.4, p.502-518, Dec. 1991
	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
	Françoise Roch-Siebert , Gilles Villard, PAC: first experiments on a 128 transputers méganode, Proceedings of the 1991 international symposium on Symbolic and algebraic computation, p.343-351, July 15-17, 1991, Bonn, West Germany
	Jörn Springer, Exact solution of general integer systems of linear equations, ACM Transactions on Mathematical Software (TOMS), v.12 n.1, p.51-61, March 1986
	S. Cabay , T. P. L. Lam, Algorithm 522: ESOLVE, Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations [F4], ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.404-410, Dec. 1977
	Erich Kaltofen , Gilles Villard, Computing the sign or the value of the determinant of an integer matrix, a complexity survey, Journal of Computational and Applied Mathematics, v.162 n.1, p.133-146, 1 January 2004
	J.-L. Roch , P. Senechaud , F. Sievert-Rich , G. Villard, Computer algebra on MIMD machine, ACM SIGSAM Bulletin, v.23 n.1, p.16-32, Jan. 1989