Solve large system of linear equations over GF(2)

asked 2011-03-28 21:10:14 +0100

ji-o
33 ●2 ●2 ●6

I need to solve a pretty large system of linear equations over GF(2) (The matrix is around 20000 x 20000). The straightforward approach used to solve linear equation systems (by using MatrixSpace and octave) will ran out of memory before even building up the matrix.

I wonder if there is any method i could use to solve such a system. Also note that the system i try to solve is sparse in general.

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2011-04-01 06:02:23 +0100

mmarco
351 ●4 ●13 ●20

It's just a guess, but maybe a groebner basis over boolean algebra method would work. Look for documentation about the polybori interface.

edit flag offensive delete link

add a comment

answered 2011-10-13 14:35:59 +0100

malb
71 ●2 ●4

Hi,

20,000 x 20,000 is not large and you should be able to do it in a few seconds on a modern CPU:

http://m4ri.sagemath.org/performance.html

However, Sage doesn't expose the fast code we have for this in M4RI:, cf.

http://m4ri.sagemath.org/doxygen/solve_8h.html

That's why it's not as fast as it should be. Sorry, we should fix this.

edit flag offensive delete link

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2011-03-28 21:10:14 +0100

Seen: 1,881 times

Last updated: Oct 13 '11

Solve large system of linear equations over GF(2) edit

2 Answers