ACF calculation might be quadractic

[kain88-de]

The fftpack library implemented in numpy doesn't scale as well as the fftw for all input sizes. The optimal scaling of O(N log N) is only achieved if the length of your input is a power of 2 or 3. For other input sizes the divide and conquer approach doesn't work. The worst case is for lengths that are prime numbers, then fftpack falls back to the O(N^2) algorithm. fftpack has a nice helper function to find the optimal length. This means you have to pad the array with a few more zeros.

# ensure that we always use a power of 2 or 3 for zero-padding,
# this way we'll ensure O(n log n) runtime of the fft.
n = fftpack.helper.next_fast_len(2 * nobs + 1)

I use this in my own library.

https://github.com/bio-phys/pydiffusion/blob/master/pydiffusion/util/timeseries.py

[pdebuyl]

Hi @kain88-de thank you for the comment!

My benchmark was done with powers of 2, which is what I use most of the time. I was aware of the issue you mentioned but never actually tested it and the result is speaking :-)

I wish to depend only on numpy for tidynamics. I am testing using only powers of 2 at the "padding" stage of the fast correlation algorithm. The output seems very close to the previous benchmark except that there are no peaks at non-power of 2 lengths.

NumPy's documentation for ffts does not mention further performance hints, so I see no better "pure NumPy" improvements.

[pdebuyl]

The issue was close by the commit message automatically. The benchmark now has extra non-power of two points: http://lab.pdebuyl.be/tidynamics/auto_examples/plot_nlogn_scaling.html#sphx-glr-auto-examples-plot-nlogn-scaling-py

This is the first contribution I receive for tidynamics, I will add a section in the documentation to mention it.

Also, very nice library https://github.com/bio-phys/pydiffusion I was not aware of its existence. You might also be interested in rowan, a NumPy-based quaternion library that I have reviewed for the journal of open source software: openjournals/joss-reviews#787

[kain88-de]

Great to hear your performance is better now. I would suggest you to copy the function from scipy into your module. I have on times run out of memory with only powers of two. The scipy version will look for powers of 2,3 and 5 which will be better. There are also a good bunch of tests you can copy as well.

…

On Fri 29. Jun 2018 at 14:32, Pierre de Buyl ***@***.***> wrote: The issue was close by the commit message automatically. The benchmark now has extra non-power of two points: http://lab.pdebuyl.be/tidynamics/auto_examples/plot_nlogn_scaling.html#sphx-glr-auto-examples-plot-nlogn-scaling-py This is the first contribution I receive for tidynamics, I will add a section in the documentation to mention it. Also, very nice library https://github.com/bio-phys/pydiffusion I was not aware of its existence. You might also be interested in rowan, a NumPy-based quaternion library that I have reviewed for the journal of open source software: openjournals/joss-reviews#787 <openjournals/joss-reviews#787> — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEGnVsJYRE2eCkHfpeETVs9j1BLUahRMks5uBh5KgaJpZM4U8sZu> .