commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sébastien Brisard (Commented) (JIRA) <>
Subject [jira] [Commented] (MATH-732) Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement). Preserved public API 100%. Removed unnecessary use of instance variables and instance state.
Date Wed, 08 Feb 2012 08:12:00 GMT


Sébastien Brisard commented on MATH-732:

Hi Kurt,
first of all, thanks again for your patch. From what I can judge, it is very clearly written
and should be easy to maintain. Could you please have a look to what I have done with it {{r1241807}}.
Does that suit you?

Here is the list of the small changes I've done
# Created {{double[][] TransformUtils.createRealAndImaginaryArray(Complex[])}} in place of
** {{double[] FastFourierTransformer.getRealArray(Complex[])}}
** {{double[] FastFourierTransformer.getImaginaryArray(Complex[])}}
# Moved {{Complex[] FastFourierTransformer.buildComplexArray(double[], double[])}} to {{TransformUtils.createComplexArray(double[][])}}
# Changed {{FastFourierTransformer.transformInPlace(double[], double[], boolean)}} to  {{FastFourierTransformer.transformInPlace(double[][],
# Renamed some variables to conform with camelCase.

What do you think of the use of two dimensional arrays instead of two one-dimensional arrays?

Things which are still pending about {{FastFourierTransformer.bitReversalShuffle2(double[],
* Could you please provide a javadoc for this method?
* I would be tempted to make this method private. If it stays public, the assertion about
the length of the arrays has to be changed into a proper test + exception.
* To be consistent with the rest of the class, I should think that its signature should be
changed to {{FastFourierTransformer.bitReversalShuffle2(double[][])}}

On static methods. I keep thinking about the point you raised above. I like the idea of having
static methods, but that would not apply to {{FastCosineTransformer}} and {{FastCosineTransformer}},
which both implement {{RealTransformer}}. Now, in the new implementation of {{FastFourierTransform}},
we have some inconsistencies
* {{transformInPlace(double[][], boolean)}} is static, and always performs the _standard_
* {{transform(Complex[]}} and {{inverseTransform(Complex[])}} are _not_ static, and perform
either the _standard_ or the _unitary_ transform, depending on how the transformer was created.

I would recommend that {{transformInPlace(double[][], boolean)}} be changed to a *class* method,
and that this method performs either the _standard_ or the _unitary_ transform, just like
the other methods in this class. This seems more logical to me, but this is of course only
my view on the subject.

Looking forward to reading your thoughts on the subject.
> Major Speed Improvement to 1D Discrete Fourier Transform (approximately 5x-9x improvement).
Preserved public API 100%. Removed unnecessary use of instance variables and instance state.
> ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
>                 Key: MATH-732
>                 URL:
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>            Assignee: Sébastien Brisard
>              Labels: api, perfomance
>             Fix For: 3.0
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png,,,
> I wrote my own Discrete Fourier Transform function in Java and ran some benchmarks and
found that it ran dramatically faster than the Apache library implementation. This is a pretty
straight forward implementation of the standard Cooley Tukey algorithm that I read out of
a textbook. This passes all the Apache library test cases plus several I had written on my
own. I created a source code library patch that preserves the public API completely while
changing the internal implementation to achieve the performance improvement.
> In addition to the performance issue, I suggest that Discrete Fourier Transform functionality
be provided as stateless pure functions (in Java this would be implemented with static methods)
just like most other math functions. As-is, the library requires the user to instantiate a
Transformer instance which maintains instance state, which is an unecessary complexity for
a pure math function. I held off on this change since it would change the public API and affect
existing code. However, I see similar backward compatability breaking API changes are already
in the FastFourierTransformer class in the 3.0 code base.

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:!default.jspa
For more information on JIRA, see:


View raw message