[Gsll-devel] Possible use of user-supplied vector sizes and offsets for FFT

[Sumant Oemrawsingh]

On Tue, Nov 03, 2009 at 10:54:00PM -0400, Liam Healy wrote:
> Sumant,
> 
> In writing GSLL, I've tried to adhere to the philosophy of providing a
> good Lisp interface to GSL as it exists in the latest release.  When
> I've had ideas on better ways to do GSL, I've restrained myself from
> putting them in GSLL.  So, there may well be ways they could have made
> a better, more versatile, etc. library, but I have not tried to
> implement them.  I've chosen this policy in order to limit the amount
> of work required for GSLL, which has been substantial as it is.

I totally understand your point here, and agree in general.

> Specifically with regard to FFTs, the 2+ dimensions case may be very
> useful, but I don't see that GSL has done it, so I will avoid it in
> GSLL.  The stride is there in GSLL because it's in GSL; offset is not.

This is where I do not agree. GSL has not explicitly done 2D FFTs, that is
true. However, it provides a mechanism to implement this yourself. When you
say offset is not in GSLL because it is not in GSL, I don't think you
appreciate the ease with which an offset is introduced to a C array; you just
add a number to it. Thus, an array a of size n can be passed with an offset by
saying a+offset, where the latter array has a size n-offset. Therefore, GSL
doesn't have to explicitly provide the offset as a parameter.

True, stride is mostly in there to only apply an FFT to, say, one column of an
array. The size n is there to be able to do an FFT on just part of your array.
Generally, the latter makes no sense without the ability to also have offsets.

I think it's fine to not have the 2D FFTs as a direct functionality in GSLL.
I just wouldn't like to see GSLL lose flexibility with respect to GSL, and as
it is now, in GSL someone can easily write an N-dimensional FFT in GSL by just
looping over his array, while in GSLL, aside from looping, lots of slicing,
copying (and probably consing in the process) would have to be done. I've
looked at some old code I used, and see that I indeed did perform a 2D
transform in GSL (before I started using FFTW because it was faster on huge
arrays).

> So where does that leave your good ideas?  A lot of what you're
> talking about I think can be helped along by having a mechanism for
> array creation, slicing, concatenation, etc., and perhaps another
> chunk by a port of fftw that is compatible with GSLL arrays.  As you
> have seen and we have discussed, there has been a lot of discussion on
> array utilities and they are a highly requested feature.  I have given
> this a lot of thought recently and decided there needs to be a
> separate system to do this, in part because I was uneasy in adding
> things to GSLL that weren't part of GSL and in part because I realize
> the extent of what needs to be done really justifies a separate system
> (or more likely, systems).  I have not had a chance to create and test
> much code, but I hope to soon.

This sounds good. However, note that in GSL, you just need N loops for an
N-dimensional FFT, no "array utilities" required.

> I'll continue to work on the FFT port and let you work it over before
> I pull it into master.  Then I'm going to try to pull together the
> beginnings of the array system; it will take a while to get that
> settled but I think it will be worth making this as versatile as
> possible.

Also sounds good. I'm still available to implement some of the FFT work. You
won't have to be afraid that I put in all sorts of crazy stuff before
discussing it with you :)

Regards,
Sumant