Optimizing recursive loop
Hey Everybody, I am approximating the derivative of nonperiodic functions on [-1,1] using Chebyshev polynomials. The implementation is straightforward and works well but is painfully slow. The routine wastes most of its time on a trivial operation (see comment in the code) Unfortunately the spectral coefficients are calculated recursively and thus I haven't found a way to speed up the code. I am aware of list comprehensions, the speed advantage of calling native numpy functions etc. But no luck yet finding an alternate formulation that speeds up the calculation. I attached a stripped down variant of the code. I am very grateful for tips or directions where to look for a solution (well I know writing a small C extension might be the way to go but Id love to have speedy Python) Note: The DCT takes almost no time compared to the statement in the loop. Cheers Robert
Boiled it down a bit more to only include code that actually takes time. First time around I found the other variant more instructive because it shows the discrepancy between the DCT and the loop but might be confusing. Thus here the bare minimum that correctly calculates the coefficients of the first derivative from the coefficients of the Chebyshev polynomials. Cheers Robert On 25.07.2011 00:43, Robert Elsner wrote:
Hey Everybody,
I am approximating the derivative of nonperiodic functions on [-1,1] using Chebyshev polynomials. The implementation is straightforward and works well but is painfully slow. The routine wastes most of its time on a trivial operation (see comment in the code) Unfortunately the spectral coefficients are calculated recursively and thus I haven't found a way to speed up the code. I am aware of list comprehensions, the speed advantage of calling native numpy functions etc. But no luck yet finding an alternate formulation that speeds up the calculation. I attached a stripped down variant of the code. I am very grateful for tips or directions where to look for a solution (well I know writing a small C extension might be the way to go but Id love to have speedy Python)
Note: The DCT takes almost no time compared to the statement in the loop.
Cheers Robert
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
For those cases where you cannot vectorize the operation, numpy is usually does not help much. Try using Cython. You will be able to compile the part of the code and the loop will be much faster (can be more than 100 times faster). http://docs.cython.org/ -Joon On Sun, 24 Jul 2011 18:10:14 -0500, Robert Elsner <mlist@re-factory.de> wrote:
Boiled it down a bit more to only include code that actually takes time. First time around I found the other variant more instructive because it shows the discrepancy between the DCT and the loop but might be confusing. Thus here the bare minimum that correctly calculates the coefficients of the first derivative from the coefficients of the Chebyshev polynomials.
Cheers Robert
On 25.07.2011 00:43, Robert Elsner wrote:
Hey Everybody,
I am approximating the derivative of nonperiodic functions on [-1,1] using Chebyshev polynomials. The implementation is straightforward and works well but is painfully slow. The routine wastes most of its time on a trivial operation (see comment in the code) Unfortunately the spectral coefficients are calculated recursively and thus I haven't found a way to speed up the code. I am aware of list comprehensions, the speed advantage of calling native numpy functions etc. But no luck yet finding an alternate formulation that speeds up the calculation. I attached a stripped down variant of the code. I am very grateful for tips or directions where to look for a solution (well I know writing a small C extension might be the way to go but Id love to have speedy Python)
Note: The DCT takes almost no time compared to the statement in the loop.
Cheers Robert
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
-- Using Opera's revolutionary email client: http://www.opera.com/mail/
Thanks for the hint. I thought about Cython myself but I was unable to get even the slightest speed gain out of it. Here is the equivalent Cython code with the timing and setup.py. I typed (I think). Am I missing something obvious? Cheers Robert On 25.07.2011 01:38, Joon Ro wrote:
For those cases where you cannot vectorize the operation, numpy is usually does not help much. Try using Cython. You will be able to compile the part of the code and the loop will be much faster (can be more than 100 times faster).
-Joon
On Sun, 24 Jul 2011 18:10:14 -0500, Robert Elsner <mlist@re-factory.de> wrote:
Boiled it down a bit more to only include code that actually takes time. First time around I found the other variant more instructive because it shows the discrepancy between the DCT and the loop but might be confusing. Thus here the bare minimum that correctly calculates the coefficients of the first derivative from the coefficients of the Chebyshev polynomials.
Cheers Robert
On 25.07.2011 00:43, Robert Elsner wrote:
Hey Everybody,
I am approximating the derivative of nonperiodic functions on [-1,1] using Chebyshev polynomials. The implementation is straightforward and works well but is painfully slow. The routine wastes most of its time on a trivial operation (see comment in the code) Unfortunately the spectral coefficients are calculated recursively and thus I haven't found a way to speed up the code. I am aware of list comprehensions, the speed advantage of calling native numpy functions etc. But no luck yet finding an alternate formulation that speeds up the calculation. I attached a stripped down variant of the code. I am very grateful for tips or directions where to look for a solution (well I know writing a small C extension might be the way to go but Id love to have speedy Python)
Note: The DCT takes almost no time compared to the statement in the loop.
Cheers Robert
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Yes I did. Slicing and Cython do not mix too well. Using an explicit loop fixes the problem. In case anybody is interested the code is attached. Thanks for your help Robert On 25.07.2011 12:30, Robert Elsner wrote:
Thanks for the hint. I thought about Cython myself but I was unable to get even the slightest speed gain out of it. Here is the equivalent Cython code with the timing and setup.py. I typed (I think). Am I missing something obvious?
Cheers Robert
On 25.07.2011 01:38, Joon Ro wrote:
For those cases where you cannot vectorize the operation, numpy is usually does not help much. Try using Cython. You will be able to compile the part of the code and the loop will be much faster (can be more than 100 times faster).
-Joon
On Sun, 24 Jul 2011 18:10:14 -0500, Robert Elsner <mlist@re-factory.de> wrote:
Boiled it down a bit more to only include code that actually takes time. First time around I found the other variant more instructive because it shows the discrepancy between the DCT and the loop but might be confusing. Thus here the bare minimum that correctly calculates the coefficients of the first derivative from the coefficients of the Chebyshev polynomials.
Cheers Robert
On 25.07.2011 00:43, Robert Elsner wrote:
Hey Everybody,
I am approximating the derivative of nonperiodic functions on [-1,1] using Chebyshev polynomials. The implementation is straightforward and works well but is painfully slow. The routine wastes most of its time on a trivial operation (see comment in the code) Unfortunately the spectral coefficients are calculated recursively and thus I haven't found a way to speed up the code. I am aware of list comprehensions, the speed advantage of calling native numpy functions etc. But no luck yet finding an alternate formulation that speeds up the calculation. I attached a stripped down variant of the code. I am very grateful for tips or directions where to look for a solution (well I know writing a small C extension might be the way to go but Id love to have speedy Python)
Note: The DCT takes almost no time compared to the statement in the loop.
Cheers Robert
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
Mon, 25 Jul 2011 12:30:34 +0200, Robert Elsner wrote:
Thanks for the hint. I thought about Cython myself but I was unable to get even the slightest speed gain out of it. Here is the equivalent Cython code with the timing and setup.py. I typed (I think). Am I missing something obvious?
Cython doesn't vectorize the slice operations such as b[:,j-g] but falls back to Numpy on them. You'll need to convert the slice notation to a loop to get speed gains. -- Pauli Virtanen
On Sun, Jul 24, 2011 at 5:10 PM, Robert Elsner <mlist@re-factory.de> wrote:
Boiled it down a bit more to only include code that actually takes time. First time around I found the other variant more instructive because it shows the discrepancy between the DCT and the loop but might be confusing. Thus here the bare minimum that correctly calculates the coefficients of the first derivative from the coefficients of the Chebyshev polynomials.
Have you tried using an (inverse) discrete sine transform to get the derivative? dT_n/dx = n*U_{n-1}, where U_n is the Chebyshev polynomial of the second kind, sin((n+1)\theta)/sin(theta) where cos(\theta) = x. I don't believe the discrete sine transform is part of scipy, but you can just use the inverse fft instead. <snip> Chuck
I didn't look into that but it definitely sounds interesting. Especially as the coefficient manipulation is mildly unstable for higher derivatives. Need to work out the math first though ;). Thanks for the hint. On 25.07.2011 15:59, Charles R Harris wrote:
On Sun, Jul 24, 2011 at 5:10 PM, Robert Elsner <mlist@re-factory.de> wrote:
Boiled it down a bit more to only include code that actually takes time. First time around I found the other variant more instructive because it shows the discrepancy between the DCT and the loop but might be confusing. Thus here the bare minimum that correctly calculates the coefficients of the first derivative from the coefficients of the Chebyshev polynomials.
Have you tried using an (inverse) discrete sine transform to get the derivative? dT_n/dx = n*U_{n-1}, where U_n is the Chebyshev polynomial of the second kind, sin((n+1)\theta)/sin(theta) where cos(\theta) = x. I don't believe the discrete sine transform is part of scipy, but you can just use the inverse fft instead.
<snip>
Chuck
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
participants (4)
-
Charles R Harris -
Joon Ro -
Pauli Virtanen -
Robert Elsner