This validates what I've often said, which is that if you use the right algorithms and the right data structures, then Python can be just as fast as a compiled alternative (especially since "the right data structures" usually means fast built-in data structures).
To me, right now, there a four main things that can make SymPy slow (in order: - expand - slow matrices/linear algebra - slow polys (esp. in highly multivariate situations) - the core expand() is the worst. If we can make that faster, then all of SymPy will feel zippier. Slow linear algebra is responsible for slow solve(), but also for slow integrate(), since heurisch() basically hangs here. I'm not sure where else it is used (other than in the matrices themselves, obviously). For slow polys, this rarely makes things slow, but it serves as a barrier to make things faster, since if you rewrite an algorithm using the polys, it makes it slower whenever the polynomials have more than a few variables (this is what happened with heurisch). Whenever I find myself breaking a long computation, I'd say 70% of the time it is in expand somewhere and 60% of the time it is in the polys. The core I would say is actually not too slow, at least compared to these other things, but since it is used everywhere, even marginal speedups can add up. Your work (I'm assuming) will fix point 3, and your continuing work will fix point 2. Do you have any plans to fix point 1 (expand)? For point 4 of course the best way forward is to remove the old assumptions. In my opinion, though, speed is the least concern in the core. Bigger issues are how to better manage canonicalization and how to deal with global vs. local assumptions. Aaron Meurer On Wed, Mar 13, 2013 at 4:29 PM, Mateusz Paprocki <[email protected]> wrote: > 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. > > -- 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.
