Я заинтересован в решении больших (n до 10 ^ 5 или, может быть, даже 10 ^ 6) прямоугольных (возможно, на 10% больше столбцов, чем строк) разреженных (‹ 10 ненулевых элементов в строке) систем Ax = b над конечным полем GF(q) (q может быть премьер около 1000 или около того). Из литературы следует, что блочные методы Ланцоша могут быть наиболее подходящими.
У меня есть Linbox, который должен иметь такие методы, но мне не удалось заставить там работать решатель BlockLanczos, и в одном отчете говорится, что это было нарушено с 2003 года. Метод SparseElimination действительно работает, но кажется, что он не будет работать для больших n из-за заполнения матрицы.
Итак, что доступно для решения таких проблем?
