Hi, On 12 March 2013 07:37, ThanhVu Nguyen <[email protected]> wrote: > That sounds very interesting. Can you share some details on what you did > that makes it much faster, even when using pure Python coefficients ? why > is that the current solve in sympy is so slow comparing to the one in Sage ? >
Speed improvement is a combination of better algorithms and data structures, and many hours spent with a profiler. In case of this development branch all three are equally important. One reason why solve() is currently slow is because it uses SymPy's symbolic expression trees for doing coefficient arithmetic in matrices module (instead of gmpy if available or PythonRational, which is a much faster cousin of Rational and Fraction (Python 2.6+) types). > How do I reproduce what you did after obtaining the patch, assuming the > input is my original list of 165 equations as given in > http://pastebin.com/cE87W9m3 ? What is eqs_165x165() in the code eqs = > eqs_165x165() ? Also, how long usually does it take for such a patch to > get into the main sympy branch ? > See https://github.com/mattpap/sympy/blob/sparse-polys/sympy/polys/benchmarks/bench_solvers.py. Function eqs_165x165() just creates the system of equations. I copied http://pastebin.com/cE87W9m3 there and created a benchmark out of it. So if you pull changes from https://github.com/mattpap/sympy/tree/sparse-polys then just literally repeat commands from my previous E-mail to reproduce those results. I made some further improvements and now it takes 1.95 seconds on average on my computer to load and solve the system. I also solved this system in Maxima directly and, thought it alone was faster than Sage, it's still slower than this code. It took it 2.3 seconds to load equations from a file and 5.7 to solve the system. However, it has to be pointed out that Maxima does a little more than SymPy in this case, because it tries to "simplify"/make the results look pretty. Personally I don't like such behavior, because if I wanted solutions "simplified" I could feed them to simplify() (although in SymPy simplify() could hang because it still uses old slow polynomials). Simplifications can be disabled in Maxima with "simp: false;" and with this setup it takes 0.6 seconds to load and 4.3 to solve the system. Even now it does some postprocessing, but I don't think it's very expensive. This branch should get merged in a week, but until a stable release of SymPy, APIs may change quite a bit (and they will), so you may have to update your code regularly if you will follow development repository of SymPy. This is, however, a great opportunity to submit early feedback regarding features, bugs and/or speed. > Thanks for the works ! > > >> >> On 9 March 2013 21:41, ThanhVu Nguyen <[email protected]> wrote: >> > They are linear equations, the coeficients are floating points ... the >> > simpliest kind of linear equations for solving. For example >> > >> > solve([2x + 2y + 3= 0 , 4.2x + 5y + 1 = 0 ... ] , solution_dict=True) >> > >> > Here's a real big one 165 unknowns with 165 equations that SAGE's solve >> > runs >> > at least 5 times faster than Sympy's solve: >> > http://pastebin.com/cE87W9m3 >> > >> >> Recently I got some interesting speed improvements regarding this >> issue in a development branch (see >> https://github.com/sympy/sympy/pull/1840). I was able to solve this >> 165x165 system under 4 seconds on my computer (Sage takes about 24 >> seconds when simply using solve()). >> >> To be fair, I got this result by >> using gmpy for coefficient domain (which SymPy does automatically >> anyway if gmpy is installed), but even with pure Python coefficients >> (int, Fraction) it takes under 19 seconds to solve the system. Also, >> please note that this doesn't use the symbolic core of SymPy >> (sympy.core), so there will be additional speed penalty when >> converting between symbolic trees and efficient low-level polynomial >> and matrix representations. If you want to try it out you have to use >> sparse-polys branch from #1840 pull request. Here is a sample code: >> >> In [1]: from sympy.polys.benchmarks.bench_solvers import * >> >> In [2]: %time eqs = eqs_165x165() >> CPU times: user 2.12 s, sys: 0.01 s, total: 2.13 s >> Wall time: 2.12 s >> >> In [3]: %time sol = solve_lin_sys(eqs, R_165) >> CPU times: user 1.60 s, sys: 0.01 s, total: 1.60 s >> Wall time: 1.59 s >> >> > >> > >> > On Friday, March 8, 2013 12:36:38 AM UTC-7, Aaron Meurer wrote: >> >> >> >> What kind of equations are these? Are they linear equations, or >> >> polynomial? Are the coefficients rational, floating point, or >> >> symbolic. Maybe you could paste an example somewhere. >> >> >> >> solve being slow is a real problem. To fix it, we need to figure out >> >> what part is slowing it down, and either make it faster or figure out >> >> if it can be removed for that computation. >> >> >> >> Aaron Meurer >> >> >> >> On Thu, Mar 7, 2013 at 10:57 PM, ThanhVu Nguyen >> >> <[email protected]> wrote: >> >> > I concur, the "solve in Sympy is very slow comparing to the "solve" >> >> > function in Sage. Doesn't need to come up with any special example, >> >> > just >> >> > try to solve over 20 unknowns and so and you will see the difference. >> >> > >> >> > One of my problem requires solving for 248 eqts for 164 unknowns. >> >> > Here's >> >> > the >> >> > time: with SAGE 4.5.1 : 82.8926379681 secs, with Sympy 0.7.2: >> >> > 557.724228144 >> >> > secs. Both give the exact same solution so no problem on >> >> > soundness. >> >> > >> >> > I don't like using Sage because it's inconvenient to ask the users to >> >> > download the huge package, but my stuff relies on equation solvings >> >> > so >> >> > I >> >> > have to stick with Sage. >> >> > >> >> > >> >> > >> >> > On Sunday, February 24, 2013 3:15:27 AM UTC-7, Alessandro Bernardini >> >> > wrote: >> >> >> >> >> >> Hello, >> >> >> >> >> >> i have to solve systems of linear algebraic equations (nodal >> >> >> equations >> >> >> from circuit theory). >> >> >> I tried examples witch 7 unknowns and a lot of symbolic parameters: >> >> >> i >> >> >> obtain 7 equations in the 7 unknowns (and with the symbolic >> >> >> parameters). >> >> >> Then i solve for the 7 unknowns: sympy solve simply runs "out of >> >> >> time". >> >> >> For 3 unknowns in 3 equations the results are computed after a few >> >> >> minutes. For 7 unknowns in 7 equations i had to stop the >> >> >> computation. >> >> >> >> >> >> Sage math does it in much lesser time. >> >> >> >> >> >> I have tried manual=True simplify=False and other options and i >> >> >> always >> >> >> have the same performance problem. >> >> >> >> >> >> Can someone help ? >> >> >> >> >> >> Thanks >> >> >> >> >> > -- >> >> > You received this message because you are subscribed to the Google >> >> > Groups >> >> > "sympy" group. >> >> > To unsubscribe from this group and stop receiving emails from it, >> >> > send >> >> > an >> >> > email to [email protected]. >> >> > To post to this group, send email to [email protected]. >> >> > Visit this group at http://groups.google.com/group/sympy?hl=en. >> >> > For more options, visit https://groups.google.com/groups/opt_out. >> >> > >> >> > >> > >> > -- >> > You received this message because you are subscribed to the Google >> > Groups >> > "sympy" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> > an >> > email to [email protected]. >> > To post to this group, send email to [email protected]. >> > Visit this group at http://groups.google.com/group/sympy?hl=en. >> > For more options, visit https://groups.google.com/groups/opt_out. >> > >> > >> >> Mateusz > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at http://groups.google.com/group/sympy?hl=en. > For more options, visit https://groups.google.com/groups/opt_out. > > Mateusz -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sympy?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
