Fast computation of the Smith normal form of an integer matrix

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast computation of the Smith normal form of an integer matrix

Full text

Pdf (994 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: 110 - 118

Year of Publication: 1995

ISBN:0-89791-699-9

Author

Mark Giesbrecht

Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada, R3T 3T6

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): 5, Downloads (12 Months): 24, 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/220346.220361 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	E. R. Berlekamp. Factoring polynomials over large finite fields. Math. Comp. 24, pp. 713-735, 1970.
	3	J. Buchmann. A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. In Sdminaire de thdorie des hombres, Paris, 1988.
	4	T. J. Chou and G. E. Collins. Algorithms for the solution of systems of linear Diophantine equations. SIAM J. of Computing 11, pp. 687-708, 1982.
	5	Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
	6	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]
	7	F. R. Gantmacher. The Theory of Matrices, Vol. L Chelsea Publishing Co. (New York NY), 1990.
	8	Mark William Giesbrecht, Nearly optimal algorithms for canonical matrix forms, University of Toronto, Toronto, Ont., Canada, 1993
	9	G. Golub and C. Van Loan. Matrix Computations. Johns Hopkins University Press (Baltimore, USA), 1983.
	10	J. L. Hafner and K. S. McCurley. A rigorous subexponential algorithm for computation of class groups. J. Amer. Math. Soc. 2, pp. 837-850, 1989.
	11	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]
	12	O. Ibarra, S. Moran, and R. Hui. A generalization of the fast LUP matrix decomposition algorithm and applica.- tion. J. of Algorithms 3, pp. 45-56, 1982.
	13	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]
	14	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]
	15	R. Kannan and A. Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comp. 8, pp. 499-507, 1979.
	16	R. Lidl and H. Niederreiter. Finite Fields, vol. 20 of Encyclopedia of Mathematics and its Applications. Addison- Wesley (Reading MA), 1983.
	17	M. Newman. Integral Matrices. Academic Press (New York), 1972.
	18	J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Ill. J. Math. 6, pp. 64-94, 1962.
	19	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]
	20	H..}. S. Smith. On systems of linear indeterminate equations and congruences. Philos. Trans. Royal Soc. London 151, pp. 293-326, 1861.

CITED BY 8

	Xin Gui Fang , George Havas, On the worst-case complexity of integer Gaussian elimination, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.28-31, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Arne Storjohann, Near optimal algorithms for computing Smith normal forms of integer matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.267-274, July 24-26, 1996, Zurich, Switzerland
	Thom Mulders , Arne Storjohann, The modulo N extended GCD problem for polynomials, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.105-112, August 13-15, 1998, Rostock, Germany
	Frank Lübeck, On the computation of elementary divisors of integer matrices, Journal of Symbolic Computation, v.33 n.1, p.57-65, 01/01/2002
	Eric Allender , Robert Beals , Mitsunori Ogihara, The complexity of matrix rank and feasible systems of linear equations (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.161-167, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 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
	Gerold Jäger , Clemens Wagner, Efficient parallelizations of Hermite and Smith normal form algorithms, Parallel Computing, v.35 n.6, p.345-357, June, 2009