[Maxima] Comments about FFT
ziga.lenarcic at gmail.com
Sat Aug 22 17:36:44 CDT 2009
I've tried the 'new' fft in Maxima with support for lists. While all
is nice and it 'works', after inspecting sourcecode it seem to be
implemented in a very inefficient way. I haven't tested the speed of
the internal fft algorithm, but since it's a lisp rewrite from a
fortran book, probably there are faster algorithms.
What concerns me the most is the conversion from array to a list and
such related tasks.
(dotimes (i ($length a1))
(setf (nth (1+ i) a1) (m+ (nth (1+ i) a1) (m* '$%i (nth (1
+ i) a2)))))
can't be efficient on lists of length perhaps 1024*8. Surely the list
should be traversed in some other way (and constructing a complex
number with m+ and m* is probably an overkill also). Maxima's 'fft'
is terribly slow, but doesn't need to be.
I would suggest also to take a look at existing implementations in CL
which also allows for arrays which are not of length of power of 2
(but uses a much slower algorithm in such cases).
Why not use code that's already there in such cases?
Ideally FFTW with CFFI should be used, but since Maxima doesn't want
to rely on C libraries yet, this is not an option.
More information about the Maxima