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, 17 Oct 2013 06:54:13 -0500Solve a "big" polynomial system numericallyhttp://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/I would like to solve numerically a polynomial system with around 10^5 variables and 10^7 equations. Each equation is of degree 4 with integer coefficients and contains around 10 variables, so that the **jacobian** of the system is a very "**hollow**" matrix with **integer entries**.
Let X=[x_0,x_1, x_2,...] and E=[eq_0,eq_1, eq_2...] the list of variables and equations :
> Is there a SAGE function f(E,X) which
> find numerically solutions for such a system?
> Is SAGE relevant for such intensive
> computation ?
I think the code needs to be **100% cython**, for not losing time.
My computer has a hard disk of 980 Go, 4Go of RAM and its processor "Intel Core i5 CPU 760 @ 2.80GHz × 4" is around 10^9 FLOPS.
I guess my computer is not enough powerful for doing such computation in a reasonable time :
The jacobian J is a (10^5)x(10^7) matrix, so for example, the [Gauss-Newton algorithm](http://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm) would require around 1000 Go of RAM and 10^16 operations.
> I know very few things in numerical
> analysis, so some advices would be
> welcome.
Wed, 16 Oct 2013 00:25:28 -0500http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/Answer by Shashank for <p>I would like to solve numerically a polynomial system with around 10^5 variables and 10^7 equations. Each equation is of degree 4 with integer coefficients and contains around 10 variables, so that the <strong>jacobian</strong> of the system is a very "<strong>hollow</strong>" matrix with <strong>integer entries</strong>. </p>
<p>Let X=[x_0,x_1, x_2,...] and E=[eq_0,eq_1, eq_2...] the list of variables and equations : </p>
<blockquote>
<p>Is there a SAGE function f(E,X) which
find numerically solutions for such a system? </p>
<p>Is SAGE relevant for such intensive
computation ? </p>
</blockquote>
<p>I think the code needs to be <strong>100% cython</strong>, for not losing time. </p>
<p>My computer has a hard disk of 980 Go, 4Go of RAM and its processor "Intel Core i5 CPU 760 @ 2.80GHz × 4" is around 10^9 FLOPS. </p>
<p>I guess my computer is not enough powerful for doing such computation in a reasonable time : <br/>
The jacobian J is a (10^5)x(10^7) matrix, so for example, the <a href="http://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm">Gauss-Newton algorithm</a> would require around 1000 Go of RAM and 10^16 operations. </p>
<blockquote>
<p>I know very few things in numerical
analysis, so some advices would be
welcome.</p>
</blockquote>
http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?answer=15544#post-id-15544If you think the problem is going to take a long time, then using cython is recommended. Start the notebook with %cython in the beginning and declare the matrix as a numpy matrix instead of a sage matrix, using command cdef np.matrix. Also the scipy algorithm for leastsq is very similar to newton-gauss method. You can use scipy.optimise.leastsq to solve the equation.
I hope it helps. I normally work with small matrices so I might be wrong, but I have to loop over a lot of matrices and using scipy within cython is much faster than default sage algorithms. Wed, 16 Oct 2013 07:04:24 -0500http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?answer=15544#post-id-15544Comment by Sébastien Palcoux for <p>If you think the problem is going to take a long time, then using cython is recommended. Start the notebook with %cython in the beginning and declare the matrix as a numpy matrix instead of a sage matrix, using command cdef np.matrix. Also the scipy algorithm for leastsq is very similar to newton-gauss method. You can use scipy.optimise.leastsq to solve the equation. </p>
<p>I hope it helps. I normally work with small matrices so I might be wrong, but I have to loop over a lot of matrices and using scipy within cython is much faster than default sage algorithms. </p>
http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?comment=16921#post-id-16921Thank you very much, I will try scipy algorithm and numpy matrix. Is it compatible with the "sparse mode" for matrix ?Wed, 16 Oct 2013 22:13:06 -0500http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?comment=16921#post-id-16921Comment by Shashank for <p>If you think the problem is going to take a long time, then using cython is recommended. Start the notebook with %cython in the beginning and declare the matrix as a numpy matrix instead of a sage matrix, using command cdef np.matrix. Also the scipy algorithm for leastsq is very similar to newton-gauss method. You can use scipy.optimise.leastsq to solve the equation. </p>
<p>I hope it helps. I normally work with small matrices so I might be wrong, but I have to loop over a lot of matrices and using scipy within cython is much faster than default sage algorithms. </p>
http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?comment=16920#post-id-16920If you want sparse matrix you can use the scipy matrix instead to numpy. http://docs.scipy.org/doc/scipy/reference/sparse.htmlThu, 17 Oct 2013 06:54:13 -0500http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?comment=16920#post-id-16920Answer by tmonteil for <p>I would like to solve numerically a polynomial system with around 10^5 variables and 10^7 equations. Each equation is of degree 4 with integer coefficients and contains around 10 variables, so that the <strong>jacobian</strong> of the system is a very "<strong>hollow</strong>" matrix with <strong>integer entries</strong>. </p>
<p>Let X=[x_0,x_1, x_2,...] and E=[eq_0,eq_1, eq_2...] the list of variables and equations : </p>
<blockquote>
<p>Is there a SAGE function f(E,X) which
find numerically solutions for such a system? </p>
<p>Is SAGE relevant for such intensive
computation ? </p>
</blockquote>
<p>I think the code needs to be <strong>100% cython</strong>, for not losing time. </p>
<p>My computer has a hard disk of 980 Go, 4Go of RAM and its processor "Intel Core i5 CPU 760 @ 2.80GHz × 4" is around 10^9 FLOPS. </p>
<p>I guess my computer is not enough powerful for doing such computation in a reasonable time : <br/>
The jacobian J is a (10^5)x(10^7) matrix, so for example, the <a href="http://en.wikipedia.org/wiki/Gauss%E2%80%93Newton_algorithm">Gauss-Newton algorithm</a> would require around 1000 Go of RAM and 10^16 operations. </p>
<blockquote>
<p>I know very few things in numerical
analysis, so some advices would be
welcome.</p>
</blockquote>
http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?answer=15543#post-id-15543If it can help, the mathematical english for "creuse" is "sparse", not "hollow". So you can have a look at:
sage: M = matrix(ZZ, 10^5, 10^7, sparse=True)
sage: M
100000 x 10000000 sparse matrix over Integer Ring (type 'print M.str()' to see all of the entries)
sage: M[3,4] = 10
sage: M[10,10]
0
sage: M[3,4]
10
And then see if Sage can survive your computations.
Wed, 16 Oct 2013 05:25:10 -0500http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?answer=15543#post-id-15543Comment by Sébastien Palcoux for <p>If it can help, the mathematical english for "creuse" is "sparse", not "hollow". So you can have a look at:</p>
<pre><code>sage: M = matrix(ZZ, 10^5, 10^7, sparse=True)
sage: M
100000 x 10000000 sparse matrix over Integer Ring (type 'print M.str()' to see all of the entries)
sage: M[3,4] = 10
sage: M[10,10]
0
sage: M[3,4]
10
</code></pre>
<p>And then see if Sage can survive your computations.</p>
http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?comment=16922#post-id-16922Thank you very much ! (I also do my PhD at the IML, Luminy, with Antony Wassermann in operators algebras, 2005-2009). So if I understand well, in mode sparse, the computer memorizes only the non-zero entries, and so in my case, this needs only 100 Mo of RAM (instead of 1000 Go).Wed, 16 Oct 2013 22:11:53 -0500http://ask.sagemath.org/question/10605/solve-a-big-polynomial-system-numerically/?comment=16922#post-id-16922