Re: Cleaning and fixing fft in scipy ?

Pearu Peterson wrote:
>
> I am ok with both steps. Let us know when the first step is complete
> so that we can test that the interface is working for different backends.
I have something almost ready for review (complex 1d only), but I have a 
couple of questions:
    - My understanding is that except for djbfft backend, all other 
backend implement fft of any size (eg different than 2^n); so for djbfft 
backend, for size different than 2^n, it uses a diffferent backend. For 
example, if FFTW (v2) is selected and djbfft detected, then the zfft 
function is effectively using 2 backend: djbfft and fftw2. Would it be a 
big problem if in djbfft case, the sizes != 2^n are always handled 
through a fixed backend (fftpack I guess) ?
    - there is one backend called fftwork. I would like to check wether 
my patch at least compile for all backend, but I don't know this 
backend, and didn't find anything on the internet ?

cheers,

David

Re: Cleaning and fixing fft in scipy ?

On 02/05/07, David Cournapeau <david <at> ar.media.kyoto-u.ac.jp> wrote:
>     - My understanding is that except for djbfft backend, all other
> backend implement fft of any size (eg different than 2^n); so for djbfft
> backend, for size different than 2^n, it uses a diffferent backend. For
> example, if FFTW (v2) is selected and djbfft detected, then the zfft
> function is effectively using 2 backend: djbfft and fftw2. Would it be a
> big problem if in djbfft case, the sizes != 2^n are always handled
> through a fixed backend (fftpack I guess) ?

Well, probably not, as people using djbfft probably know what they are
doing. But It does seem a bit drastic to drop from the fastest backend
to the slowest if say fftw or MKL is also installed. Especially as
this would provide lower performance than the current implementation.

But why is this necessary anyway? It is only decided at compile time
right? Or are you going the whole way and compiling all available back
ends and then letting people choose dynamically? That would be a nice
feature.

Cheers,
John

Re: Cleaning and fixing fft in scipy ?

John Travers wrote:
> On 02/05/07, David Cournapeau <david <at> ar.media.kyoto-u.ac.jp> wrote:
>>     - My understanding is that except for djbfft backend, all other
>> backend implement fft of any size (eg different than 2^n); so for djbfft
>> backend, for size different than 2^n, it uses a diffferent backend. For
>> example, if FFTW (v2) is selected and djbfft detected, then the zfft
>> function is effectively using 2 backend: djbfft and fftw2. Would it be a
>> big problem if in djbfft case, the sizes != 2^n are always handled
>> through a fixed backend (fftpack I guess) ?
>
> Well, probably not, as people using djbfft probably know what they are
> doing. But It does seem a bit drastic to drop from the fastest backend
> to the slowest if say fftw or MKL is also installed. Especially as
> this would provide lower performance than the current implementation.
If fftw or mkl is installed, I am not sure djbfft would be used anyway. 
It may have been the fastest fft a few years ago, but I cannot repeat 
any of the results given on djbfft with recent CPU (and by recent, I 
mean a pentium 4, that is already a few years old) and compilers. More 
fundamentally, if you care about efficiency fpr fft, you use 2^N size.
>
> But why is this necessary anyway? It is only decided at compile time
> right? 
The goal of the reorganization was:
    - to make easier to read existing code
    - to make it easier to add additional backends

It was a bit complicated to support point 2 with only C macro in a 
reliable way (because of djbfft exception, like the ones I assume you 
put for mkl/djbfft). But after having thought a bit, I took a totally 
different approach: I am now generating the code with a python script 

Cleaning zfft: first patch

Hi,

    I've just finished the first part of cleaning fftpack (only zfft for 
now; wanted to get dev feedback before implementing the scheme for 
everything). The patch is available as the ticket 408:

http://projects.scipy.org/scipy/scipy/ticket/408

    The patch consists in two part:
       - one part split each implementation out of zfft.c, to put it in 
zfft_name.c files, where name is the name of the backend (mkl, fftw, 
fftw3, etc...). The corresponding files have no #ifdef, etc... and 
should be easy to read/improve now.
       - the above source files are then used to generate a zfft.c file, 
through a python script. The main reason why I used python to generate 
the file instead of C macro is because I find this solution easier to 
add backend: adding a backend only consists in creating a new 
zfft_name.c file, and adding name to a python list in the python 
script.  Also, as the zfft.c is human readable and do not use new 
macros, it should be easy to read it now.
        - Regenerating the zfft.c file is only necessary when one of the 
backend source is changed, or when a new backend is added.

    Otherwise, it should work exactly as before; any change of behaviour 
with respect to configuring/compiling/running is a bug :) I've made no 
attempt for the python script to be pretty, too

    cheers,

    David

Old numarray convolve2d fft=1 option

Hi,
I'm relatively new to this, and certainly no expert on the underlying 
math of all this stuff, but I'm trying to do relatively large kernel 
convolutions on large 2d matrices.  The kernels might be 160x160 while 
the matrices themselves might be 2500x2500.  They're also likely to be 
sparse matrices, but I'll worry about that later - for now I'm just 
scoping things out.

So... anyway... with those size convolutions in mind, I'm intrigued by 
the fft=1 option that was in the numarray.convolve2d function (or so it 
says at

http://stsdas.stsci.edu/numarray/numarray-1.5.html/node65.html

This option doesn't seem to be in the current scipy.signal.convolve2d 
function.  Presumably it would speed 2d convolutions up a lot?

Is there a way around this?

Or a plan to put the fft implementation into scipy.signal.convolve2d?

Thanks

David

--

-- 
David O'Sullivan, Senior Lecturer
School of Geography and Environmental Science
University of Auckland | Te Whare Wananga o Tamaki Makaurau

Re: Old numarray convolve2d fft=1 option

David O'Sullivan wrote:
> Hi,
> I'm relatively new to this, and certainly no expert on the underlying 
> math of all this stuff, but I'm trying to do relatively large kernel 
> convolutions on large 2d matrices.  The kernels might be 160x160 while 
> the matrices themselves might be 2500x2500.  They're also likely to be 
> sparse matrices, but I'll worry about that later - for now I'm just 
> scoping things out.
>
> So... anyway... with those size convolutions in mind, I'm intrigued by 
> the fft=1 option that was in the numarray.convolve2d function (or so it 
> says at
>
> http://stsdas.stsci.edu/numarray/numarray-1.5.html/node65.html
>
> This option doesn't seem to be in the current scipy.signal.convolve2d 
> function.  Presumably it would speed 2d convolutions up a lot?
>
> Is there a way around this?
>
> Or a plan to put the fft implementation into scipy.signal.convolve2d?
>
> Thanks
>
> David
>
>
>   
David,

Re: getting test method name

[sorry, again moving something from email to the list]

"Brian Hawthorne" <brian.lee.hawthorne <at> gmail.com> writes:
[concerning a backwards-compatibility in mlabwrap's testing.py]
> I noticed though that you added a python >= 2.5 dependency in the
> setup.pyfile in order to have absolute imports.

Yes -- but I reckon we might want to stay a bit more conservative with the
testing stuff since our hope is to get that included somewhere else and since
scipy/matplotlib/numpy still support 2.3, IIRC. If it turns out not to be
needed (or there is little external interest in testing.py anyway), I'd drop
it immediately.

> I finally got matlab installed on my laptop but couldn't build until after
> removing that dependency (because I have py2.4). Since 2.4 is still the
> default version distributed for example with Fedora 6, do you think we could
> just wait a bit before adding a 2.5 dependency?

Sure, if installing python2.5 is inconvenient for you, feel free to revert the
changes (just comment the relevant blocks out). I'll try to at least make some
more headway with the proxying thing before I plan to make use of python 2.5
features (customization of proxying behavior would also be a good candidate
for 2.5-style with-statements, however).

I'm a bit surprised by the implication that fedora (unlike debian or ubuntu)
doesn't manage to support multiple version of python, which sounds pretty
sucky. BTW Is the following any help?

<http://www.serpentine.com/blog/2006/12/22/how-to-build-safe-clean-python-25-rpms-for-fedora-core-6/>

should scikits.mlawrap require python2.5 [Was: Re: getting test method name]

Sorry, I forgot to fix the subject line, please reply to this email instead,
I'll paste in the same body -- 'as

[sorry, again moving something from email to the list]

"Brian Hawthorne" <brian.lee.hawthorne <at> gmail.com> writes:
[concerning a backwards-compatibility in mlabwrap's testing.py]
> I noticed though that you added a python >= 2.5 dependency in the
> setup.pyfile in order to have absolute imports.

Yes -- but I reckon we might want to stay a bit more conservative with the
testing stuff since our hope is to get that included somewhere else and since
scipy/matplotlib/numpy still support 2.3, IIRC. If it turns out not to be
needed (or there is little external interest in testing.py anyway), I'd drop
it immediately.

> I finally got matlab installed on my laptop but couldn't build until after
> removing that dependency (because I have py2.4). Since 2.4 is still the
> default version distributed for example with Fedora 6, do you think we could
> just wait a bit before adding a 2.5 dependency?

Sure, if installing python2.5 is inconvenient for you, feel free to revert the
changes (just comment the relevant blocks out). I'll try to at least make some
more headway with the proxying thing before I plan to make use of python 2.5
features (customization of proxying behavior would also be a good candidate
for 2.5-style with-statements, however).

I'm a bit surprised by the implication that fedora (unlike debian or ubuntu)
doesn't manage to support multiple version of python, which sounds pretty
sucky. BTW Is the following any help?

Re: Old numarray convolve2d fft=1 option

On 02/05/07, David O'Sullivan <dosu004 <at> sges.auckland.ac.nz> wrote:

> I'm relatively new to this, and certainly no expert on the underlying
> math of all this stuff, but I'm trying to do relatively large kernel
> convolutions on large 2d matrices.  The kernels might be 160x160 while
> the matrices themselves might be 2500x2500.  They're also likely to be
> sparse matrices, but I'll worry about that later - for now I'm just
> scoping things out.

Sparse matrices are going to want another algorithm - if they're
sparse enough, the direct approach to convolutions (implemented taking
sparseness into account) will almost certainly be more efficient.

> This option doesn't seem to be in the current scipy.signal.convolve2d
> function.  Presumably it would speed 2d convolutions up a lot?

Basically, yes. FFTs are fairly fast and they turn convolutions into
elementwise multiplication.

It would not be terribly difficult to implement from scratch: you take
a two-dimensional real FFT of each array, padding appropriately,
multiply the FFTs, and take an inverse two-dimensional real FFT. You
may have to fiddle with normalizations a bit.

But, as always, I would not spend much effort optimizing the procedure
until you're sure that this step will be slow enough to matter. Though
as you're convolving a matrix with four million elements, it probably
will...

If you're *really* in a hurry, and the input matrices are sparse

Re: Cleaning and fixing fft in scipy ?

On May 2, 2007, at 05:02 , John Travers wrote:

> On 02/05/07, David Cournapeau <david <at> ar.media.kyoto-u.ac.jp> wrote:
>>     - My understanding is that except for djbfft backend, all other
>> backend implement fft of any size (eg different than 2^n); so for  
>> djbfft
>> backend, for size different than 2^n, it uses a diffferent  
>> backend. For
>> example, if FFTW (v2) is selected and djbfft detected, then the zfft
>> function is effectively using 2 backend: djbfft and fftw2. Would  
>> it be a
>> big problem if in djbfft case, the sizes != 2^n are always handled
>> through a fixed backend (fftpack I guess) ?
>
> Well, probably not, as people using djbfft probably know what they are
> doing.

Not necessarily  It's listed as a possible dependency, so people  
(like me) just install it.

--

-- 
|>|\/|<
/------------------------------------------------------------------\
|David M. Cooke              http://arbutus.physics.mcmaster.ca/dmc/
|cookedm <at> physics.mcmaster.ca

_______________________________________________