A block algorithm of Lanczos type for solving sparse systems of linear equations
Mikhail Alekseevich Cherepnev · Discrete Mathematics and Applications · 2008
We suggest a new block algorithm for solving sparse systems of linear equations over GF (2) of the form where A is a symmetric matrix, F = GF (2) is a field with two elements. The algorithm is constructed with the use of matrix Padé approximations. The running time of the algorithm with the use of parallel calculations is max{ O ( dN 2 / n ), O ( N 2 )}, 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.