Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. 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.

Rank to TopRank to BottomVotersWatch issueWatchersConvert to sub-taskLinkCloneUpdate Comment AuthorReplace String in CommentUpdate Comment VisibilityDelete Comments
    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 3.0
    • Fix Version/s: 3.0
    • Labels:

      Description

      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.

        Attachments

        1. FastFourierTransformerTest.java
          30 kB
          Kurt Ostfeld
        2. FastFourierTransformer.java
          31 kB
          Kurt Ostfeld
        3. Main.java
          1 kB
          Kurt Ostfeld
        4. DFTPerformanceWithPatch.png
          8 kB
          Kurt Ostfeld
        5. DFTPerformanceWithoutPatch.png
          8 kB
          Kurt Ostfeld

          Activity

          $i18n.getText('security.level.explanation', $currentSelection) Viewable by All Users
          Cancel

            People

            • Assignee:
              celestin Sebastien Brisard
              Reporter:
              kurtostfeld Kurt Ostfeld

              Dates

              • Created:
                Updated:
                Resolved:

                Issue deployment