Fast deterministic computation of determinants of dense matrices

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast deterministic computation of determinants of dense matrices

Full text

Pdf (907 KB)

Source

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

Vancouver, British Columbia, Canada

Pages: 197 - 204

Year of Publication: 1999

ISBN:1-58113-073-2

Authors

John Abbott	Dipartimento di Matematica, Università di Geneva, Italy
Manuel Bronstein	INRIA - Projet CAFÉ, Sophia-Antipolis, France
Thom Mulders	Institute of Scientific Computing, ETH Zurich, 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): 4, Downloads (12 Months): 26, Citation Count: 11

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/309831.309934 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	BAREISS, E. Computational sohltions of' matrix problems over an integral domain. J. Inst. Maths Applies 10 (1972), 68--104.
	2	Leo Breiman, Probability, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
	3	Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Computing exact geometric predicates using modular arithmetic with single precision, Proceedings of the thirteenth annual symposium on Computational geometry, p.174-182, June 04-06, 1997, Nice, France [doi>10.1145/262839.262948]
	4	C, APANI. A.. NIESI, G., AND ~,OBBIANO, L. CoCoA" Computations in commutative algebra, http'//cocoa. dima. unige, it/.
	5	C, LARKSO.\', K. Safe and effe(:tive determinant evaluation. In Proc. 33rd Ann. IEEE Syrup. Foundations of Comp. Science (1992), pp. 387-395.
	6	DixoN, J. Exact solution of linear equations using padic expansions. Numer. Math. 40 (1982), 137-141.
	7	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]
	8	FItUMKIN, M. Polynomial time algorithms in tile theory of linear diophantine equations. LNCS 56 (1977), 386- 392.
	9	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]
	10	HOKN, R.. AND JOItNSON, C. Matrix Analysis. Cambridge University Press, 1985.
	11	HOWELL, J. Spans in the inodule (Z,~)~. Linear and Mv ltilinear Algebra 19 (1986), 67-77.
	12	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 [doi>10.1145/309831.309905]
	13	N I~WMAN, M. Integral Matrices. Academic Press, 1972.
	14	Victor Pan, Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations, Information Processing Letters, v.28 n.2, p.71-75, June 24, 1988 [doi>10.1016/0020-0190(88)90166-4]
	15	SHouP, V. NTL' A library ibr doing number theory. http"//www, cs. wisc. edu/~shoup/ntl.
	16	Arne Storjohann , Thom Mulders, Fast Algorithms for for Linear Algebra Modulo N, Proceedings of the 6th Annual European Symposium on Algorithms, p.139-150, August 24-26, 1998

CITED BY 11

	Sergei A. Abramov , Manuel Bronstein, On solutions of linear functional systems, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.1-6, July 2001, London, Ontario, Canada
	Victor Y. Pan , Xinmao Wang, Acceleration of Euclidean algorithm and extensions, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.207-213, July 07-10, 2002, Lille, France
	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
	Erich Kaltofen, An output-sensitive variant of the baby steps/giant steps determinant algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.138-144, July 07-10, 2002, Lille, France
	David Saunders , Zhendong Wan, Smith normal form of dense integer matrices fast algorithms into practice, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.274-281, July 04-07, 2004, Santander, Spain
	Erich Kaltofen , Gilles Villard, Computing the sign or the value of the determinant of an integer matrix, a complexity survey, Journal of Computational and Applied Mathematics, v.162 n.1, p.133-146, 1 January 2004
	Ioannis Z. Emiris , Victor Y. Pan, Improved algorithms for computing determinants and resultants, Journal of Complexity, v.21 n.1, p.43-71, February 2005
	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
	Arne Storjohann, The shifted number system for fast linear algebra on integer matrices, Journal of Complexity, v.21 n.4, p.609-650, August 2005
	Jung Hee Cheon , Woo-Hwan Kim , Hyun Soo Nam, Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme, Information Processing Letters, v.97 n.3, p.118-123, 14 February 2006
	Jean-Guillaume Dumas , Philippe Elbaz-Vincent , Pascal Giorgi , Anna Urbánska, Parallel computation of the rank of large sparse matrices from algebraic K-theory, Proceedings of the 2007 international workshop on Parallel symbolic computation, July 27-28, 2007, London, Ontario, Canada