[Numpy-discussion] chirp-z

[David Cournapeau]

Charles R Harris wrote:
>
>
> On 5/27/07, *Matthieu Brucher* <matthieu.brucher at gmail.com 
> <mailto:matthieu.brucher at gmail.com>> wrote:
>
>     Hi,
>
>     Isn't the chirp transform only two cross-correlations ? And for a
>     fast one, there is a module in SciPy, and I think that kind of
>     operation belongs more to Scipy than Numpy ;)
>
>
> Umm, no,
>
> There really aren't any transparent fast fft convolutions in SciPy. 
> The closest thing is in signaltools, fftconvolve, and if you ask it to 
> convolve, say, sequences whose length add up to 7902, then it will do 
> a size 7901 transform. Because 7901 is prime this takes about 300 
> times as long as a transform of size 8192.
There is only one fft implementation in numpy, and I don't think it 
works (eg it is not O(NlogN)) for prime numbers.
> That glitch could be fixed, but I think something as basic as 
> fftconvolve should reside at a higher level than scipy.signals anyway, 
> say in numpy.fft.
numpy is for low level things. The problem of fft is that good, general 
fft algorithms (which work for any size in O(NlogN)) are not that 
common, and not easily distributable. scipy.fft does have code to do 
that, though, if you have one of the required library (mkl, fftw both 
provide NlogN behaviour for any size).

Now, for convolution, you could use 0 padding, but this kind of thing 
may be too high level for numpy (which should be kept to the minimum: 
the goal of numpy really is to provide ndarray and basic).

>
> There are other scipy functions that do convolution, but those that 
> use an fft are limited. There is a (buggy) version for 2d arrays in 
> stsci, and a  version with limited (real) functionality in fftpack. I 
> don't see any more.
Could you open a ticket on scipy trac with an example which shows the 
bug, and explain what you want ? I may take a look at it (I have some 
code to do cross correlation in numpy somewhere, and could take time to 
improve its quality for inclusion in scipy).

David