[jira] Created: (MATH-216) Faster and more computationally-efficient Fast Fourier Transform implementation

Faster and more computationally-efficient Fast Fourier Transform implementation
-------------------------------------------------------------------------------

                 Key: MATH-216
                 URL: https://issues.apache.org/jira/browse/MATH-216
             Project: Commons Math
          Issue Type: Improvement
    Affects Versions: 1.2
            Reporter: Daniel Kuan
            Priority: Minor


Here are some suggestions on improving the speed and computational-efficiency of FastFourierTransformer.

1. Store roots of unity as a double array of arrays instead of Complex array.

No need for all the functionality that comes with class Complex when all that is required are the values of the roots of unity.

2. Keep track of the largest set of roots of unity calculated so far.

Subsequent requests for smaller sets of roots of unity can be derived from the largest set -- no need to recalculate the roots of unity from scratch.

3. When computing the nth roots of unity, need only compute n/4 roots instead of all n roots.

Since the roots of unity lie along a circle of unity radius, trigonometric relations can be leveraged to reduce the number of roots that need to be computed from n to n/4.

4. Execute transform algorithm on double primitives instead of on class Complex.

New instances of Complex are instantiated each time a simple arithmetic operation is performed on the Complex variables. Much time is lost to object creation and initialisation.



--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.

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

Daniel Kuan updated MATH-216:
-----------------------------

    Description:
Here are some suggestions on improving the speed and computational-efficiency of FastFourierTransformer.

1. Store roots of unity as a double array of arrays instead of Complex array.

No need for all the functionality that comes with class Complex when all that is required are the values of the roots of unity.

2. Keep track of the largest set of roots of unity calculated so far, and adopt Singleton pattern.

Subsequent requests for smaller sets of roots of unity can be derived from the largest set -- no need to recalculate the roots of unity from scratch.

3. When computing the nth roots of unity, need only compute n/4 roots instead of all n roots.

Since the roots of unity lie along a circle of unity radius, trigonometric relations can be leveraged to reduce the number of roots that need to be computed from n to n/4.

4. Execute transform algorithm on double primitives instead of on class Complex.

New instances of Complex are instantiated each time a simple arithmetic operation is performed on the Complex variables. Much time is lost to object creation and initialisation.


  was:
Here are some suggestions on improving the speed and computational-efficiency of FastFourierTransformer.

1. Store roots of unity as a double array of arrays instead of Complex array.

No need for all the functionality that comes with class Complex when all that is required are the values of the roots of unity.

2. Keep track of the largest set of roots of unity calculated so far.

Subsequent requests for smaller sets of roots of unity can be derived from the largest set -- no need to recalculate the roots of unity from scratch.

3. When computing the nth roots of unity, need only compute n/4 roots instead of all n roots.

Since the roots of unity lie along a circle of unity radius, trigonometric relations can be leveraged to reduce the number of roots that need to be computed from n to n/4.

4. Execute transform algorithm on double primitives instead of on class Complex.

New instances of Complex are instantiated each time a simple arithmetic operation is performed on the Complex variables. Much time is lost to object creation and initialisation.




Modified suggestion #2: added "adopt Singleton pattern".

> Faster and more computationally-efficient Fast Fourier Transform implementation
> -------------------------------------------------------------------------------
>
>                 Key: MATH-216
>                 URL: https://issues.apache.org/jira/browse/MATH-216
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 1.2
>            Reporter: Daniel Kuan
>            Priority: Minor
>
> Here are some suggestions on improving the speed and computational-efficiency of FastFourierTransformer.
> 1. Store roots of unity as a double array of arrays instead of Complex array.
> No need for all the functionality that comes with class Complex when all that is required are the values of the roots of unity.
> 2. Keep track of the largest set of roots of unity calculated so far, and adopt Singleton pattern.
> Subsequent requests for smaller sets of roots of unity can be derived from the largest set -- no need to recalculate the roots of unity from scratch.
> 3. When computing the nth roots of unity, need only compute n/4 roots instead of all n roots.
> Since the roots of unity lie along a circle of unity radius, trigonometric relations can be leveraged to reduce the number of roots that need to be computed from n to n/4.
> 4. Execute transform algorithm on double primitives instead of on class Complex.
> New instances of Complex are instantiated each time a simple arithmetic operation is performed on the Complex variables. Much time is lost to object creation and initialisation.

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.

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

Phil Steitz updated MATH-216:
-----------------------------

    Fix Version/s: 2.0

Patches welcome!

> Faster and more computationally-efficient Fast Fourier Transform implementation
> -------------------------------------------------------------------------------
>
>                 Key: MATH-216
>                 URL: https://issues.apache.org/jira/browse/MATH-216
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 1.2
>            Reporter: Daniel Kuan
>            Priority: Minor
>             Fix For: 2.0
>
>
> Here are some suggestions on improving the speed and computational-efficiency of FastFourierTransformer.
> 1. Store roots of unity as a double array of arrays instead of Complex array.
> No need for all the functionality that comes with class Complex when all that is required are the values of the roots of unity.
> 2. Keep track of the largest set of roots of unity calculated so far, and adopt Singleton pattern.
> Subsequent requests for smaller sets of roots of unity can be derived from the largest set -- no need to recalculate the roots of unity from scratch.
> 3. When computing the nth roots of unity, need only compute n/4 roots instead of all n roots.
> Since the roots of unity lie along a circle of unity radius, trigonometric relations can be leveraged to reduce the number of roots that need to be computed from n to n/4.
> 4. Execute transform algorithm on double primitives instead of on class Complex.
> New instances of Complex are instantiated each time a simple arithmetic operation is performed on the Complex variables. Much time is lost to object creation and initialisation.

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.

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

Phil Steitz updated MATH-216:
-----------------------------

    Fix Version/s:     (was: 2.0)
                   2.1

> Faster and more computationally-efficient Fast Fourier Transform implementation
> -------------------------------------------------------------------------------
>
>                 Key: MATH-216
>                 URL: https://issues.apache.org/jira/browse/MATH-216
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 1.2
>            Reporter: Daniel Kuan
>            Priority: Minor
>             Fix For: 2.1
>
>
> Here are some suggestions on improving the speed and computational-efficiency of FastFourierTransformer.
> 1. Store roots of unity as a double array of arrays instead of Complex array.
> No need for all the functionality that comes with class Complex when all that is required are the values of the roots of unity.
> 2. Keep track of the largest set of roots of unity calculated so far, and adopt Singleton pattern.
> Subsequent requests for smaller sets of roots of unity can be derived from the largest set -- no need to recalculate the roots of unity from scratch.
> 3. When computing the nth roots of unity, need only compute n/4 roots instead of all n roots.
> Since the roots of unity lie along a circle of unity radius, trigonometric relations can be leveraged to reduce the number of roots that need to be computed from n to n/4.
> 4. Execute transform algorithm on double primitives instead of on class Complex.
> New instances of Complex are instantiated each time a simple arithmetic operation is performed on the Complex variables. Much time is lost to object creation and initialisation.

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.

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

Phil Steitz updated MATH-216:
-----------------------------


Moving fix version to 2.1, awaiting patch for this enhancement.

> Faster and more computationally-efficient Fast Fourier Transform implementation
> -------------------------------------------------------------------------------
>
>                 Key: MATH-216
>                 URL: https://issues.apache.org/jira/browse/MATH-216
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 1.2
>            Reporter: Daniel Kuan
>            Priority: Minor
>             Fix For: 2.1
>
>
> Here are some suggestions on improving the speed and computational-efficiency of FastFourierTransformer.
> 1. Store roots of unity as a double array of arrays instead of Complex array.
> No need for all the functionality that comes with class Complex when all that is required are the values of the roots of unity.
> 2. Keep track of the largest set of roots of unity calculated so far, and adopt Singleton pattern.
> Subsequent requests for smaller sets of roots of unity can be derived from the largest set -- no need to recalculate the roots of unity from scratch.
> 3. When computing the nth roots of unity, need only compute n/4 roots instead of all n roots.
> Since the roots of unity lie along a circle of unity radius, trigonometric relations can be leveraged to reduce the number of roots that need to be computed from n to n/4.
> 4. Execute transform algorithm on double primitives instead of on class Complex.
> New instances of Complex are instantiated each time a simple arithmetic operation is performed on the Complex variables. Much time is lost to object creation and initialisation.

--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.