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

M. A. Cherepnev

Diskretnaya Matematika, Tome 20 (2008) no. 1, pp. 145-150

Résumé

We suggest a new block algorithm for solving sparse systems of linear equations over $GF(2)$ of the form $Ax=b$, $A\in F(N\times N)$, $b\in F(N\times1)$, 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$ for some absolute constant $C$, then this estimate is better than the estimate of the running time of the well-known Montgomery algorithm.