On Jun 14, 2010, at 10:17 AM, Kevin Hunter wrote: > I'm currently working on a mathematical optimization framework. > Briefly, solving an optimization problem means finding the best > possible solution from a set of feasible solutions. Usually, this > involves maximizing or minimizing one or more "objective" functions, > but within the confines of a number of constraints. One problem might > be > > Maximize f(x,y) = x^2 + x - 2y > subject to > constraint 1: y > 5 "y must be greater than 5" > constraint 2: x < 40 "x must be less than 40" > constraint 3: 3x + 3y + 2x - 3x < 40 "the eqn must be less than > 40"
Is this related to cylindrical algebraic decomposition? > > This is a very simplistic problem. For starters it has but 2 > variables, x and y. Many of the problems posed to our optimization > framework regularly have hundreds of thousands or millions of > variables. > > Currently, our framework can handle this size problem, but it spends a > significant amount of time in our reduction phase, I think roughly > what Sympy calls simplification. As our core competency is in > optimization, not variable and expression manipulation in this regard, > I'm looking at possible options to outsource this part of our work. What do you mean by reduction? Is it mainly cancelation of things like 2*x - x and x**2/x, or is there more involved? > > As I've only recently discovered Sympy, I am impressed by what the API > can currently do and plans to do in the future. However, I'm curious > at its state of performance. i.e. Speed. I note that there's a > difference between sympycore and sympy, as far as the wiki goes, but > I'm wondering how strong the interest of the core developers is toward > performance. > > Here's example code to illustrate one calculation set a user of our > codebase might do. Specifically, I note that this Sympy snippet is > only "feasible" for values of size about 100 (which takes 7 minutes on > my machine). I submit that as I'm new to Sympy, this is perhaps not a > "proper" Sympy interaction, so please educate me as necessary. > > <code language='python'> > from sympy import * > > size = int(30) > > Xvars = [ Symbol( 'X%i' % i ) for i in xrange(size) ] > Yvars = [ Symbol( 'Y%i' % i ) for i in xrange(size) ] > > mysum = lambda x, y: x + y > > answer = reduce( mysum, > [x * y > for x in Xvars > for y in Yvars] > ) A slightly better way to do this is to send the list straight to Add. # For size == 30 In [26]: %timeit answer = reduce( mysum, [x * y for x in Xvars for y in Yvars]) 100 loops, best of 3: 5.24 ms per loop In [27]: %timeit answer = Add(*[x * y for x in Xvars for y in Yvars]) 100 loops, best of 3: 2.92 ms per loop In [34]: size = 100 In [35]: Xvars = [ Symbol( 'X%i' % i ) for i in xrange(size) ] In [36]: Yvars = [ Symbol( 'Y%i' % i ) for i in xrange(size) ] In [37]: %timeit answer = reduce( mysum, [x * y for x in Xvars for y in Yvars]) 1 loops, best of 3: 64.4 ms per loop In [38]: %timeit answer = Add(*[x * y for x in Xvars for y in Yvars]) 10 loops, best of 3: 34.3 ms per loop In [37]: %timeit answer = reduce( mysum, [x * y for x in Xvars for y in Yvars]) 1 loops, best of 3: 64.4 ms per loop In [38]: %timeit answer = Add(*[x * y for x in Xvars for y in Yvars]) 10 loops, best of 3: 34.3 ms per loop #NOTE, the first time did take a long time as it did for you, but I think it was much faster after that due to caching. I think the list comprehension is probably the best way to do that bit, except maybe using a generator instead of a list comprehension (i.e., (x*y for x in Xvars for y in Yvars) instead of [x*y for x in Xvars for y in Yvars]). You do realize that the size of this list increases quadratically with size? As for speed, if the expressions you are dealing with are only polynomial in nature, you might achieve better speed by installing gmpy, running sympy with the SYMPY_GROUND_TYPES=gmpy set in bash, and using Polys. Note that this gmpy speed up is only available in our development branch for the moment. Polys might not be faster for multiple variables at the moment because they use a dense multivariate representation based on nested lists, but Mateusz has promised to merge in a sparse dense representation based on dictionaries that will be faster. However, you will have to try it. For now, regular sympy expressions may be faster, depending on what you do. There is also support in the Polys, in master, for cython. I am not too sure how to get this working, so someone else will have to help there, but it should provide an additional speed up. > > print answer > </code> > > Questions in bullet form: > - Is this is a "Sympy" way of doing this multiplication and > summation? > > - We would regularly have that size variable be on an order greater > than 10,000. Currently, this code seems only feasible for values of > up to about 100, which takes this snippet on my machine about 7 > minutes. What is the inclination towards performance optimization > within the Sympy project and developer community? > We are always working on improving sympy, and performance is important. We hope to cythonize the core, but first we need to refactor it with our new assumptions, which may take some time. Also, we are always welcome to patches if you find something that you can improve yourself. Aaron Meurer -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
