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?

# java fft problem

Started by ●April 13, 2011

Reply by ●April 13, 20112011-04-13

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

> 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

Reply by ●April 15, 20112011-04-15

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

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

Reply by ●April 18, 20112011-04-18

- 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

- 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