Optimizing Python polynomial evaluation

Question

I have a function which evaluates terms of a polynomial in several variables. The inputs are lists of powers of each variable. For example, for two variables and 2nd order it looks like this,

def f(x,y): return [1, x[1], y[1], x[1]*y[1], x[2], y[2]] x = [2**0, 2**1, 2**2] y = [3**0, 3**1, 3**2] >>> f(x,y) [1,2,3,6,4,9]

In reality the function is higher order and has many variables so on average there are a few thousand terms (in fact, I create the function at run time with an eval statement, but that's not important). The function is on an inner most loop and is currently a speed bottleneck. The profiler tells me I spend most of the time in __times__.

Short of creating a C extension module, can anyone see any room for optimization?

Edit: The example above is trying to evaulate 1 + x + y + xy + x^2 + y^2 with x = 2and y = 3, except without adding them, just putting each term in a list.

Adding them is fine (with some coefficients A, B, ...) i.e. all I'm trying to do is compute:

A + B*x + C*y + D*x*y + E*x^2 + F*y^2.

How often is the function called with similar or the same arguments? — Nolen Royalty, CommentedApr 8, 2012 at 7:53
I'm really not sure about what your script does, but have you tried looking into scipy/numpy? — Rik Poggi, CommentedApr 8, 2012 at 7:55
@NolenRoyalty good question, unfortunately the answer is that each variable is different every time. — marius, CommentedApr 8, 2012 at 8:00
Can the functions be described using recursion in such a way that you could cache previous values to calculate future ones? — Nolen Royalty, CommentedApr 8, 2012 at 8:01
@NolenRoyalty Hmm... I don't think caching anything would help, each time a new x,y, etc... is picked randomly and the polynomial gets evaluated. — marius, CommentedApr 8, 2012 at 8:09

Rik Poggi · Accepted Answer · 2012-04-08 09:00:03Z

I'm not sure from which version, but numpy should have a polyval2d(x,y,c) function into the polynomial module, that will perfectly apply to your example.

You seemed interested in expanding your example to a much higher dimension.

In the same module there's a polyval3d(x,y,z,c), if that's not enought I'd suggest (as I guess you're already doing) to look at the source code. It shouldn't be too hard to implement what best suits your needs, and you can always ask here on SO :)

Aha, that DID help. What I was looking for is something called Horner's method. The idea is that instead of evaluating 1 + x + y + x^2 + y^2 + x y, you evaluate 1 + y (1 + y) + x (1 + x + y) which involves fewer operations. — marius, CommentedApr 8, 2012 at 20:22

Janne Karila · Accepted Answer · 2012-04-08 14:52:56Z

The function is on an inner most loop and is currently a speed bottleneck.

You could try to get rid of the loop altogether, by using NumPy and replacing your variables with arrays of higher dimension.

A good idea but I don't know the next values of x,y, etc... until after I evaluate the function, so I can't vectorize it. — marius, CommentedApr 8, 2012 at 20:17

Collectives™ on Stack Overflow

Optimizing Python polynomial evaluation

2 Answers 2

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Related