1
$\begingroup$

Given $m=385$, I have a linear equation system over a field $\mathbb{F}_p$ with $p$ a small prime (could be 5,7,11, something like this) with the following properties:

  1. There are $m^2$ variables.
  2. Every variable appears in exactly 7 equation.
  3. Every equation contains at most 3 variables.
  4. The coefficient of the variables is always 1.
  5. The free term in the equations are always 0, with one specific equation (an equation of the form $3x=1$ for a specific variable $x$).

I am currently using SAGE. It solved nicely smaller equation systems, but this one killed it, even when constructing the matrix as sparse ("Error allocating matrix"). The question is - should I simply try a better (and less convenient) sparse matrix handling package, or is there a better way to deal with such sparse systems of equations? (I can do a little programming myself if needed).

$\endgroup$
1
  • $\begingroup$ You will get more comprehensive replies for such questions @ scicomp.stackexchange.com. $\endgroup$
    – Inquest
    Commented Feb 8, 2012 at 15:45

1 Answer 1

1
$\begingroup$

Since you have constant number of non-zero entries per row, your system is fit for iterative methods, namely in finite fields case: Wiedemann's algorithm. Check out LinBox library. As for convenience, AFAIK LinBox is included in SAGE.

$\endgroup$
3
  • $\begingroup$ Thank you! This seems very promising. $\endgroup$
    – Gadi A
    Commented Jan 9, 2012 at 16:17
  • $\begingroup$ It seems there are two problems here. First, the algorithm is for square matrices, and mine isn't; second, the algorithm is not supposed to work well in small finite fields, which is exactly the case I'm dealing with. $\endgroup$
    – Gadi A
    Commented Jan 10, 2012 at 9:56
  • $\begingroup$ (1) Squarizer can handle rectangular matrices (2) IIRC LinBox supports small finite field through the field type <Modular>. To find out more, you should post your problem to LinBox users group. $\endgroup$
    – user2468
    Commented Jan 10, 2012 at 14:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .