Solving sparse linear equations over finite fields

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Solving sparse linear equations over finite fields

Source

IEEE Transactions on Information Theory archive
Volume 32 , Issue 1 (January 1986) table of contents

Pages: 54 - 62

Year of Publication: 1986

ISSN:0018-9448

Author

D H Wiedemann

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 56

Additional Information:

cited by index terms

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	10.1109/TIT.1986.1057137

CITED BY 56

	Emmanuel Thomé, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Journal of Symbolic Computation, v.33 n.5, p.757-775, May 2002
	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
	Wayne Eberly, Processor-efficient parallel matrix inversion over abstract fields: two extensions, Proceedings of the second international symposium on Parallel symbolic computation, p.38-45, July 20-22, 1997, Maui, Hawaii, United States
	E. Kaltofen , A. Lobo, On rank properties of Toeplitz matrices over finite fields, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.241-249, July 24-26, 1996, Zurich, Switzerland
	Erich Kaltofen, On computing determinants of matrices without divisions, Papers from the international symposium on Symbolic and algebraic computation, p.342-349, July 27-29, 1992, Berkeley, California, United States
	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
	Victor Shoup, Efficient computation of minimal polynomials in algebraic extensions of finite fields, Proceedings of the 1999 international symposium on Symbolic and algebraic computation, p.53-58, July 28-31, 1999, Vancouver, British Columbia, Canada
	Igor A. Semaev, Special prime numbers and discrete logs in finite prime fields, Mathematics of Computation, v.71 n.237, p.363-377, January 2002
	J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States
	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
	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
	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
	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
	Ioannis Z. Emiris , Victor Y. Pan, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, Journal of Symbolic Computation, v.33 n.4, p.393-413, April 2002
	Wayne Eberly, Black box Frobenius decompositions over small fields, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.106-113, July 2000, St. Andrews, Scotland
	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
	Ioanis Z. Emiris , Victor Y. Pan, The structure of sparse resultant matrices, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.189-196, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Victor Y. Pan , Zhao Q. Chen, The complexity of the matrix eigenproblem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.507-516, May 01-04, 1999, Atlanta, Georgia, United States
	Emmanuel Thomé, Fast computation of linear generators for matrix sequences and application to the block Wiedemann algorithm, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.323-331, July 2001, London, Ontario, Canada
	Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland
	Erich Kaltofen , Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.398-406, May 29-June 01, 1995, Las Vegas, Nevada, United States
	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
	Wayne Eberly, Early termination over small fields, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.80-87, August 03-06, 2003, Philadelphia, PA, USA
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Erich Kaltofen , Wen-shin Lee, Early termination in sparse interpolation algorithms, Journal of Symbolic Computation, v.36 n.3-4, p.365-400, September 2003
	Peter Fleischmann , Markus Chr. Holder , Peter Roelse, The black-box Niederreiter algorithm and its implementation over the binary field, Mathematics of Computation, v.72 n.244, p.1887-1899, October 2003
	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
	Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States
	Erich Kaltofen , Austin Lobo, Factoring high-degree polynomials by the black box Berlekamp algorithm, Proceedings of the international symposium on Symbolic and algebraic computation, p.90-98, July 20-22, 1994, Oxford, United Kingdom
	Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003
	Wayne Eberly, Reliable Krylov-based algorithms for matrix null space and rank, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.127-134, July 04-07, 2004, Santander, Spain
	Thomas Wollinger , Jan Pelzl , Christof Paar, Cantor versus Harley: Optimization and Analysis of Explicit Formulae for Hyperelliptic Curve Cryptosystems, IEEE Transactions on Computers, v.54 n.7, p.861-872, July 2005
	Thomas Wollinger , Jan Pelzl , Volker Wittelsberger , Christof Paar , Gökay Saldamli , Çetin K. Koç, Elliptic and hyperelliptic curves on embedded μP, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.3, p.509-533, August 2004
	Marcel Dhiflaoui , Stefan Funke , Carsten Kwappik , Kurt Mehlhorn , Michael Seel , Elmar Schömer , Ralph Schulte , Dennis Weber, Certifying and repairing solutions to large LPs how good are LP-solvers?, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Bradford Hovinen , Wayne Eberly, A reliable block Lanczos algorithm over small finite fields, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.177-184, July 24-27, 2005, Beijing, China
	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
	Jeffrey Adams , B. David Saunders , Zhendong Wan, Signature of symmetric rational matrices and the unitary dual of lie groups, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.13-20, July 24-27, 2005, Beijing, China
	William J. Turner, Preconditioners for singular black box matrices, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.332-339, July 24-27, 2005, Beijing, China
	Oliver Schirokauer, Virtual logarithms, Journal of Algorithms, v.57 n.2, p.140-147, November 2005
	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
	Alexandros G. Dimakis , Vinod Prabhakaran , Kannan Ramchandran, Decentralized erasure codes for distributed networked storage, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2809-2816, June 2006
	William J. Turner, A block Wiedemann rank algorithm, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Hoon Hong , Erich Kaltofen , Michael Singer, East Coast Computer Algebra Day '99 (April 24, 1999): abstracts of invited talks and presented posters, ACM SIGSAM Bulletin, v.33 n.2, p.43-52, June 1999
	Andrew Odlyzko, Discrete Logarithms: The Past and the Future, Designs, Codes and Cryptography, v.19 n.2-3, p.129-145, March 2000
	A. K. Lenstra , H. W. Lenstra, Jr. , M. S. Manasse , J. M. Pollard, The number field sieve, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.564-572, May 13-17, 1990, Baltimore, Maryland, United States
	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
	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
	John P. May , B. David Saunders , David Harlan Wood, Numerical techniques for computing the inertia of products of matrices of rational numbers, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	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
	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
	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
	Chin-Chen Chang , Shih-Chang Chang, The design of e-traveler's check with efficiency and mutual authentication, Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, January 15-16, 2009, Suwon, Korea
	Victor Y. Pan , Brian Murphy , Rhys E. Rosholt, Nearly optimal symbolic-numerical algorithms for structured integer matrices and polynomials, Proceedings of the 2009 conference on Symbolic numeric computation, August 03-05, 2009, Kyoto, Japan
	Jean-Guillaume Dumas , Clément Pernet , B. David Saunders, On finding multiplicities of characteristic polynomial factors of black-box matrices, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea
	B. David Saunders , Bryan S. Youse, Large matrix, small rank, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea