[jira] [Created] (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.

classic Classic list List threaded Threaded
27 messages Options
12
Reply | Threaded
Open this post in threaded view
|

[jira] [Created] (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.

Gilles (Jira)
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: https://issues.apache.org/jira/browse/MATH-732
             Project: Commons Math
          Issue Type: Improvement
    Affects Versions: 3.0
            Reporter: Kurt Ostfeld
             Fix For: 3.0
         Attachments: FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff

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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment: FastFourierTransformerTest.java.diff
                FastFourierTransformer.java.diff
   

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment: DFTPerformanceWithPatch.png
                DFTPerformanceWithoutPatch.png

These benchmarks were run on my laptop and averaged over ten trials. The benchmark code used the current and unchanged public API to the 3.0 FastFourierTransformer class.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment: FastFourierTransformerTest.java.diff
                FastFourierTransformer.java.diff

This is a reupload of the exact same patch files. Last time, I didn't notice the ASF license option. This time, it's properly selected.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13185174#comment-13185174 ]

Sébastien Brisard commented on MATH-732:
----------------------------------------

Thanks Kurt! Such a speed-up is obviously most welcome. As you might have noticed (MATH-677), we are in the middle of cleaning-up the interface for fast transforms. I'm currently working on the tests, which were a bit slim previously. So now is a good time to include your proposal. I will look into it, and try to reproduce your results. Please allow for some time, though!

As for having all flavours of {{transform()}} static. This would indeed be nice not to have to instantiate {{FastFourierTransformer}}. However, this would mean that
* the type (standard, unitary) of transform to be performed should be specified through the call to {{transform()}}
* it would not be possible to specify the {{transform()}} methods in a common interface (see {{RealTransformer}}). Whether it really matters, I'm not sure.

For the time being, could you please make sure you sign the [ICLA|http://apache.org/licenses/#clas] (if you haven't already)?
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13191248#comment-13191248 ]

Kurt Ostfeld commented on MATH-732:
-----------------------------------

Thank you so much, Sebastien!

I signed the ICLA and it's filed.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment: Main.java

Simple benchmark program that I used to generate results.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13192851#comment-13192851 ]

Bruce A Johnson commented on MATH-732:
--------------------------------------

I see your benchmark program does the speed test with a real array as input.  Do you know if similar speed gains are present when using a complex array?
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment: Main.java

updated version of simple benchmark program that uses complex input data rather than a real input.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13193152#comment-13193152 ]

Kurt Ostfeld commented on MATH-732:
-----------------------------------

I ran the updated benchmark that uses complex data (with non-zero imaginary values) and got more pronounced speed improvements with the patched library.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13193226#comment-13193226 ]

Bruce A Johnson commented on MATH-732:
--------------------------------------

Great and thanks.  I'm anxious to try this in some of my software that heavily uses the Commons Math FFT.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>            Reporter: Kurt Ostfeld
>              Labels: api, perfomance
>             Fix For: 3.0
>
>         Attachments: DFTPerformanceWithPatch.png, DFTPerformanceWithoutPatch.png, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13198561#comment-13198561 ]

Sébastien Brisard commented on MATH-732:
----------------------------------------

Hi Kurt,
I'm willing to have a look to your proposal. As we are trying to release 3.0 soon, we need to decide if this issue is postponed to 3.1. I've been working quite a lot on MATH-677, and the patch you provided no longer works. Would you like to check out the latest version of CM and patch against this version ? Alternatively (preferably), you could just attach the whole modified {{FastFourierTransformer}} class, since I will keep both old and new implementations side by side for the sake of my tests.

Thanks beforehand,
Sébastien
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment: FastFourierTransformerTest.java
                FastFourierTransformer.java

Updated versions of code that merges and accommodates other recent changes in trunk. Full versions rather than diff files.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformer.java.diff, FastFourierTransformer.java.diff, FastFourierTransformerTest.java, FastFourierTransformerTest.java.diff, FastFourierTransformerTest.java.diff, Main.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment:     (was: FastFourierTransformer.java.diff)
   

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformerTest.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment:     (was: Main.java)
   

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformerTest.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment:     (was: FastFourierTransformer.java.diff)
   

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformerTest.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment:     (was: FastFourierTransformerTest.java.diff)
   

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformerTest.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Kurt Ostfeld updated MATH-732:
------------------------------

    Attachment:     (was: FastFourierTransformerTest.java.diff)
   

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformerTest.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13199019#comment-13199019 ]

Kurt Ostfeld commented on MATH-732:
-----------------------------------

I'm hoping this should be a fairly easy drop-in replacement. I'm still seeing large (~10x) performance improvements in my benchmarks. I had to make very small tweaks to the unit tests: In three cases, I had to reduce testing tolerance by one, because the output results differed passed the 13th decimal value.
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformerTest.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


Reply | Threaded
Open this post in threaded view
|

[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.

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-732?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13199115#comment-13199115 ]

Sébastien Brisard commented on MATH-732:
----------------------------------------

Thanks Kurt for all this work. I will look into it in the coming days. I agree this might be fairly easy to include, but I do want to spend some time on the comparison: I'm sure there is a lot to learn from comparing the old and new implementations.
As for testing tolerance, I just set it so that the current implementation passes the tests, so no worries about your modifications.
Sébastien
               

> 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: https://issues.apache.org/jira/browse/MATH-732
>             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, FastFourierTransformer.java, FastFourierTransformerTest.java, Main.java
>
>
> 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: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira


12