ACF calculation might be quadractic
kain88-de opened this issue · 3 comments
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
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.
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