[jira] Created: (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

[jira] Created: (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

Gilles (Jira)
LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
-------------------------------------------------------------------------------------------

                 Key: MATH-464
                 URL: https://issues.apache.org/jira/browse/MATH-464
             Project: Commons Math
          Issue Type: Bug
    Affects Versions: 2.1
            Reporter: Michael Borcherds
            Priority: Critical


The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
(in GeoGebra)

The argument defaultMaximalIterationCount = 100 is being ignored

This is the version we are using:
http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java

    LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
   
        try {
                double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
        } catch (Exception ee) {
                ee.printStackTrace();
        }



class testFun implements UnivariateRealFunction {

    public double value(double x) throws FunctionEvaluationException {
    count ++;
        if (x>=0 && x<=5) return 0.2; else return 0;
    }

}


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

Reply | Threaded
Open this post in threaded view
|

[jira] Updated: (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

Gilles (Jira)

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

Phil Steitz updated MATH-464:
-----------------------------

    Fix Version/s: 2.2

Thanks for reporting this.

The problem here is not with the iteration count.  In the example above, only 26 iterations are executed and the method returns the correct value.  What is causing the number of function evaluations to be so large is that each iteration involves multiple function evaluations.   I need to dig more deeply into the algorithm to determine what (if anything) the problem is, but what is causing the high number of function evaluations is the following
{code}
// prepare next iteration
double ratio = FastMath.min(4, FastMath.pow(delta / limit, 0.5 / abscissas.length));
n = FastMath.max((int) (ratio * n), n + 1);
{code}

In the example, delta / limit becomes large, causing n to increase rapidly.  As n increases, the number of function evaluations increases.

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 2.2
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

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

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Phil Steitz commented on MATH-464:
----------------------------------

I am now thinking that this is not a bug, but a consequence of the fact that the integrand in the example is not at all well-approximated by a polynomial.  With a small-enough stepsize, the algorithm does converge, but requiring the large number of function evaluations above.  Here are some stepsize values for the example and the associated absolute error:

n 8 error 0.05738431110184819
n 28 error 0.027423287634332688
n 100 error 8.62162720248888E-5
n 249 error 5.308122631570711E-4
n 650 error 4.3582615516528367E-4
n 1641 error 2.519984967931377E-4
n 3829 error 5.838605030586419E-5
...
 n 1102593 error 6.71416523906343E-8

The last entry is from the last (26th) iteration.  I haven't verified the rationale for the updating formula for n above, but it does appear warranted in this case to increase n quickly as large n (= small stepsize) is required to get a decent estimate of the integral using Gaussian quadrature.


> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 2.2
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

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

Reply | Threaded
Open this post in threaded view
|

[jira] Commented: (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Luc Maisonobe commented on MATH-464:
------------------------------------

Perhaps we should also provide higher order formulas, using either a fixed set of precomputed constants or a way to compute the coefficients for any order.

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 2.2
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

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

Reply | Threaded
Open this post in threaded view
|

[jira] Updated: (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Phil Steitz updated MATH-464:
-----------------------------

    Fix Version/s:     (was: 2.2)
                   3.0

Moving to 3.0.  I don't think this is a bug, but points to a couple of possible enhancements:

1) higher order formulas (+0 on this suggestion from Luc - IMO the example and others like it are not suitable for Legendre-Gauss)
2) bound on the number of function evaluations (I vaguely recall us talking about this elsewhere, but can't find the reference.  If anyone else can, pls add.)

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 3.0
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

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

Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Luc Maisonobe commented on MATH-464:
------------------------------------

We restarted a thread about this a few days after the previous comment on this issue.
The thread can be read here: http://commons.markmail.org/thread/cajgm5lwphlse3lr

I think adding maxEvaluations while still preserving the existing maxIterations would be fine.

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 3.0
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
Reply | Threaded
Open this post in threaded view
|

[jira] [Issue Comment Edited] (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Luc Maisonobe edited comment on MATH-464 at 4/9/11 7:49 PM:
------------------------------------------------------------

We restarted a thread about this a few days after the previous comment on this issue.
The thread can be read here: http://markmail.org/thread/rnazrggnnuehz4qv

I think adding maxEvaluations while still preserving the existing maxIterations would be fine.

      was (Author: luc):
    We restarted a thread about this a few days after the previous comment on this issue.
The thread can be read here: http://commons.markmail.org/thread/cajgm5lwphlse3lr

I think adding maxEvaluations while still preserving the existing maxIterations would be fine.
 

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 3.0
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Luc Maisonobe commented on MATH-464:
------------------------------------

Coming back to this issue.

I would propose to follow the same pattern we used for root solvers: adding a maxEval parameter in the top level integrate interface declaration. So we would have the same kind of configuration, with tolerances set at integrator/solver level and maxEval and function pointer passed at integrate/solve method call.

Since we are just in the phase we change interfaces, this would be a good time to add this parameter.

Does this seems reasonable ?

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 3.0
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Phil Steitz commented on MATH-464:
----------------------------------

+1 for your suggestion, Luc.  Lets try to get this into 3.0.

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 3.0
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Resolved] (MATH-464) LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations

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

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

Luc Maisonobe resolved MATH-464.
--------------------------------

    Resolution: Fixed

Fixed in subversion repository as of r1160914.

The API of the integrators has been changed for consistency with solvers API. Now the main convergence parameters are set in the constructor and remain fixed, but a maximal number of function evaluation must be provided at each call to the integration method.

Thanks for the report

> LegendreGaussIntegrator ignores defaultMaximalIterationCount and does 38 million iterations
> -------------------------------------------------------------------------------------------
>
>                 Key: MATH-464
>                 URL: https://issues.apache.org/jira/browse/MATH-464
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.1
>            Reporter: Michael Borcherds
>            Priority: Critical
>             Fix For: 3.0
>
>   Original Estimate: 3h
>  Remaining Estimate: 3h
>
> The following code results in count = 37801710 which is effectively an infinite loop for typical functions we are using
> (in GeoGebra)
> The argument defaultMaximalIterationCount = 100 is being ignored
> This is the version we are using:
> http://www.geogebra.org/trac/browser/trunk/geogebra/org/apache/commons/math/analysis/integration/LegendreGaussIntegrator.java
>     LegendreGaussIntegrator gauss = new LegendreGaussIntegrator(5, 100);
>    
> try {
> double result = gauss.integrate(new testFun(), -10, 0.32462367623786328);
> } catch (Exception ee) {
> ee.printStackTrace();
> }
> class testFun implements UnivariateRealFunction {
>     public double value(double x) throws FunctionEvaluationException {
>     count ++;
>         if (x>=0 && x<=5) return 0.2; else return 0;
>     }
> }

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira