Preconditioning of rectangular polynomial matrices for efficient Hermite normal form computation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Preconditioning of rectangular polynomial matrices for efficient Hermite normal form computation

Full text

Pdf (765 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 1995 international symposium on Symbolic and algebraic computation table of contents

Montreal, Quebec, Canada

Pages: 119 - 125

Year of Publication: 1995

ISBN:0-89791-699-9

Authors

Arne Storjohann	Department of Computer Science, University of Waterloo, Waterloo, Canada
George Labahn	Department of Computer Science, University of Waterloo, Waterloo, Canada

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation
SIGNUM: ACM Special Interest Group on Numerical Mathematics

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/220346.220362 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	E. H. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation, 22(103)'565-578, 1968.
	2	E. H. Bareiss. Computational solution of matrix problems over an integral domain. Phil. Trans. Roy. Soc. London, 10:68-104, 1972.
	3	P. D. Domich , R. Kannan , L. E. Trotter, Jr., Hermite normal form computation using modulo determinant arithmetic, Mathematics of Operations Research, v.12 n.1, p.50-59, Feb. 1987 [doi>10.1287/moor.12.1.50]
	4	David James Ford, On the computation of the maximal order in a dedekind domain., 1978
	5	Keith O. Geddes , Stephen R. Czapor , George Labahn, Algorithms for computer algebra, Kluwer Academic Publishers, Norwell, MA, 1992
	6	Mark Giesbrecht, Fast algorithms for rational forms of integer matrices, Proceedings of the international symposium on Symbolic and algebraic computation, p.305-311, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190432]
	7	James L. Hafner , Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM Journal on Computing, v.20 n.6, p.1068-1083, Dec. 1991 [doi>10.1137/0220067]
	8	C. Hermite. Sur l'introduction des variables continues dans la thdorie des hombres. J. Reine Angew. Math., 41:191-216, 1851.
	9	Costas S. Iliopoulos, Worst-case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and the Hermite and Smith normal forms of an integer matrix, SIAM Journal on Computing, v.18 n.4, p.658-669, Aug. 1989 [doi>10.1137/0218045]
	10	Thomas Kailath. Linear Systems. Prentice Hall, Englewood Cliffs, N.J., 1980.
	11	E. Kaltofen , M. S. Krishnamoorthy , B. D. Saunders, Fast parallel computation of hermite and smith forms of polynomial matrices, SIAM Journal on Algebraic and Discrete Methods, v.8 n.4, p.683-690, Oct. 1987 [doi>10.1137/0608057]
	12	Erich Kaltofen, M. S. Krishnamoorthy, and B. David Saunders. Parallel algorithms for matrix normal forms. Linear Algebra and its Applications, 136:189-208, 1990.
	13	R. Kannan. Polynomial-time algorithms for solving systems of linear equations over polynomials. Theoretical Computer Science, 39:69-88, 1985.
	14	S.E. Labhalla, H. Lombardi, and R. Marlin. Algorithmes de calcul de la r~duction d'Hermite d'une matrice ~ coefficients polynomiaux. In Comptes-Rendus de MEGA92, Nice, France. Birkhauser, 1992.
	15	M. Newman. Integral Matrices. Academic Press, !972.
	16	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	17	Arne Storjohann. Computation of Hermite and Smith normal forms of matrices. Master's thesis, Dept. of Computer Science, University of Waterloo, 1994.
	18	Barry Trager. Integration of Algebraic Functions. FhD thesis, Dept. of EECS, M.I.T., 1984.

CITED BY 4

	Arne Storjohann , George Labahn, Asymptotically fast computation of Hermite normal forms of integer matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.259-266, July 24-26, 1996, Zurich, Switzerland
	Arne Storjohann, High-order lifting, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.246-254, July 07-10, 2002, Lille, France
	Arne Storjohann, High-order lifting and integrality certification, Journal of Symbolic Computation, v.36 n.3-4, p.613-648, September 2003
	Arne Storjohann, A solution to the extended GCD problem with applications, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.109-116, July 21-23, 1997, Kihei, Maui, Hawaii, United States