|
This article is cited in 5 scientific papers (total in 5 papers)
A block algorithm of Lanczos type for solving sparse systems of linear equations
M. A. Cherepnev
Abstract:
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<Cn$ for some absolute constant $C$, then this estimate is better than the estimate of the running time of the well-known Montgomery algorithm.
Received: 18.04.2007
Citation:
M. A. Cherepnev, “A block algorithm of Lanczos type for solving sparse systems of linear equations”, Diskr. Mat., 20:1 (2008), 145–150; Discrete Math. Appl., 18:1 (2008), 79–84
Linking options:
https://www.mathnet.ru/eng/dm997https://doi.org/10.4213/dm997 https://www.mathnet.ru/eng/dm/v20/i1/p145
|
Statistics & downloads: |
Abstract page: | 1243 | Full-text PDF : | 464 | References: | 99 | First page: | 22 |
|