The Exact Solution of Systems of Linear Equations with Polynomial Coefficients

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Exact Solution of Systems of Linear Equations with Polynomial Coefficients

Full text

Pdf (1.90 MB)

Source

Journal of the ACM (JACM) archive
Volume 20 , Issue 4 (October 1973) table of contents

Pages: 563 - 588

Year of Publication: 1973

ISSN:0004-5411

Author

Michael T. McClellan

Computer Science Center, University of Maryland, College Park, Maryland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 44, Citation Count: 20

Additional Information:

references cited by index terms

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/321784.321787 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	BARzIss, E.H. Sylvester's identity and multistep integer-preserving Gaussian elimination. Math. Comp. $~, 103 (July 1968), 565-578.
	2	BIRKHOFF, G., AND M^CLANE, S. A Survey of Modern Algebra, 3rd Ed., Macmillan, New York, 1965.
	3	BODWIG, E. Matrix Calculus. Interscience, New York, 1959.
	4	BOROSH, I., AND FRANKEL, A.S. Exact solutions of linear equations with rational coefficients by congruence techniques. Math. Comp. SO, 93 (Jan. 1966), 107-112.
	5	FRAENKEL, A. S., AND LOEWENTHAL, D. Exact solutions of linear equations with rational co* efficients. J. Res. NBS 75B, 1, 2 (Jan.-June, 1971), 67-75.
	6	BROwN, W.S, HYDE, J.P.,ANDT^GuE, B.A. The ALPAK system for nonnumerical algebra on a digital computer--III : Systems of linear equations and a class of side relations. Bell Syst. Tech. J. 4,S, 2 (July 1964), 1547-1562.
	7	BROWN, W. S. The compleat Euclidean algorithm. Bell Telephone Labs. Rep., Murray Hill, N.J., June 1968.
	8	W. S. Brown, On Euclid's algorithm and the computation of polynomial greatest common divisors, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.195-211, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806288]
	9	George E. Collins, Subresultants and Reduced Polynomial Remainder Sequences, Journal of the ACM (JACM), v.14 n.1, p.128-142, Jan. 1967 [doi>10.1145/321371.321381]
	10	COLLINS, G.E. Computing time analyses for some arithmetic and algebraic algorithms. Proc. 1968 Summer Inst. on Symbolic Mathematical Computation, R. Tobey, Ed., IBM Federal Systems Ctr., June 1969, pp. 195-232.
	11	COLLINS, G. E., HEINDEL, L. E., HOROWITZ, E., McCLELLAN, M. T., AND MUSSER, D.R. The SAC-1 modular arithmetic system. Computing Ctr. Tech. Rep. 10, U. of Wisconsin, Madison, Wisc., June 1969.
	12	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]
	13	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]
	14	COLLtNS, G.E. The SAC-1 polynomial greatest common divisor and resultant system. Computer Sci. Dep. Teeh. Rep. 145, U. of Wisconsin, Madison, Wisc., Feb. 1972.
	15	COLm NS, G. E., AND MCCLELLAN, M.T. The SAC-1 polynomial linear algebra system. Computer Sci. Dep. Tech. Rep. 154, U. of Wisconsin, Madison, Wisc., Apr. 1972.
	16	Fox, L. An Introduction to Numerical Linear Algebra. Clarendon Press, Oxford, 1964.
	17	GANT~ACHER, F.R. Matrix Theory, Vol. 1. Chelsea, New York, 1959.
	18	~OWELL, J. A., AND GREGORY, R.T. An algorithm for solving linear algebraic equations using residue arithmetic. BIT 9 (1969), 200-234, 324-337.
	19	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	20	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	21	LIPSON, J.D. Symbolic methods for the computer solution of linear equations with applications to flow-graphs. Proc. 1968 Summer Inst. on Symbolic Mathematical Computation, Robert Tobey, Ed., IBM Federal Systems Ctr., June 1969, pp. 233-303.
	22	John D. Lipson, Chinese remainder and interpolation algorithms, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.372-391, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806309]
	23	H. A. Luther , L. F. Guseman, Jr., A finite sequentially compact process for the adjoints of matrices over arbitrary integral domains, Communications of the ACM, v.5 n.8, p.447-448, Aug. 1962 [doi>10.1145/368637.368764]
	24	McCLELLAN, M. T. The exact solution of systems of linear equations with polynomial coefficients. Computer Sci. Dep. Tech. Rep. 136 (Ph.D. Th.), U. of Wisconsin, Madison, Wisc., Sept. 1971.
	25	NEWMAN, M, Solving equations exactly. J. Res. NBS 71B, 4 (Oct.-Dec. 1967), 171-179.
	26	RALSTON, A. A First Course in Numerical Analysis. McGraw-Hill, New York, 1965.
	27	ROSSER, J. B. A method of computing exact inverses of matrices with integer coefficients. J. Res. NBS/~9, 5 (Nov. 1952), 349-358.
	28	TAKAHASI, H., AND ISHIBASHI, Y. A new method for "exact calculation" by digital computer. Information Processing in Japan I (1961), 28-42.

CITED BY 20

	Tateaki Sasaki , Hirokazu Murao, Efficient Gaussian Elimination Method for Symbolic Determinants and Linear Systems, ACM Transactions on Mathematical Software (TOMS), v.8 n.3, p.277-289, Sept. 1982
	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
	C. Bajaj , I. Ihm, Hermite interpolation of rational space curves using real algebraic surfaces, Proceedings of the fifth annual symposium on Computational geometry, p.94-103, June 05-07, 1989, Saarbruchen, West Germany
	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
	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
	H. I. Epstein, Using basis computation to determine pseudo-multiplicative independence, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.229-237, August 10-12, 1976, Yorktown Heights, New York, United States
	Paul D. Domich, Residual hermite normal form computations, ACM Transactions on Mathematical Software (TOMS), v.15 n.3, p.275-286, Sept. 1989
	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
	Sergei A. Abramov , Manuel Bronstein, On solutions of linear functional systems, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.1-6, July 2001, London, Ontario, Canada
	Thom Mulders , Arne Storjohann, Rational solutions of singular linear systems, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.242-249, July 2000, St. Andrews, Scotland
	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
	Paul S. Wang , Tadatoshi Minamikawa, Taking advantage of zero entries in the exact inverse of sparse matrices, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.346-350, August 10-12, 1976, Yorktown Heights, New York, United States
	Manuel Bronstein , Thom Mulders , Jacques-Arthur Weil, On symmetric powers of differential operators, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.156-163, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	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
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Brent Gregory , Erich Kaltofen, Analysis of the binary complexity of asymptotically fast algorithms for linear system solving, ACM SIGSAM Bulletin, v.22 n.2, p.41-49, April 1988
	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
	Giuliano Casale, An efficient algorithm for the exact analysis of multiclass queueing networks with large population sizes, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 2006
	D. E. Khmelnov, MEG-Eliminations, Programming and Computing Software, v.27 n.1, p.12-17, January-February 2001
	Susan Hert , Michael Hoffmann , Lutz Kettner , Sylvain Pion , Michael Seel, An adaptable and extensible geometry kernel, Computational Geometry: Theory and Applications, v.38 n.1-2, p.16-36, September, 2007