java fft problem

Started by ramboksg April 13, 2011
I am trying to implement some algorithm in java that is originally done in matlab. One of the parts is fast fourier transform. In matlab code it looks as following: FY = fft(X,44100);
Where according to http://www.mathworks.com/help/techdoc/ref/fft.html :
Y = fft(X,n) returns the n-point DFT. fft(X) is equivalent to fft(X, n) where n is the size of X in the first nonsingleton dimension. If the length of X is less than n, X is padded with trailing zeros to length n. If the length of X is greater than n, the sequence X is truncated. When X is a matrix, the length of the columns are adjusted in the same manner.

So I am trying to implement something similar in java using jtransforms library. But when I create an instance:
DoubleFFT_1D fft = new DoubleFFT_1D(44100);

it takes about 2 minutes to create an fft instance of size 44100 which is way too long. Anyone know how to solve this problem?
Rambo-

> I am trying to implement some algorithm in java that is
> originally done in matlab. One of the parts is fast fourier
> transform. In matlab code it looks as
> following: FY = fft(X,44100);
> Where according to http://www.mathworks.com/help/techdoc/ref/fft.html :
> Y = fft(X,n) returns the n-point DFT. fft(X) is equivalent
> to fft(X, n) where n is the size of X in the first
> nonsingleton dimension. If the length of X is less than
> n, X is padded with trailing zeros to length n. If the
> length of X is greater than n, the sequence X is
> truncated. When X is a matrix, the length of the columns
> are adjusted in the same manner.
>
> So I am trying to implement something similar in java
> using jtransforms library. But when I create an instance:
> DoubleFFT_1D fft = new DoubleFFT_1D(44100);
>
> it takes about 2 minutes to create an fft instance of
> size 44100 which is way too long. Anyone know how to
> solve this problem?

Suggest to find out in detail how jtransforms fft works. It's not typical for an fft function to perform
non-power-of-2 FFT operations -- but MATLAB does it if you so specify (would be the case in your example). To do
"arbitrary length FFT" takes more sophisticated algorithms, which of course MATLAB has (and a lot of other DSP
software do not).

You might try the jtransforms fft with length 65536 (next largest power-of-2) and see if that's any faster. Note in
that case you may need to add zero-padding to X (after 44100). The jtransforms fft might do the zero-padding on its
own, but again, it depends on how it actually works.

-Jeff
As Jeff said ...

Here's the limitations listed on the jtransforms webpage:

*Limitations*

- 1D transforms for not power-of-two sizes are sequential (when the
mixed-radix is used).
- 1D transforms for power-of-two sizes can use only 2 or 4 threads.
- The number of threads must be a power-of-two number.
- Only in-place transforms are available.
- Only DCT-II
and DCT-III
are
available.
- Only DST-II
and DST-III
are
available.
- Only real DHT is
available.

So, it looks like you lose your parallel processing capability when you use
a non-power of two size for your transform. Additionally, as Jeff also
noted, power of two transforms for the FFT (as well as all of the other
transforms in this library) make use of much more efficient algorithms than
non-power of two transforms.
-Brant
On Wed, Apr 13, 2011 at 11:25 AM, Jeff Brower wrote:

> Rambo-
> > I am trying to implement some algorithm in java that is
> > originally done in matlab. One of the parts is fast fourier
> > transform. In matlab code it looks as
> > following: FY = fft(X,44100);
> >
> >
> > Where according to http://www.mathworks.com/help/techdoc/ref/fft.html :
> > Y = fft(X,n) returns the n-point DFT. fft(X) is equivalent
> > to fft(X, n) where n is the size of X in the first
> > nonsingleton dimension. If the length of X is less than
> > n, X is padded with trailing zeros to length n. If the
> > length of X is greater than n, the sequence X is
> > truncated. When X is a matrix, the length of the columns
> > are adjusted in the same manner.
> >
> > So I am trying to implement something similar in java
> > using jtransforms library. But when I create an instance:
> > DoubleFFT_1D fft = new DoubleFFT_1D(44100);
> >
> > it takes about 2 minutes to create an fft instance of
> > size 44100 which is way too long. Anyone know how to
> > solve this problem?
>
> Suggest to find out in detail how jtransforms fft works. It's not typical
> for an fft function to perform
> non-power-of-2 FFT operations -- but MATLAB does it if you so specify
> (would be the case in your example). To do
> "arbitrary length FFT" takes more sophisticated algorithms, which of course
> MATLAB has (and a lot of other DSP
> software do not).
>
> You might try the jtransforms fft with length 65536 (next largest
> power-of-2) and see if that's any faster. Note in
> that case you may need to add zero-padding to X (after 44100). The
> jtransforms fft might do the zero-padding on its
> own, but again, it depends on how it actually works.
>
> -Jeff
>
>
>

--
Brant Jameson
PhD Candidate
UC Santa Cruz Computer Engineering
http://people.ucsc.edu/~pheese
- The Discrete Hartley Transform (DHT) is a real transform, in the sense that it transforms a real-valued input sequence into a real-valued output sequence. There is nothing to be gained from using the DHT, compared to FFT algorithms written for real-valued input data (so called RFFT algorithms). The FHT actually has a few more add/sub-operations than the RFFT, but this is often swamped by the control code. The run-times also depend on the compiler (the code generator) and the target architecture. If speed is important, try to experiment with the compiler switches.
- Non-power of two algorithms, such as the Prime Factor Algorithm (PFA) and the Winograd Fourier Transform (WFA) can readily be parallelised, as they are also divide and conquer algorithms. The difference is that the transform length N must be factorisable into relative prime factors, and that the sub-DFTs in each stage are more complicated that in radix-2 algorithms. They can, however, can be computed in parallel in each stage. I am now aware of any JAVA-code for PFA and WFT, though.
Sigmund.

From: a... [mailto:a...] On Behalf Of Brant Jameson
Sent: 13. april 2011 19:59
To: Jeff Brower
Cc: a...; Rambo ksg
Subject: Re: [audiodsp] java fft problem

As Jeff said ...

Here's the limitations listed on the jtransforms webpage:
Limitations

* 1D transforms for not power-of-two sizes are sequential (when the mixed-radix is used).
* 1D transforms for power-of-two sizes can use only 2 or 4 threads.
* The number of threads must be a power-of-two number.
* Only in-place transforms are available.
* Only DCT-II and DCT-III are available.
* Only DST-II and DST-III are available.
* Only real DHT is available.
So, it looks like you lose your parallel processing capability when you use a non-power of two size for your transform. Additionally, as Jeff also noted, power of two transforms for the FFT (as well as all of the other transforms in this library) make use of much more efficient algorithms than non-power of two transforms.
-Brant
On Wed, Apr 13, 2011 at 11:25 AM, Jeff Brower > wrote:
Rambo-
> I am trying to implement some algorithm in java that is
> originally done in matlab. One of the parts is fast fourier
> transform. In matlab code it looks as
> following: FY = fft(X,44100);
> Where according to http://www.mathworks.com/help/techdoc/ref/fft.html :
> Y = fft(X,n) returns the n-point DFT. fft(X) is equivalent
> to fft(X, n) where n is the size of X in the first
> nonsingleton dimension. If the length of X is less than
> n, X is padded with trailing zeros to length n. If the
> length of X is greater than n, the sequence X is
> truncated. When X is a matrix, the length of the columns
> are adjusted in the same manner.
>
> So I am trying to implement something similar in java
> using jtransforms library. But when I create an instance:
> DoubleFFT_1D fft = new DoubleFFT_1D(44100);
>
> it takes about 2 minutes to create an fft instance of
> size 44100 which is way too long. Anyone know how to
> solve this problem?
Suggest to find out in detail how jtransforms fft works. It's not typical for an fft function to perform
non-power-of-2 FFT operations -- but MATLAB does it if you so specify (would be the case in your example). To do
"arbitrary length FFT" takes more sophisticated algorithms, which of course MATLAB has (and a lot of other DSP
software do not).

You might try the jtransforms fft with length 65536 (next largest power-of-2) and see if that's any faster. Note in
that case you may need to add zero-padding to X (after 44100). The jtransforms fft might do the zero-padding on its
own, but again, it depends on how it actually works.

-Jeff

--
Brant Jameson
PhD Candidate
UC Santa Cruz Computer Engineering
http://people.ucsc.edu/~pheese