Re: [office-comment] office-formula: FFT functions?

[robert_weir@us.ibm.com]

Hi Steven,

This is an interesting idea.  In practice,do you think this makes sense as 
spreadsheet array functions which take an array and return an array?  Or 
as an application comment that prompts the user to select an input and 
output range,along the lines of what Excel does with its Analysis Toolkit?

My experience is that most users are not even aware of array functions in 
Excel and how they use.  On the other hand, most users are not aware of 
FFT's either.

If done as a spreadsheet function, the FFT would obviously need to be 
recalculated every time one of the cells in the input range changed.  At 
O(N log N) this isn't so bad.

Do you know if there are any ways to calculate an FFT with incremental 
changes?  So I calculate once in O(N log N) and then change only some of 
the input cells, a small portion of them -- is there a much faster way of 
calculating the new results?

Note also that complex number support in spreadsheets is rather poor in 
general, and only a handful of functions work with them.

What functions would you recommend?  Maybe FFT() and the inverse IFFT(). 
Each one might have a parameter that specifies the normalization 
convention.  Maybe also a Power() function?  I could imagine in the time 
domain CrossCorrelation()and AutoCorrelation() would be useful as well. 
These are interesting for fields beyond signal processing, including 
economics.

Note however that it is always a debatable point on whether a particular 
feature request should be placed in the standard, or whether it is best 
done as an extension.  I'd be more encouraged to add features like this to 
the ODF standard if we had one or more vendors committed to supporting 
this feature in their product. 

If it were purely up to me, I'd love to create the ultimate 
engineer's/scientist's spreadsheet application.   There are a lot of 
things we could do, like adding units support, integration with R, etc. 
But we would need a set of volunteers dedicated to implementing this in 
OpenOffice or Gnumeric or someplace.

Regards,

-Rob

___________________________

Rob Weir
Software Architect
Workplace, Portal and Collaboration Software
IBM Software Group

email: robert_weir@us.ibm.com
phone: 1-978-399-7122
blog: http://www.robweir.com/blog/



"Steven G. Johnson" <stevenj@fftw.org> 
01/28/2008 05:58 PM
Please respond to
stevenj@math.mit.edu


To
office-comment@lists.oasis-open.org
cc

Subject
[office-comment] office-formula: FFT functions?






Hi, I was wondering if there was any interest in including a discrete 
Fourier transform function in OpenFormula (and, based on that, one can 
easily implement convolutions, correlations, autocorrelations, etcetera as 

desired). e.g. Excel has some FFT functionality via the data analysis 
toolpack, as I understand it, but I didn't see anything in the OpenFormula 

draft.

I'm co-author of FFTW (www.fftw.org), a popular free-software FFT 
implementation (used e.g. in Matlab, GNU Octave, etc.), and I wanted to 
send you a note in case you wanted any help with this.  I would be happy 
to provide any advice on specification, a reference implementation, 
etcetera that you might need.  I'm not a spreadsheet expert, but I hope 
that my knowledge of FFTs and their applications would be helpful.

We get a sizeable amount of email at fftw.org from people who just want to 

transform some data in a spreadsheet, and so I get the impression that 
that there is a fair demand for this kind of capability; also, if you 
google "excel fft" you will get a lot of pages.  FFTs themselves are kind 
of hard for a user to implement in a spreadsheet language, but once you 
have them there are all sorts of things that can be done directly in the 
formula language (windowing, filtering, correlations, etcetera).

Regards,
Steven G. Johnson [stevenj at math dot mit dot edu]

PS. If you do specify FFT functions, you don't want to make the same 
mistakes that Excel did, e.g. you don't want to artificially limit support 

to power-of-two sizes (a very inconvenient restriction for analysis of 
user-generated data).  Given a power-of-two FFT, you can implement support 

for arbitrary sizes with a couple dozen more lines of code (via 
Bluestein's algorithm), so there's really no excuse not to support any 
size with O(n log n) complexity.

This publicly archived list offers a means to provide input to the
OASIS Open Document Format for Office Applications (OpenDocument) TC.

In order to verify user consent to the Feedback License terms and
to minimize spam in the list archive, subscription is required
before posting.

Subscribe: office-comment-subscribe@lists.oasis-open.org
Unsubscribe: office-comment-unsubscribe@lists.oasis-open.org
List help: office-comment-help@lists.oasis-open.org
List archive: http://lists.oasis-open.org/archives/office-comment/
Feedback License: http://www.oasis-open.org/who/ipr/feedback_license.pdf
List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
Committee: 
http://www.oasis-open.org/committees/tc_home.php?wg_abbrev=office