linear-algebra - 在 GF(q) 上求解稀疏系统

Question

我有兴趣解决大型(n 最多 10^5 甚至 10^6)矩形(列比行多 10%)稀疏(每行 < 10 个非零值)系统 Ax = b在有限域上GF(q) ( q 可能是接近 1000 左右的质数)。从文献中看，块 Lanczos 方法可能是最合适的。

我有应该有这样的方法的 Linbox，但一直无法让 BlockLanczos 求解器在那里工作，并且 one report说这从 2003 年开始就被打破了。SparseElimination方法确实有效，但对于大型 n 似乎这不起作用因为矩阵的填充。

那么，有什么可以解决此类问题的呢？

Answer 1

Julia 支持有限域。我的教授有一个简短的 how to on his.它在第 37 行。 LU decomp 和其他命令是内置的并从 GF 类型派生而来。