Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #13633 > unrolled thread

deterministic integration

Started byAlex Krasnov <akrasnov@eecs.berkeley.edu>
First post2013-02-27 08:03 +0000
Last post2013-03-04 03:57 +0000
Articles 4 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  deterministic integration Alex Krasnov <akrasnov@eecs.berkeley.edu> - 2013-02-27 08:03 +0000
    Re: deterministic integration daniel.lichtblau0@gmail.com - 2013-02-28 04:43 +0000
    Re: deterministic integration Alex Krasnov <akrasnov@eecs.berkeley.edu> - 2013-03-02 08:43 +0000
    Re: deterministic integration danl@wolfram.com - 2013-03-04 03:57 +0000

#13633 — deterministic integration

FromAlex Krasnov <akrasnov@eecs.berkeley.edu>
Date2013-02-27 08:03 +0000
Subjectdeterministic integration
Message-ID<kgkejq$4bc$1@smc.vnet.net>
This issue has already been discussed on this list, but the previous 
solutions are unsatisfactory. Integrate returns non-deterministic results 
depending on machine speed and kernel cache state. Example (Mathematica 
8.0.4):

In:	Assuming[Element[z, Reals], Integrate[1/Sqrt[x^2+y^2+z^2], {x, -1, 1}, {y, -1, 1}]]
Out:	-4*(z*ArcCot[z*Sqrt[2 + z^2]] + Log[1 - I*z] + Log[(1 + I*z)/(3 + z^2 + 2*Sqrt[2 + z^2])])

In:	Assuming[Element[z, Reals], Integrate[1/Sqrt[x^2+y^2+z^2], {x, -1, 1}, {y, -1, 1}]]
Out:	-4*(z*ArcCot[z*Sqrt[2 + z^2]] + Log[(1 + z^2)/(3 + z^2 + 2*Sqrt[2 + z^2])])

The previous solutions involve adjusting the machine speed and clearing 
the kernel cache before each evaluation. This strategy attempts to achieve 
the least transformed result, though this is presumably not guaranteed. 
Instead, how can one achieve the most transformed result? The behavior of 
Integrate appears to be similar to that of Refine, Simplify, FullSimplify. 
However, unlike the latter, Integrate does not expose a TimeConstraint 
option. How can one achieve the effect of TimeConstraint -> Infinity? Is 
the absence of this option related to the undecidability of Risch's 
algorithm or is the non-determinism entirely in a subsequent 
simplification phase?

Alex

[toc] | [next] | [standalone]


#13644

Fromdaniel.lichtblau0@gmail.com
Date2013-02-28 04:43 +0000
Message-ID<kgmn9s$8i5$1@smc.vnet.net>
In reply to#13633
On Wednesday, February 27, 2013 2:03:06 AM UTC-6, Alex Krasnov wrote:
> This issue has already been discussed on this list, but the previous 
> 
> solutions are unsatisfactory. Integrate returns non-deterministic results 
> 
> depending on machine speed and kernel cache state. Example (Mathematica 
> 
> 8.0.4):
> 
> 
> 
> In:	Assuming[Element[z, Reals], Integrate[1/Sqrt[x^2+y^2+z^2], {x, -1, 1}, {y, -1, 1}]]
> 
> Out:	-4*(z*ArcCot[z*Sqrt[2 + z^2]] + Log[1 - I*z] + Log[(1 + I*z)/(3 + z^2 + 2*Sqrt[2 + z^2])])
> 
> 
> 
> In:	Assuming[Element[z, Reals], Integrate[1/Sqrt[x^2+y^2+z^2], {x, -1, 1}, {y, -1, 1}]]
> 
> Out:	-4*(z*ArcCot[z*Sqrt[2 + z^2]] + Log[(1 + z^2)/(3 + z^2 + 2*Sqrt[2 + z^2])])
> 
> 
> 
> The previous solutions involve adjusting the machine speed and clearing 
> 
> the kernel cache before each evaluation. This strategy attempts to achieve 
> 
> the least transformed result, though this is presumably not guaranteed. 
> 
> Instead, how can one achieve the most transformed result? The behavior of 
> 
> Integrate appears to be similar to that of Refine, Simplify, FullSimplify. 
> 
> However, unlike the latter, Integrate does not expose a TimeConstraint 
> 
> option. How can one achieve the effect of TimeConstraint -> Infinity? Is 
> 
> the absence of this option related to the undecidability of Risch's 
> 
> algorithm or is the non-determinism entirely in a subsequent 
> 
> simplification phase?
> 
> 
> 
> Alex

Integrate uses a very large number of time-constrained computations, and some of them also use time constraints under the hood.

There is some amount of discussion of this here:

http://library.wolfram.com/infocenter/Conferences/5832/

A revised/updated version may be found here:

http://www.sigsam.org/cca/issues/issue175.html

See in particular section 5.7.

As for effectively setting all time constraints to infinity, this might by and large work (except there are also several places where Integrate code bypasses the evaluator for time-constraining).

Unprotect[TimeConstrained];
TimeConstrained[expr_,args___] := expr

This alters toe speed of your example above from 10 seconds to a minute; plan accordingly.

Daniel Lichtblau
Wolfram Research


[toc] | [prev] | [next] | [standalone]


#13680

FromAlex Krasnov <akrasnov@eecs.berkeley.edu>
Date2013-03-02 08:43 +0000
Message-ID<kgse47$j6t$1@smc.vnet.net>
In reply to#13633
On Wed, 27 Feb 2013, daniel.lichtblau0@gmail.com wrote:

> Integrate uses a very large number of time-constrained computations, and some of them also use time constraints under the hood.
>
> There is some amount of discussion of this here:
>
> http://library.wolfram.com/infocenter/Conferences/5832/
>
> A revised/updated version may be found here:
>
> http://www.sigsam.org/cca/issues/issue175.html
>
> See in particular section 5.7.

Thank you for the detailed information. One clarification: are time 
constraints and associated non-determinism limited to definite integration 
in the current implementation or is there an example from indefinite 
integration?

> As for effectively setting all time constraints to infinity, this might by and large work (except there are also several places where Integrate code bypasses the evaluator for time-constraining).
>
> Unprotect[TimeConstrained];
> TimeConstrained[expr_,args___] := expr
>
> This alters toe speed of your example above from 10 seconds to a minute; plan accordingly.

Interesting. On my system (Mathematica 8.0.4), this does not make a 
significant timing difference but does appear to achieve the desired 
result.

Alex

[toc] | [prev] | [next] | [standalone]


#13692

Fromdanl@wolfram.com
Date2013-03-04 03:57 +0000
Message-ID<kh163v$sa5$1@smc.vnet.net>
In reply to#13633
On Saturday, March 2, 2013 2:43:51 AM UTC-6, Alex Krasnov wrote:
> On Wed, 27 Feb 2013, d...@gmail.com wrote:
>
> > Integrate uses a very large number of time-constrained
> > computations, and some of them also use time constraints under the hood.
>
> > There is some amount of discussion of this here:
> 
> > http://library.wolfram.com/infocenter/Conferences/5832/
>
> > A revised/updated version may be found here:
>
> > http://www.sigsam.org/cca/issues/issue175.html
>
> > See in particular section 5.7.
>
>
> Thank you for the detailed information. One clarification: are time
> constraints and associated non-determinism limited to definite integration
> in the current implementation or is there an example from indefinite
> integration?

I don't have a handy example, but yes, I'm sure indefinite integration will also encounter this issue. That said, it will be far less common because indefinite integration does not use the assumptions mechanism and that is one significant area where timeouts are likely to happen. It also does not have any issue with path singularities, another area of frequent timeouts.


> > As for effectively setting all time constraints to infinity, this might by and large work (except there are also several places where Integrate code bypasses the evaluator for time-constraining).
>
> > Unprotect[TimeConstrained];
>
> > TimeConstrained[expr_,args___] := expr
>
> > This alters the speed of your example above from 10 seconds
> to a minute; plan accordingly.
>
> Interesting. On my system (Mathematica 8.0.4), this does not make a
> significant timing difference but does appear to achieve the desired
> result.
>
> Alex

This again is proibably subject to vagaries of machine speed. On my laptop using version 9 I see 28.7 vs. 87.2 seconds. Using version 8 both come in at around 22 seconds, each time starting in a fresh kernel. My guess is some key part succeeeds in 8 just fast enough to not send some part of Integrate down a different route.

Daniel Lichtblau
Wolfram Research

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web