[Gsll-devel] fast-fourier-transform branch in repo.or.cz

[Liam Healy]

On Sat, Oct 31, 2009 at 12:53 PM, Sumant Oemrawsingh <soemraws at xs4all.nl> wrote:
> Hi Liam, others,
>
> You might want to hold off on merging fast-fourier-transforms branch into
> master, since I'm seriously considering changing the naming scheme of some of
> the objects and functions. See below for the reasons why.

I have no problem holding off.  However, I've no problem committing into
master less-than-perfect interfaces if basic functionality is there.  I don't
hesitate to change the interface later if it's an improvement in usage
or consistency, as I'm sure many have found the hard way.   Having
said that, I will respect your wishes until we have some consensus
on the issues you mention.

>
> I've committed the real FFTs to the fast-fourier-transforms branch, as well as
> an fft-example.lisp file. The file adds functions that can be called to run
> transforms similar to the examples in the manual, and could theoretically
> serve as test functions. I've not added them as tests yet though, because I'm
> not sure how to do that, or even how to automatically generate these tests.

I can do that part.  The creation of the tests is the hard part (for
me).  I will run
them and commit changes in the f-f-t branch, and you can look them over
for sanity.

>
> I'm looking into the tests in the fft directory of GSL to convert them into
> lisp, but haven't commited anything yet.
>
> Now, about the current interface:
>
> One thing that I was worried about is that I'm now using keyword arguments for
> e.g. stride and n (which probably should be called dimension?). Is this ok
> with the rest of the GSLL interface?

Mostly I skipped over porting stride arguments because I didn't see
their utility and there was some complexity involved.  In a quick check,
I notice where it is implemented in wavelet it is a mandatory argument,
and in linear-least-squares it is an optional argument.  Given the
inconsistency and incompleteness I don't think this is a major issue,
so I'd let it go for now.  At some point we'll need to do a cleanup
of the interface and this might pop up, but I'm not going to hold
things up to try to fix that now.

>
> Second, the way the objects and functions are added might not be the "nicest"
> way to add them. For instance, GSL defines real (single and double float)
> wavetables and workspaces, which, at this moment, I've added as separate
> objects using separate defmobject forms. Ideally, I'd like to define them in a
> way so that they can be constructed with (make-wavetable 'double-float
> :dimension x) or so, similar to make-marray, but I wasn't sure how to do that
> exactly. Any tips or pointers are appreciated. This would also be great for
> a macro with which to do non-radix-2 FFTs more efficiently:
> (with-fourier-transform
>  (workspace wavetable :type '(complex double-float) :dimension 129)
>  ;; Perform several FFTs that are all of the specified type and dimension,
>  ;; reusing the workspace and wavetable
>  ...)

I see what you're saying.  I'll take a look at this to see if I can come
up with a solution.   In a quick check, I don't see an analogous set
of definitions in any other part of GSLL, so this may require some work.

>
> With regard to functions, GSL has IMO a bit of an annoying naming convention,
> e.g. for complex transforms, there exists a "forward", "backward" and
> "inverse" function, as well as a "transform" function that takes a direction
> as parameter. For real transforms, there is only a "transform" function that
> does _not_ take the direction as a parameter. The reason for this is obviously
> tied to how real transforms are handled, but IMO makes for a terrible
> interface. Ideally, a user would just want to say:
>
> (fourier-transform vector) or maybe even (forward-fourier-transform vector)
> (inverse-fourier-transform vector)
> (backward-fourier-transform vector) ;; unscaled inverse transform
>
> and have all the details automatically sorted out. This would typically be
> wrapper functions around the functions that are now already in the branch.

I wholeheartedly endorse the idea of cleaning up the GSL interface where
we can.

>
> Finally, I haven't looked into how the slices by Malcolm Reynolds work yet,
> but the FFTs most likely won't work properly at all on a slice. Possibly this
> can be solved with wrapper functions as well.

Don't worry about this; I am mapping out a strategy for array handling that
is likely to be a major restructuring and not necessarily compatible with
any of the solutions that people have published, including my own.
I'm holding off on publishing my thoughts until I test enough ideas in
code to see that it's workable.

>
> Anyway, any feedback from anyone who plans to use these FFTs, has used GSL's
> FFTs or just wants to put in his two bits, is welcome.

I'm interested in this too, as I'm not really an FFT user, at least at
this level.

> Regards,
> Sumant
>

Thanks for your continued contributions.

Liam