ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 13 Oct 2011 07:35:59 -0500Solve large system of linear equations over GF(2)http://ask.sagemath.org/question/8031/solve-large-system-of-linear-equations-over-gf2/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.Mon, 28 Mar 2011 14:10:14 -0500http://ask.sagemath.org/question/8031/solve-large-system-of-linear-equations-over-gf2/Answer by malb for <p>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.</p>
<p>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.</p>
http://ask.sagemath.org/question/8031/solve-large-system-of-linear-equations-over-gf2/?answer=12752#post-id-12752Hi,
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.
Thu, 13 Oct 2011 07:35:59 -0500http://ask.sagemath.org/question/8031/solve-large-system-of-linear-equations-over-gf2/?answer=12752#post-id-12752Answer by mmarco for <p>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.</p>
<p>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.</p>
http://ask.sagemath.org/question/8031/solve-large-system-of-linear-equations-over-gf2/?answer=12243#post-id-12243It's just a guess, but maybe a groebner basis over boolean algebra method would work.
Look for documentation about the polybori interface.Thu, 31 Mar 2011 23:02:23 -0500http://ask.sagemath.org/question/8031/solve-large-system-of-linear-equations-over-gf2/?answer=12243#post-id-12243