СЛУ над GF(2)

[vlad_light]

Пусть $\mathbf A\in \mathrm{Mat}_{n\times n}(GF(2))$ невырождена и имеет порядка $O(n)$ ненулевых элементов. Нужно быстренько решить уравнение $\mathbf A \mathbf x = \mathbf b$.
Я пока нашел такую штуку:
1. Ищем строку с наименьшим кол-вом единиц ($i$);
2. Ищем в ней столбец, на котором стоит единица ($j$);
3. Вычеркиваем столбец $j$;
3а. Если это была единственная единица в строке -- записываем в начало "таблицы столбцов" номер столбца $j$, а в начало "таблицы строк" номер строки $i$;
3б. Иначе, записываем в конец "таблицы столбцов" номер столбца $j$;
4. Повторяем до тех пор, пока не вычеркнем все столбцы;
5. Дописываем в "таблицу строк" номера непомеченных строк;
В итоге должно получиться две таблицы вида:

$$ \begin{tabular}{c c c c c} \# & 1 & 2 & \cdots & n\\ i & i_1 & i_2 & \cdots & j_n \end{tabular} \quad \begin{tabular}{c c c c c} \# & 1 & 2 & \cdots & n\\ j & j_1 & j_2 & \cdots & j_n \end{tabular} $$

Переставляя строки и столбцы исходной матрицы согласно таблицам, мы приведём её к виду:

$$ \begin{pmatrix} \mathbf L & \mathbf L_1 \\ \mathbf D & \mathbf D_1 \end{pmatrix} \Rightarrow \begin{pmatrix} \mathbf I & \mathbf L_1 \\ \mathbf 0 & \mathbf D_1 \end{pmatrix} \Rightarrow \cdots $$

где $\mathbf L$ -- нижнетреугольная квадратная матрица, $\mathbf L_1$ -- нижнетреугольная прямоугольная матрица, $\mathbf D, \mathbf D_1$ -- плотные матрицы. Далее предлагают действовать методом Гаусса.
Подскажите, пожалуйста, что-нибудь на этот счёт.
Заранее благодарен!