- 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.
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
>
>
>
> 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 ramboksg●April 13, 20112011-04-13
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?