Решение разреженной системы над GF(q)

Question

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

У меня есть Linbox, который должен иметь такие методы, но я не смог заставить работать там решатель BlockLanczos, и в одном отчете говорится, что он был сломан с 2003 года. SparseElimination метод работает, но кажется, что это не будет работать хорошо для больших n из-за заполнения матрицы.

Итак, что доступно, что работает для таких проблем?

Answer 1

Юлия поддерживает конечные поля. Мой профессор коротко рассказал о своем. Он находится на линии 37. Декомпиляция LU и другие команды встроены и получены из типа GF.