An efficient sparse minor expansion algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient sparse minor expansion algorithm

Full text

Pdf (470 KB)

Source

ACM Annual Conference/Annual Meeting archive
Proceedings of the annual conference table of contents

Houston, Texas, United States

Pages: 429 - 434

Year of Publication: 1976

Author

Martin L. Griss

Sponsor

ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract 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/800191.805633 What is a DOI?

ABSTRACT

An improved algorithm for computing the minors of a (large) sparse matrix of polynomials is described, with emphasis on efficiency and optimal ordering. A possible application to polynomial resultant computation is discussed.

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	W.M. Gentleman, On the Evaluation of Symbolic Determinants, University of Waterloo Pre-print, 1972.
	2	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]
	3	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]
	4	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	5	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]
	6	A.C. Hearn, REDUCE 2 User's Manual, Second Edition, University of Utah Computational Physics Group Report No. UCP-19, March, 1973.
	6.1	A.C. Hearn, A Mode Analyzing Algebraic Manipulation Program, Proceedings of ACM 74, San Diego, 1974, 722-724.
	6.2	Martin L. Griss, The definition and use of data structures in REDUCE, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.53-59, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806323]
	7	R.P. Tewarson, Sparse Matrices, Vol. 99 of Mathematics in Science and Engineering, Academic Press, 1973.

CITED BY 2

	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
	J. Smit, A cancellation free algorithm, with factoring capabilities, for the efficient solution of large sparse sets of equations, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.146-154, August 05-07, 1981, Snowbird, Utah, United States