The Exact Solution of Linear Equations with Rational Function Coefficients

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Exact Solution of Linear Equations with Rational Function Coefficients

Full text

Pdf (1.58 MB)

Source

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

Pages: 1 - 25

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): 4, Downloads (12 Months): 36, Citation Count: 3

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/355719.355720 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. Comp. ~2, 103 (July 1968), 565-578.
	2	BOROSH, I., AND FRAENKEL, A.S. Exact solutions of linear equations with rational coefficients by congruence techniques. Math. Comp. $0, 93 (Jan. 1966), 107-112.
	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	COLLINS, G.E. Computing time analyses for some arithmetic and algebraic algorithms. Proc. 1968 Summer Inst. Symbolic Math. Comput., R. Tobey, Ed., IBM Federal Systems Div., Bethesda, Md., June 1969, pp. 195-232.
	5	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]
	6	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]
	7	COLLINS, G.E. The SAC-1 polynomial greatest common divisor and resultant system. Tech. Rep. No. 145, Comptr. Sci. Dep., U. of Wisconsin, Madison, Wis., Feb. 1972.
	8	COLLINS, G.E., AND MCCLELLAN, M.T. The SAC-1 polynomial linear algebra system. Tech. Rep. No. 154, Comptr. Sci. Dep., U. of Wisconsin, Madison, Wis., April 1972.
	9	COLLINS, G.E. Computer algebra of polynomials and rational functions. Amer. Math. Monthly 80, 7 (Aug.-Sept. 1973), 725-755.
	10	FORSYTHE, G., AND MOLER, C.B. Computer Solution of Linear Algebraic Systems. Prentice- Hall, Englewood Cliffs, N.J., 1967.
	11	Ga~.GORY, R.T., AND KARNEr, D.L. A Collection of Matrices for Testing Computational Alqorithms. Wiley, New York, 1969.
	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	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]
	14	HOWELL, J.A., XND GREGORY, R.T. An algorithm for solving linear algebraic equations using residue arithmetic. BIT 9 (1969), 200-234, 324-337.
	15	HOWELL, J.A., AND GREGORY, R.T. Solving linear equations using residue arithmeticalgorithm II, BIT 10 (1970), 23-37.
	16	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	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	LiPso~, J.D. Symbolic methods for the computer solution of linear equations with applications to flowgraphs. Proc. 1968 Summer Inst. Symbolic Math. Comp., R. Tobey Ed., IBM Federal Systems Div., Bethesda, Md., June 1969, pp. 233-303.
	19	MCCLELLAN, M.T. The exact solution of systems of linear equations with polynomial coefficients. Tech. Rep. No. 136 (Ph.D. Th.), Comptr. Sci. Dep., U. of Wisconsin, Madison, Wis., 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 with polynomial coefficients. Tech. Rep. No. TR-290, Comptr. Sci. Ctr., U. of Maryland, College Park, Md., Jan. 1974 (available as PB228460, NTIS, Springfield, Va).
	22	McCLELLAN, M.T. The exact solution of linear equations with rational function coefficients. Tech. Rep. TR-341, Comptr. Sci. Center, U. of Maryland, College Park, Md., Oct. 1974.
	23	MCCLELLAN, M.T. The exact solution of linear equations: Density vs. sparsity. (in preparation).
	24	David R. Musser, Multivariate Polynomial Factorization, Journal of the ACM (JACM), v.22 n.2, p.291-308, April 1975 [doi>10.1145/321879.321890]
	25	NEWMAN, M. Solving equations exactly. J. Res. Nat. Bur. Standards 71B, 4 (Oct.-Dec. 1967), 171-179.
	26	REID, J.K., Ed. Large Sparse Sets of Linear Equations. Academic Press, New York,I 1971.
	27	R~EINSOLDT, W.C., AND MESZTENYI, C.K. Programs for the solution of large sparse matrix problems based on the arc-graph structure. Tech. Rep. TR-262, Comptr. Sci. Center, U. of Maryland, College Park, Md., Sept. 1973.
	28	ROSE, D.J., AND WILLOUGHBY, R.A. Eds., Sparse Matrices and Their Applications. Plenum Press, New York, 1972.
	29	TAK~IASI, H., AND ISH~SASHI, Y. A New Method for "Exact calculation" by digital computer. Information Processing in Japan i (1961), 28-42.
	30	TODD, J. The condition of finite segments of the Hilbert matrix. In Contributions to the Solution of Systems of Linear Equations and the Determination of Eigenvalues, Taussky, O. Ed., Applied Math. Ser., Vol. 39, U.S. Nat. Bur. Standards, 1954, pp. 109-116.

CITED BY 3

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