Subject: SUMMARY:3-D fast sine-transform

From: Hong <[email-masked]>
Date: Wed, 30 Jan 2002 09:21:54 -0500

Dear cclers,
Many thanks to those that replied to my last mail.  Finally I found 3-D fast
sine transform code called FFTSG from,
 http://momonga.t.u-tokyo.ac.jp/~ooura/fft.html
but unfortunately it's not the type of FST that I really want. It seems that
there are at least two types of discrete sine transform(DST), in 1-D case,
they look like 
S(k)=Sum_{j=1}^{N-1} Sin( Pi*k*j/N )
and 
S(k)=Sum_{j=0}^{N-1) Sin( Pi*k*(j+0.5)/N )

What I need is the first type in 3-D form. In FFTSG, for 1-D, both of the
two types are implimented, but for 3-D case, only the second type is available. 
I am not clear whether they can be used for same purpose. 

Following is a summary of replied mails. Most people think FFTW is a good FFT
package. Unfortunately it doesn't have implimentation of FST. Another FFT
package I want to recomend is FFTPACK. From my own tests, for 1-D case, 
FFTPACK is a little faster than FFTW.
Thank you all!
    Hong Jiang

---------------------------------------------------------
Dear cclers,
I need to use 3-D fast sine transform (FST) in my codes, but I can only
find 1-D FST code. A simple way to do 3d FST is build it from 1-D FST.
That's what I am using now. I suspect that's not the optimal way  and I wonder
whether there are more efficient  implimentations.  Could you give me
some suggestions or advice? 

From: [email-masked]
To: Hong <[email-masked]>
Date: Sat, 26 Jan 2002 14:45:26 -0200

------------------------------------------------------
Hello
 Take a look at 

 http://www.fftw.org

Pedro

-------------------------------------------------------
From: Szilveszter Juhos <[email-masked]>

http://www.fftw.org/ is a quite a good one (at least some people who I
trust are using it and told it is OK :). 

Szilva

--------------------------------------------------------
From: "Van Dam, HJJ (Huub)" <[email-masked]>
To: [email-masked]
Date: Mon, 28 Jan 2002 13:10:19 +0000

Dear Hong,

I have passed your question on to a collegue of mine who is implementing a parallel
FFT at the moment. Below is the information he came up with. I hope this helps.
Please summarise the answers you get, they might be of use to us as well.

Best wishes,

Huub

Ian Bush wrote:

> Hi Huub,
>
> Off the top of my head I know of no freeware packages that do 3-D
> Fast sine transforms, but I would be very suprised if none exist.
> I'm sure a quick search at  www.google.com will show something up.
>
> As for the efficency he's probably right - doing N**3 1D FST's to do
> a 3D FST is potentially a horribly inefficient way of doing it as
> if you do it all at once not only do you avoid a whole slew of call
> overheads you can, more importantly, play clever games to block
> the operation so that data can be reused from the cache.
>
> So apart from search google the two other things I would suggest are
>
> 1) See if his manufacturor provides a high quality implementation of
> this type of routine ( e.g. ESSL on IBM, CXML on Compaq, MKL on x86
> running either Linux or the graphical interface to DOS )
>
> 2) The FST can be related to the FFT, and there are plenty of high
> quality multi-dimensional FFT packages out there. I suggest FFTW
> at www.fftw.org
>
> Hope this is of use,
>
> Ian

-----------------------------------------------------------
From: "Susan R. Atlas" <[email-masked]>To: Szilveszter Juhos <[email-masked]>
Cc: [email-masked],  [email-masked]
Date: Wed, 30 Jan 2002 06:47:40 -0700

I have used FFTW for several years now, and it Rocks!  (very efficient,
correct, easy to use...)
On some problems it even outperformed commercial parallel FFTs tuned by the
vendor for their own parallel computing architecture.

- Susan