Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Further analysis of Coppersmith's block Wiedemann algorithm for the solution of sparse linear systems (extended abstract)

Full text

Pdf (1.17 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: 32 - 39

Year of Publication: 1997

ISBN:0-89791-875-4

Author

G. Villard

LMC-IMAG, B.P. 53, F-38041 Grenoble cedex 9

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): 10, Downloads (12 Months): 43, Citation Count: 17

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.258742 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	Bernhard Beckermann , George Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Pade Approximants, SIAM Journal on Matrix Analysis and Applications, v.15 n.3, p.804-823, July 1994 [doi>10.1137/S0895479892230031]
	2	BECKERMANN, B., AND LABAHN, G. Recursiveness in matrix rational interpolation problems. Tech. Rep. Publication ANO 357, {lniversitd de Lille France, 1996.
	3	BUI,THEEL, A., AND VAN BAr(EL, M. A matrix Euclidean algorithm and the matrix minimal Padd approximation problem. In Continued bYactions and Padd Approximants (1990), C. Brezinski, Ed., North-Holland, pp. 11--51.
	4	(;OPPEL, W Matrices of rational functions. Bull. Austral. Math. Soc. I1 (1974), 89--113.
	5	COPPERSMITtt, D. Solving linear equations over GF(2): block Lanczos algorithm. Linear Algebra and its Applications 192 (1993), 33-60.
	6	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]
	7	DELSARTE, P., GENIN, Y., AND KAMP, Y. A generalization of the Levinson algorithm for Hermitian Toeplitz matrices with any rank profile. IEEE Internat. Conf. Acoust. Speech Signal Process. 33 (1985), 964-971.
	8	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]
	9	FORNEY, G Minimal bases of rational vector spaces, with applications to multivariable linear systems. SIAM J. Control I3 (1975), 493-520.
	10	GANTMACHER, F. Th~orie des matrices. Dunod, Paris, France, 1966.
	11	JACOBSON, N. Lectures in Abstract Algebra II, Linear Algebra. Springer-Verlag, 1953.
	12	JACOBSON, N Basic Algebra I. W.H. Freeman and Company, 1974.
	13	KAILATIt, T. Linear systems. Prentice Hall, 1980.
	14	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]
	15	KALTOFEN, E., AND LOBO, i. Distributed matrix-free solution of large sparse linear systems over finite fields. In High Performance Computing 1996, San Diego, CA (1996), A. Tentner, Ed., Society for Computer Simulation, Simulation Councils, Inc, pp. 244--247.
	16	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 [doi>10.1145/113379.113396]
	17	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
	18	Brian A. LaMacchia , Andrew M. Odlyzko, Solving Large Sparse Linear Systems over Finite Fields, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.109-133, August 11-15, 1990
	19	Robert John Lambert , Ian F. Blake, Computational aspects of discrete logarithms, 1996
	20	LENSTRA, A., LENSTRA, H., MANASSE, M., AND POLLARD, j. The factorization of the ninth Fermat number. Math. Comp. 61 (1993), 319-349.
	21	Austin Anthony Lobo, Matrix-free linear system solving and applications to symbolic computation, Rensselaer Polytechnic Institute, Troy, NY, 1996
	22	MACDUFFEE, C. The theory of matrices. Chelsea, New-York, 1956.
	23	MASS~Y, J. Shift-register synthesis and BCH decoding. IEEE Trans. Inform. Theory ! 5 (1969), 122-127.
	24	MONT(3OMZR~, P. A block Lanczos algorithm for finding dependencies over GF(2). In EUROCRYPT'95, Heidelberg, Germany. Springer LNCS 921 (1995), pp. 106-120.
	25	PENFIELD jR., P., SPENCER, R., AND DUINKER, S. Tellegen's theorem and electrical networks. M.I.T. Press, Cambridge, MA, 1970.
	26	PoPov, V. Invariant description of linear, time-invariant controllable systems. SIAM J. Control 10 (May 1972), 252- 264.
	27	VAN BAREL, M., AND BULTHEEL, A. A general module theoretic framework for vector M-Padd and matrix rational interpolation. Numerical Algorithms 3 (1992), 451-462.
	28	VERCr~ESE, G., AND KAILATH. Rational matrix structure. IEEE Trans. Automat. Control 26 (1981), 434-438.
	29	G. Villard, Computing Popov and Hermite forms of polynomial matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.250-258, July 24-26, 1996, Zurich, Switzerland [doi>10.1145/236869.237082]
	30	VZLLARD, G. A study of Coppersmith's block Wiedemann algorithm using matrix polynomials, Feb. 1997. RR IMAG Grenoble, France.
	31	VJLLARD, G. Computing minimum generating matrix polynomials, 1997. Preprint IMAG Grenoble, Prance.
	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	WIMMER, H. A Jordan factorization for polynomial matrices. Proceedings of the American Math. Soc. 75, 2 (1979), 201- 206.
	34	WOLOVtCrl, W. Linear multivariable systems. Springer- Verlag, New-York, 1974.

CITED BY 17

	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
	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
	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
	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
	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
	Pascal Giorgi , Claude-Pierre Jeannerod , Gilles Villard, On the complexity of polynomial matrix computations, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.135-142, August 03-06, 2003, Philadelphia, PA, USA
	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
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 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
	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
	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
	Arne Storjohann , Gilles Villard, Computing the rank and a small nullspace basis of a polynomial matrix, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.309-316, July 24-27, 2005, Beijing, China
	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
	Andrew Odlyzko, Discrete Logarithms: The Past and the Future, Designs, Codes and Cryptography, v.19 n.2-3, p.129-145, March 2000
	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