[jira] [Commented] (MATH-745) up to 5x Performance Improvement on FasFourierTransformer.java by using a recursive iterative sumation Approach
[ https://issues.apache.org/jira/browse/MATH-745?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206865#comment-13206865 ] Bruce A Johnson commented on MATH-745: -- Just to be clear, is this 5x faster than the old implementation (pre Math-732), or after Math-732 (and thereby ~25x faster than the old)? > up to 5x Performance Improvement on FasFourierTransformer.java by using a > recursive iterative sumation Approach > --- > > Key: MATH-745 > URL: https://issues.apache.org/jira/browse/MATH-745 > Project: Commons Math > Issue Type: Improvement >Affects Versions: 3.0 >Reporter: Leandro Ariel Pezzente > Labels: FFT, Fast, Fourier, Transform > Attachments: FastFourierTransformer.patch.txt > > > By swithinch form a loop iterative approach to a recursive iterative approach > on fastFourierTransformer.java a Perfomance Improvement of up to 5x is gained. -- 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
[jira] [Commented] (MATH-728) Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than 2*dim+1
[
https://issues.apache.org/jira/browse/MATH-728?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13206281#comment-13206281
]
Bruce A Johnson commented on MATH-728:
--
I've been playing with BOBYQA (downloaded from svn repository today, and
commenting out the PathNotExplored exceptions). A couple observations.
1) I can't make it fail with large number of interpolation points (as long as
you stay under the (2n+1)*(2n+2)/2 recommended max. So this issue is resolved.
2) With large number of interpolation points the algorithm is significantly
slower. I'm minimizing a function with a 169 parameters. The function
evaluation takes ~50 msec. With n+2 interpolation points, the additional time
for each step is about 10 msec. With 2*n+1 points, the additional time is
about 50 msec, and with about 6*n, the additional time is 250 msec. So with
larger nInterpolation points a lot of time is spent in the algorithm, besides
evaluating the function. At some point I'll try to do some profiling of the
code.
3) It makes a big difference to normalize the parameters as the initial search
region is dependent on the point with the smallest boundary difference. So it
seems one shouldn't directly fit the "natural" parameters but normalized values.
> Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than
> 2*dim+1
> --
>
> Key: MATH-728
> URL: https://issues.apache.org/jira/browse/MATH-728
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 3.0
> Environment: Mac Java(TM) SE Runtime Environment (build
> 1.6.0_29-b11-402-11M3527)
>Reporter: Bruce A Johnson
>
> I've been having trouble getting BOBYQA to minimize a function (actually a
> non-linear least squares fit) so as one change I increased the number of
> interpolation points. It seems that anything larger than 2*dim+1 causes an
> error (typically at
> line 1662
>interpolationPoints.setEntry(nfm, ipt,
> interpolationPoints.getEntry(ipt, ipt));
> I'm guessing there is an off by one error in the translation from FORTRAN.
> Changing the BOBYQAOptimizerTest as follows (increasing number of
> interpolation points by one) will cause failures.
> Bruce
> Index:
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> ===
> ---
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (revision 1221065)
> +++
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (working copy)
> @@ -258,7 +258,7 @@
> //RealPointValuePair result = optim.optimize(10, func, goal,
> startPoint);
> final double[] lB = boundaries == null ? null : boundaries[0];
> final double[] uB = boundaries == null ? null : boundaries[1];
> -BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 1);
> +BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 2);
> RealPointValuePair result = optim.optimize(maxEvaluations, func,
> goal, startPoint, lB, uB);
> //System.out.println(func.getClass().getName() + " = "
> // + optim.getEvaluations() + " f(");
--
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
[jira] [Commented] (MATH-728) Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than 2*dim+1
[
https://issues.apache.org/jira/browse/MATH-728?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13203540#comment-13203540
]
Bruce A Johnson commented on MATH-728:
--
Hi Giles,
I'll try to do so over the next couple days.
cheers,
Bruce
> Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than
> 2*dim+1
> --
>
> Key: MATH-728
> URL: https://issues.apache.org/jira/browse/MATH-728
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 3.0
> Environment: Mac Java(TM) SE Runtime Environment (build
> 1.6.0_29-b11-402-11M3527)
>Reporter: Bruce A Johnson
>
> I've been having trouble getting BOBYQA to minimize a function (actually a
> non-linear least squares fit) so as one change I increased the number of
> interpolation points. It seems that anything larger than 2*dim+1 causes an
> error (typically at
> line 1662
>interpolationPoints.setEntry(nfm, ipt,
> interpolationPoints.getEntry(ipt, ipt));
> I'm guessing there is an off by one error in the translation from FORTRAN.
> Changing the BOBYQAOptimizerTest as follows (increasing number of
> interpolation points by one) will cause failures.
> Bruce
> Index:
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> ===
> ---
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (revision 1221065)
> +++
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (working copy)
> @@ -258,7 +258,7 @@
> //RealPointValuePair result = optim.optimize(10, func, goal,
> startPoint);
> final double[] lB = boundaries == null ? null : boundaries[0];
> final double[] uB = boundaries == null ? null : boundaries[1];
> -BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 1);
> +BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 2);
> RealPointValuePair result = optim.optimize(maxEvaluations, func,
> goal, startPoint, lB, uB);
> //System.out.println(func.getClass().getName() + " = "
> // + optim.getEvaluations() + " f(");
--
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
[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 i
[ 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
[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 i
[ 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
[jira] [Commented] (MATH-728) Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than 2*dim+1
[
https://issues.apache.org/jira/browse/MATH-728?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13173266#comment-13173266
]
Bruce A Johnson commented on MATH-728:
--
I, for one, am very happy to see BOBYQA in CM and will continue with "real
world" testing. If I find more issues I'll certainly report them, but so far
it's looking very promising with my applications.
> Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than
> 2*dim+1
> --
>
> Key: MATH-728
> URL: https://issues.apache.org/jira/browse/MATH-728
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 3.0
> Environment: Mac Java(TM) SE Runtime Environment (build
> 1.6.0_29-b11-402-11M3527)
>Reporter: Bruce A Johnson
>
> I've been having trouble getting BOBYQA to minimize a function (actually a
> non-linear least squares fit) so as one change I increased the number of
> interpolation points. It seems that anything larger than 2*dim+1 causes an
> error (typically at
> line 1662
>interpolationPoints.setEntry(nfm, ipt,
> interpolationPoints.getEntry(ipt, ipt));
> I'm guessing there is an off by one error in the translation from FORTRAN.
> Changing the BOBYQAOptimizerTest as follows (increasing number of
> interpolation points by one) will cause failures.
> Bruce
> Index:
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> ===
> ---
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (revision 1221065)
> +++
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (working copy)
> @@ -258,7 +258,7 @@
> //RealPointValuePair result = optim.optimize(10, func, goal,
> startPoint);
> final double[] lB = boundaries == null ? null : boundaries[0];
> final double[] uB = boundaries == null ? null : boundaries[1];
> -BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 1);
> +BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 2);
> RealPointValuePair result = optim.optimize(maxEvaluations, func,
> goal, startPoint, lB, uB);
> //System.out.println(func.getClass().getName() + " = "
> // + optim.getEvaluations() + " f(");
--
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
[jira] [Commented] (MATH-728) Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than 2*dim+1
[
https://issues.apache.org/jira/browse/MATH-728?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13173238#comment-13173238
]
Bruce A Johnson commented on MATH-728:
--
Thanks for checking this in, and it's worth noting that my function now
minimizes properly. It seems that with a large number of interpolation points
there was an out of bounds error, but even where that out of bounds error
wasn't thrown, the interpolation was set up wrong for the last few points,
causing a failure to converge. Others who have had trouble with convergence
would do well to recheck with this fix.
> Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than
> 2*dim+1
> --
>
> Key: MATH-728
> URL: https://issues.apache.org/jira/browse/MATH-728
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 3.0
> Environment: Mac Java(TM) SE Runtime Environment (build
> 1.6.0_29-b11-402-11M3527)
>Reporter: Bruce A Johnson
>
> I've been having trouble getting BOBYQA to minimize a function (actually a
> non-linear least squares fit) so as one change I increased the number of
> interpolation points. It seems that anything larger than 2*dim+1 causes an
> error (typically at
> line 1662
>interpolationPoints.setEntry(nfm, ipt,
> interpolationPoints.getEntry(ipt, ipt));
> I'm guessing there is an off by one error in the translation from FORTRAN.
> Changing the BOBYQAOptimizerTest as follows (increasing number of
> interpolation points by one) will cause failures.
> Bruce
> Index:
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> ===
> ---
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (revision 1221065)
> +++
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (working copy)
> @@ -258,7 +258,7 @@
> //RealPointValuePair result = optim.optimize(10, func, goal,
> startPoint);
> final double[] lB = boundaries == null ? null : boundaries[0];
> final double[] uB = boundaries == null ? null : boundaries[1];
> -BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 1);
> +BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 2);
> RealPointValuePair result = optim.optimize(maxEvaluations, func,
> goal, startPoint, lB, uB);
> //System.out.println(func.getClass().getName() + " = "
> // + optim.getEvaluations() + " f(");
--
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
[jira] [Commented] (MATH-728) Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than 2*dim+1
[
https://issues.apache.org/jira/browse/MATH-728?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13172888#comment-13172888
]
Bruce A Johnson commented on MATH-728:
--
Making this change fixes the problem and seems reasonable, but one of the
original translators (from FORTRAN to Java) should look this section of code
over.
@@ -1657,10 +1657,10 @@
final int tmp2 = jpt;
jpt = ipt - n;
ipt = tmp2;
-throw new PathIsExploredException(); // XXX
+//throw new PathIsExploredException(); // XXX
}
-interpolationPoints.setEntry(nfm, ipt,
interpolationPoints.getEntry(ipt, ipt));
-interpolationPoints.setEntry(nfm, jpt,
interpolationPoints.getEntry(jpt, jpt));
+interpolationPoints.setEntry(nfm, ipt-1,
interpolationPoints.getEntry(ipt, ipt-1));
+interpolationPoints.setEntry(nfm, jpt-1,
interpolationPoints.getEntry(jpt, jpt-1));
> Errors in BOBYQAOptimizer when numberOfInterpolationPoints is greater than
> 2*dim+1
> --
>
> Key: MATH-728
> URL: https://issues.apache.org/jira/browse/MATH-728
> Project: Commons Math
> Issue Type: Bug
>Affects Versions: 3.0
> Environment: Mac Java(TM) SE Runtime Environment (build
> 1.6.0_29-b11-402-11M3527)
>Reporter: Bruce A Johnson
>
> I've been having trouble getting BOBYQA to minimize a function (actually a
> non-linear least squares fit) so as one change I increased the number of
> interpolation points. It seems that anything larger than 2*dim+1 causes an
> error (typically at
> line 1662
>interpolationPoints.setEntry(nfm, ipt,
> interpolationPoints.getEntry(ipt, ipt));
> I'm guessing there is an off by one error in the translation from FORTRAN.
> Changing the BOBYQAOptimizerTest as follows (increasing number of
> interpolation points by one) will cause failures.
> Bruce
> Index:
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> ===
> ---
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (revision 1221065)
> +++
> src/test/java/org/apache/commons/math/optimization/direct/BOBYQAOptimizerTest.java
> (working copy)
> @@ -258,7 +258,7 @@
> //RealPointValuePair result = optim.optimize(10, func, goal,
> startPoint);
> final double[] lB = boundaries == null ? null : boundaries[0];
> final double[] uB = boundaries == null ? null : boundaries[1];
> -BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 1);
> +BOBYQAOptimizer optim = new BOBYQAOptimizer(2 * dim + 2);
> RealPointValuePair result = optim.optimize(maxEvaluations, func,
> goal, startPoint, lB, uB);
> //System.out.println(func.getClass().getName() + " = "
> // + optim.getEvaluations() + " f(");
--
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
