FFT package
7 Jun 2005 20:03:37 UTC
Topic 189304
(moderation:
Does someone know which package for the discrete FFT is used in the code (in case the algorithm relies on the discrete FFT)? I am sure the people involved in the scientific part of the code have done their job well.
I recall a couple of years ago seti@home changing their FFT libraries with Ooura's code (http://momonga.t.u-tokyo.ac.jp/~ooura/) in version 3.0. The Seti client also relies a lot on this type of transform and since they switched to it, that was an indication that the code was among the best at the time.
I was wondering if this is the library used here as well.
"Everything should be made as simple as possible, but not simpler." A. Einstein
FFT package
)
Stoyan,
The code that does the guts of the analysis doesn't actually use any FFT package. It's been written from scratch by the LIGO Science Collaboration.
Why?
I've said on this board a couple of times that the analysis code is based on Fourier transforms. That's "based on" rather than "is." I was being a bit disingenuous in the interest of simplicity.
In fact, what is being computed is something called the F-statistic, from some papers which are linked in other posts on this board (and are not two hundred years old like Fourier's paper). It's not a straight Fourier transform, although it is related. As an idealized (continuous) mathematical equation, it involves four inverse Fourier transforms combined in a certain way (basically to account for the daily variations of the detector beam pattern as the Earth rotates).
The actual implementation of the F-statistic is even stranger than that due to practical considerations. To avoid trashing the server (not to mention many of the hosts), the data files that Einstein@Home sends out cover only narrow frequency bands of the data. Basically, they are 10-hour stretches that have already been FFT'ed from the time domain and cut down to only 0.1Hz bandwidth. (The full band of the detector is about 50Hz to 1500Hz.) With the full frequency band we could run four inverse FFTs and combine them to make the F-statistic, but with a narrow band of data that would waste an awful lot of operations.
So there is some code that adds up the needed pieces of the four inverse FFTs. It does use the Dirichlet kernel (the thing with all the complex exponentials in it that other people have posted on this forum when describing Fourier transforms), but it picks out only the stuff it needs. And it does it in such a way as to demodulate - that is, "undo" the Doppler shifts due to the motion of the detector as it moves with the surface of the Earth, assuming a particular location on the sky which is indicated by the orange bullseye in the screen saver.
The answer I gave before, that the code is based on Fourier transforms, was true and short but rather vague because I didn't want to get too technical.
A short, less vague, more descriptive, yet still non-technical answer would be: It contains pieces of four lobotomized Fourier transforms, tied up and stitched together in a nonstandard way at the end. That's why we had to write our own.
I hope that was more entertaining,
Ben
Thanks for your exhaustive
)
Thanks for your exhaustive answer, Ben.
I was suspecting the algorithms could be specific. Actually I found some papers that you had pointed in another thread (probably these are the papers you are mentioning):
> http://arxiv.org/abs/gr-qc/9804014 - I. The signal and its detection
> http://arxiv.org/abs/gr-qc/9809046 - II. Accuracy of estimation of parameters
> http://arxiv.org/abs/gr-qc/9901013 - III. Detection statistics and
> computational requirements
> http://arxiv.org/abs/gr-qc/0012108 - IV. An all-sky search
There is more than necessary in them to gratify my curiosity. I have been a fan of the project for a long time and I am getting to like it more and more.
"Everything should be made as simple as possible, but not simpler." A. Einstein