Certifying inconsistency of sparse linear systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Certifying inconsistency of sparse linear systems

Full text

Pdf (305 KB)

Source

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

Rostock, Germany

Pages: 113 - 119

Year of Publication: 1998

ISBN:1-58113-002-3

Authors

M. Giesbrecht	Dept. of Computer Science, University of Manitoba, Winnipeg, Manitoba, R3T 2N2, Canada
A. Lobo	Dept. of Mathematics and Computer Science, Washington College, 300 Washington Ave., Chestertown, MD
B. D. Saunders	Dept. of Computer and Information Sciences, University of Delaware, Newark, DE

Sponsors

German Comp Soc : GI - Gesellshaft for Informatik
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): 15, Citation Count: 9

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/281508.281591 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	D. Coppersmith. Solving linear equations over GF(2); block Lanczos algorithm. Linear algebra and its applications 192F pp. 333-350F 1993.
	2	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]
	3	Wayne Eberly , Erich Kaltofen, On randomized Lanczos algorithms, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.176-183, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258776]
	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	Mark Giesbrecht, Efficient parallel solution of sparse systems of linear diophantine equations, Proceedings of the second international symposium on Parallel symbolic computation, p.1-10, July 20-22, 1997, Maui, Hawaii, United States [doi>10.1145/266670.266678]
	6	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]
	7	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
	8	Robert John Lambert , Ian F. Blake, Computational aspects of discrete logarithms, 1996
	9	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]
	10	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]
	11	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]
	12	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 9

	Laurent Bernardin , Bruce Char , Erich Kaltofen, Symbolic computation in Java: an appraisement, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.237-244, July 28-31, 1999, Vancouver, British Columbia, Canada
	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
	Thom Mulders , Arne Storjohann, Rational solutions of singular linear systems, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.242-249, 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
	B. D. Saunders, Black box methods for least squares problems, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.297-302, July 2001, London, Ontario, Canada
	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
	John P. May , David Saunders , Zhendong Wan, Efficient matrix rank computation with application to the study of strongly regular graphs, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Jing Xiao , Lan Liu , Lirong Xia , Tao Jiang, Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.655-664, January 07-09, 2007, New Orleans, Louisiana
	Arne Storjohann, Integer matrix rank certification, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea