A block algorithm of Lanczos type for solving sparse systems of linear equations

摘要

We suggest a new block algorithm for solving sparse systems of linear equations over GF(2) of the formAx =b, Ae F(N x N), be F(N x 1),where A is a symmetric matrix, F = GF(2) is a field with two elements. The algorithm is constructed with the use of matrix Pade approximations The running time of the algorithm with the use of parallel calculations is m&x.{O(dN2), O(N2)}, where d is the maximal number of nonzero elements over all rows of the matrix A, If d < Cn for some absolute constant C, then this estimate is better than the estimate of the running time of the well-known Montgomery algorithm.