Efficient parallel solution of sparse systems of linear diophantine equations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient parallel solution of sparse systems of linear diophantine equations

Full text

Pdf (1.38 MB)

Source

International Symposium on Parallel Symbolic Computation archive
Proceedings of the second international symposium on Parallel symbolic computation table of contents

Maui, Hawaii, United States

Pages: 1 - 10

Year of Publication: 1997

ISBN:0-89791-951-3

Author

Mark Giesbrecht

Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada, R3T 2N2

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): 1, Downloads (12 Months): 21, 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/266670.266678 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	Eric Bach , Jeffrey Shallit, Algorithmic number theory, MIT Press, Cambridge, MA, 1996
	2	E. R. Berlekamp. Factoring polynomials over large finite fields. Math. Comp. 24, pp. 713-735, 1970.
	3	W. A. Blankinship, Algorithm 288: solution of simultaneous linear Diophantine equations [F4], Communications of the ACM, v.9 n.7, p.514, July 1966 [doi>10.1145/365719.365971]
	4	I. Borosh and A. S. Fraenkel. Exact solutions of linear equations with rational coefficients by congruence techniques. Mathematics of Computation 20, pp. 107-112, 1966.
	5	G. Bradley. Algorithms for Hermite and Smith normal matrices and linear diophantine equations. Math. Comp 25(116), pp. 897-907, 1971.
	6	j.W.S. Cassels. Local Fields, vol. 3 of London Mathematical Society Student Texts. Cambridge University Press, 1986.
	7	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.
	8	Henri Cohen, A course in computational algebraic number theory, Springer-Verlag New York, Inc., New York, NY, 1995
	9	George E. Collins , Mark J. Encarnación, Efficient rational number reconstruction, Journal of Symbolic Computation, v.20 n.3, p.287-297, Sept. 1995 [doi>10.1006/jsco.1995.1051]
	10	Don Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Mathematics of Computation, v.62 n.205, p.333-350, Jan. 1994 [doi>10.2307/2153413]
	11	F. R. Gantmacher. The Theory of Matrices, Vol. I. Chelsea Publishing Co. (New York NY), 1990.
	12	P. Gibbons. Computational methods in design theory. In The CRC Handbook of Combinatorial Designs, ed. C. Colbourn and J. Dinitz, pp. 725-728. CRC Press, 1996.
	13	Mark Giesbrecht, Nearly Optimal Algorithms For Canonical Matrix Forms, SIAM Journal on Computing, v.24 n.5, p.948-969, Oct. 1995 [doi>10.1137/S0097539793252687]
	14	Mark Giesbrecht, Fast computation of the Smith form of a sparse integer matrix, Computational Complexity, v.10 n.1, p.41-69, 2001 [doi>10.1007/PL00001611]
	15	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.
	16	G. Havas and B.S. Majewski. Hermite normal form computation for integer matrices. Congressus Numerantium 105, pp. 184-193, 1994.
	17	G. Havas, D. Holt, and S. Rees. Recognizing badly presented Z-modules. Linear algebra and its applications 192, pp. 137-163, 1993.
	18	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]
	19	T. Kallath. Linear systems. Prentice-Hall (Englewood Cliffs, New Jersey), 1980.
	20	Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
	21	Erich Kaltofen , B. David Saunders, On Wiedemann's Method of Solving Sparse Linear Systems, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.29-38, October 07-11, 1991
	22	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.
	23	S. Lang. Algebraic Number Theory. Springer-Verlag (New York), 1986.
	24	R. Lidl and H. Niederreiter. Finite Fields, vol. 20 of Encyclopedia of Mathematics and its Applications. Addison- Wesley (Reading MA), 1983.
	25	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]
	26	M. Newman. Integral Matrices. Academic Press (New York), 1972.
	27	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]
	28	A. Storjohann. A fast practical deterministic algorithm for triangularizing integer matrices. Unpublished manuscript, 1996.
	29	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 [doi>10.1145/236869.237083]
	30	G. Villard, Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract), Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.32-39, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258742]
	31	Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982 [doi>10.1145/1089292.1089293]
	32	D H Wiedemann, Solving sparse linear equations over finite fields, IEEE Transactions on Information Theory, v.32 n.1, p.54-62, Jan. 1986 [doi>10.1109/TIT.1986.1057137]
	33	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

CITED BY 8

	Thom Mulders , Arne Storjohann, Diophantine linear system solving, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.181-188, July 28-31, 1999, Vancouver, British Columbia, Canada
	M. Giesbrecht , A. Lobo , B. D. Saunders, Certifying inconsistency of sparse linear systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.113-119, August 13-15, 1998, Rostock, Germany
	Jean-Guillaume Dumas , B. David Saunders , Gilles Villard, Integer Smith form via the valence: experience with large sparse matrices from homology, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.95-105, July 2000, St. Andrews, Scotland
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Zhuliang Chen , Arne Storjohann, A BLAS based C library for exact linear algebra on integer matrices, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.92-99, July 24-27, 2005, Beijing, China
	Wayne Eberly , Mark Giesbrecht , Pascal Giorgi , Arne Storjohann , Gilles Villard, Solving sparse rational linear systems, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Wayne Eberly , Mark Giesbrecht , Pascal Giorgi , Arne Storjohann , Gilles Villard, Faster inversion and other black box matrix computations using efficient block projections, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Gilles Villard, Some recent progress in exact linear algebra and related questions, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada