11

I am interested in solving large (n up to 10^5 or maybe even 10^6) rectangular (maybe 10% more columns than rows) sparse (< 10 nonzeros per row) systems Ax = b over a finite field GF(q) (q might be a prime near 1000 or so). From the literature, it looks like block Lanczos methods might be the most appropriate.

I have Linbox which is supposed to have such methods, but have been unable to get the BlockLanczos solver there to work, and one report says that this has been broken since 2003. The SparseElimination method does work, but it seems that this will not work well for large n because of fill-in of the matrix.

So, what is available that does work for such problems?

b4hand
  • 9,550
  • 4
  • 44
  • 49
Robert Israel
  • 173
  • 6
  • I'm not an expert in numerical computing, but here is a more recent code: http://seldon.sourceforge.net/doc-5.0/file.php?name=computation/solver/iterative/Cgs.cxx It's not clear if hit handles finite fields. Iterative methods like Gauss-Jacobi are also useful for large systems. – Gene May 23 '14 at 17:56
  • You may have better luck getting an answer on http://mathoverflow.net or http://math.stackexchange.com . – dg99 May 23 '14 at 18:52
  • 1
    @Gene: Thanks. It seems Seldon is for numerical computations over real or complex numbers, not exact computations over finite fields. By "Gauss-Jacobi" do you mean Gauss-Siedel or Jacobi? It's not at all clear that these methods can be adapted to finite fields (although Lanczos and conjugate-gradient methods can). – Robert Israel May 23 '14 at 20:36
  • 1
    @dg99: Thanks. I found the linbox-use newsgroup, and got an answer there: https://groups.google.com/forum/#!topic/linbox-use/gSA4oT7M2nM – Robert Israel May 23 '14 at 20:39
  • Julia supports finite fields. https://github.com/Nemocas/AbstractAlgebra.jl/blob/master/docs/src/finfield.md, http://nemocas.github.io/Nemo.jl/latest/. There are quick ways to solve them that are implicitly derived. –  May 29 '18 at 23:52

1 Answers1

0

Julia supports finite fields. My professor had a short how to on his. It's on line 37. The LU decomp and other commands are built in and derived from the GF type.