Hi Liam,

Yes, I've seen the tests, and am working on them and the examples. I'll commit something in the weekend, hopefully together with the real FFTs. That would make at least the FFT part of GSLL complete. But I'd still like to make some wrappers that make the FFT less awkward/more manageable, in the sense of automatically determining whether to use the real or complex FFT, and the radix-2 or mixed-radix ones.

In case you're wondering about why the real and complex FFTs are separated, and not just methods that dispatch on the element type of the marray, this has to do with the fact that the FFT of a real array is a complex array, but GSL doesn't store it that way. This poses no problem for the implementation, however, just a little bit of thought on my part. I'll have this sorted out and implemented in a few days.

If you want to work on the tests yourself, that's fine as well, but I thought that since I'm working on the whole FFT implementation anyway, I might as well finish the complete thing.

-Sumant

On Wed, Oct 28, 2009 at 11:07:50PM -0400, Liam Healy wrote:

Sumant,

Thanks for your work. This is a much-awaited addition. I will look it over this weekend with the idea of merging it into master; there shouldn't be any reason not to but I do run the tests on SBCL and CCL prior to committing to master just to make sure there are no regressions.

I've been trying to make it a practice to port the GSL tests to GSLL. These tests are obtained by running "make check" when building GSL. The tests for FFT look like they are in fft/test*.c. I will look at porting those tests, but if you have any insight/tips in doing that port, I'd appreciate your ideas.

Liam

On Mon, Oct 26, 2009 at 7:54 PM, Sumant Oemrawsingh soemraws@xs4all.nl wrote:

...

Hey guys,

As discussed on #lisp with LiamH, I have pushed a branch containing some preliminary stuff to get GSL's FFTs working. Unsurprisingly, the branch is called fast-fourier-transform, and should actually be easily merged with master without causing things to break. I just thought to make a branch out of it in case I totally, completely and utterly break stuff, since these are my first contributions to GSLL and my first non-trivial experience with git.

What is implemented: All complex FFT (double and single floats) are implemented.

What works/is tested: radix 2 and mixed radix stuff is working and tested with the examples in the manual. I will push the examples translated to lisp as well when I clean it up.

What isn't tested: The decimation-in-frequency functions are implemented, but I have no idea what they are supposed to do.

Over the next days, I will be implementing the real transforms as well, test all the functions with respect to their C counterparts and finally make some nicer wrapper functions around them (unless people are radically opposed to that).

Thanks, Sumant Oemrawsingh (Sikander on #lisp)

---

Gsll-devel mailing list Gsll-devel@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/gsll-devel

On Sat, Oct 31, 2009 at 12:53 PM, Sumant Oemrawsingh soemraws@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