Блочный алгоритм типа Ланцоша решения разреженных систем линейных уравнений

В статье предлагается новый блочный алгоритм решения разреженных систем линейных уравнений над $GF(2)$ вида $Ax=b$, $A\in F(N\times N)$, $b\in F(N\times1)$, где $A$ – симметричная матрица, $F=GF(2)$ – поле из двух элементов. Алгоритм построен с использованием матричных аппроксимаций Паде. Время работы алгоритма при параллельной организации вычислений оценивается величиной $\max\{O(dN^2/n), O(N^2)\}$, где $d$ – максимальное по строкам матрицы $A$ число ненулевых элементов. Если $d<Cn$ для некоторой абсолютной константы $C$, то эта оценка лучше оценки времени работы известного алгоритма Монтгомери.