A solution to the extended GCD problem with applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A solution to the extended GCD problem with applications

Full text

Pdf (1.16 MB)

Source

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

Kihei, Maui, Hawaii, United States

Pages: 109 - 116

Year of Publication: 1997

ISBN:0-89791-875-4

Author

Arne Storjohann

Eidgenössische Technische Hochschule, CH-8092 Zürich, Switzerland

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): 14, Citation Count: 2

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/258726.258762 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	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]
	2	FORD, D., AND HAVAS, G. A new algorithm and refined bounds for extended gcd computation. Tech. Rep. 354, The University of Queensland, 1995. Suhmitted.
	3	Mark Giesbrecht, Fast computation of the Smith normal form of an integer matrix, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.110-118, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220361]
	4	Mark Giesbrecht, Probabilistic Computation of the Smith Normal Form of a Sparse Integer Matrix, Proceedings of the Second International Symposium on Algorithmic Number Theory, p.173-186, May 18-23, 1996
	5	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]
	6	HAVAS, G., AND MAJEWSKI, B. S. Diagonalization of integer matrices. To appear in Journal of Symbolic Computation.
	7	HAVAS, G., AND MAJEWSKI, B. S. Hermite normal form computation for integer matrices. Congressua Numerantium 105 (1994), 87-96.
	8	George Havas , Bohdan S. Majewski, A Hard Problem That is Almost Always Easy, Proceedings of the 6th International Symposium on Algorithms and Computation, p.216-223, December 04-06, 1995
	9	HAVAS, G., MAJEWSKI, B. S., AND MATTHEWS, K. R. Extended gcd algorithms. Tech. Rep. 302, The University of Queensland, 1995. Submitted.
	10	HOWELL, J. A. Spans in the module (Z,n)*. Linear and Multilinear Algebra 19 (1986), 67--77.
	11	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]
	12	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]
	13	KALTO~EN, E., KamHNAMOORTnY, M. S., AND SAUN- OERS, B. D. Parallel algorithms for matrix normal forms. Linear Algebra and its Applications 136 (1990), 189-208.
	14	KANOLD, H.-J. 0ber eine zahlentheoretische Function von E. Jacobsthal. Abh. Braunschwieg. Wiss. Gesellsch. 25 (1975), 7-10.
	15	Bohdan S. Majewski , George Havas, The complexity of greatest common divisor computations, Proceedings of the First International Symposium on Algorithmic Number Theory, p.184-193, May 06-09, 1994
	16	Bohdan S. Majewski , George Havas, A solution to the extended gcd problem, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.248-253, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220377]
	17	SCHONHAGE, A., AND STRASSEN, V. Schnelle Multiplikation grosser Zahlen. Computing 7 (1971), 281-292.
	18	SMITH, H. J. S. On systems of linear indeterminate equations and congruences. Phil. Trans. Roy. Soc. London 151 (1861), 293-326.
	19	STORJOHANN, A. Computing Hermite and Smith norreal forms of triangular integer matrices. Tech. Rep. 256, Departement Informatik, ETH Ziirich, Dec. 1996.
	20	STORJOrlANN, A. A fast+practical+deterministic algorithm for triangularizing integer matrices. Tech. Rep. 255, Departement Informatik~ ETH Ziirich, Dec. 1996.
	21	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 [doi>10.1145/236869.237084]
	22	Arne Storjohann , George Labahn, Preconditioning of rectangular polynomial matrices for efficient Hermite normal form computation, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.119-125, July 10-12, 1995, Montreal, Quebec, Canada [doi>10.1145/220346.220362]
	23	STOP.JOHANN, A., AND LABAHN, G. A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix. Linear Algebra and its Applications 253 (1997), 155--173.
	24	Gilles Villard, Generalized subresultants for computing the Smith normal form of polynomial matrices, Journal of Symbolic Computation, v.20 n.3, p.269-286, Sept. 1995 [doi>10.1006/jsco.1995.1050]

CITED BY 2

	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