About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Linear Algebra and Its Applications
Paper
Solving linear equations over GF(2): block Lanczos algorithm
Abstract
We propose a method of solving large sparse systems of linear equations over GF(2), the field with two elements. We use the Lanczos algorithm, modified in two ways. A lookahead Lanczos algorithm is needed for the problem of dividing by an inner product whose value happens to be 0. A block version of the algorithm allows us to perform 32 matrix-vector operations for the cost of one. The resulting algorithm is competitive with structured Gaussian elimination in terms of time, and has much lower space requirements. It may be useful in the last stage of integer factorization. © 1993.