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


Groups > comp.soft-sys.math.mathematica > #4631

Re: FindRoot repeatedly evaluating function

From DrMajorBob <btreat1@austin.rr.com>
Newsgroups comp.soft-sys.math.mathematica
Subject Re: FindRoot repeatedly evaluating function
Date 2011-08-28 08:10 +0000
Organization Steven M. Christensen and Associates, Inc and MathTensor, Inc.
Message-ID <j3ct6b$5mq$1@smc.vnet.net> (permalink)
References <201108251105.HAA24905@smc.vnet.net>

Show all headers | View raw


> A colleague of mine came up with this reformulation. This is very clever
> since then you have access to the Jacobian.
>
> eqns = {Derivative[2, 0][x][S, p] - Derivative[1, 0][x][S, p] +
>       x[S, p] == 0, x[0, p] == 1, Derivative[1, 0][x][0, p] == p};
> seqns = {eqns, D[eqns, p]};
> svars = {x[S, p], Derivative[0, 1][x][S, p]};
>
> s = 0; e = 0;
> FindRoot[f[y], {y, 6}, Jacobian -> J[y]
>   , StepMonitor :> s++, EvaluationMonitor :> e++]

The first half of that DOES look clever, but the second has nothing to do  
with it.

What did you leave out?

Bobby

On Sat, 27 Aug 2011 07:18:24 -0500, Oliver Ruebenkoenig  
<ruebenko@wolfram.com> wrote:

>
>
> Hello Simon,
>
> On Thu, 25 Aug 2011, Simon Pearce wrote:
>
>> Hi Mathgroup,
>>
>> When I use FindRoot[f[y],y] I find that the inner function f is  
>> evaluated 3 or 4 times at each value of y (or at least very similar  
>> values), even if y is far from the root. This has obvious implications  
>> to the speed of my code.
>> Can anyone explain why this is the case, and tell me any way to stop it  
>> from repeatedly evaluating f? If I use f[a]:=f[a]=... then it uses the  
>> stored result, but I don't want to store thousands of such real valued  
>> expressions.
>>
>> The following simple code shows the essence of the problem, using Print  
>> to show where the function is evaluated and its value there.
>>
>> f[a_?NumericQ]:=Module[{sol},
>>  sol=NDSolve[{x''[S]-x'[S]+x[S]==0,x[0]==1,x'[0]==a},x,{S,0,10}][[1]];
>>  Print[{a,x[10]/.sol}]; x[10]/.sol ]
>> FindRoot[f[y],{y,6}]
>>
>> Thanks,
>> Simon Pearce
>> Postdoctoral Researcher
>> The Centre for Plant Integrative Biology
>> School of Biosciences
>> University of Nottingham
>>
>>
>> This message and any attachment are intended solely for the addressee  
>> and may contain confidential information. If you have received this  
>> message in error, please send it back to me, and immediately delete  
>> it.   Please do not use, copy or disclose the information contained in  
>> this message or in any attachment.  Any views or opinions expressed by  
>> the author of this email do not necessarily reflect the views of the  
>> University of Nottingham.  This message has been checked for viruses  
>> but the contents of an attachment may still contain software viruses  
>> which could damage your computer system: you are advised to perform  
>> your own checks. Email communications with the University of Nottingham  
>> may be monitored as permitted by UK legislation.
>>
>
> here are some ideas you may find useful.
>
> Here is a slight modification of your example:
>
> f[a_?NumericQ] :=
>   Module[{sol},
>    sol = NDSolve[{x''[S] - x'[S] + x[S] == 0, x[0] == 1, x'[0] == a},
>       x, {S, 0, 10}][[1]];
>    Print[InputForm[{a, x[10] /. sol}]]; x[10] /. sol]
>
> e = s = 0;
> FindRoot[f[y], {y, 6}
>   , StepMonitor :> s++, EvaluationMonitor :> e++
>   ]
>
> on my machine this gives e==17 and s==5.
>
> Sometimes the Jacobian that needs to be computed does not need to be
> updated every step.
>
> s = e = 0;
> FindRoot[f[y], {y, 6}, Method -> {"Newton", "UpdateJacobian" -> 2}
>   , StepMonitor :> s++, EvaluationMonitor :> e++]
>
> This gives me e==11 and s==4.
>
> Another thing to try is to use a finite difference approximation to the
> Jacobian that is of lover order.
>
> s = e = 0;
> FindRoot[f[y], {y, 6}
>   , Jacobian -> {"FiniteDifference", "DifferenceOrder" -> 2}
>   , StepMonitor :> s++, EvaluationMonitor :> e++]
>
> this gives me e==10 and s==3.
>
> Combining the two last approaches:
>
> s = e = 0;
> FindRoot[f[y], {y, 6}
>   , Method -> {"Newton", "UpdateJacobian" -> 2}
>   , Jacobian -> {"FiniteDifference", "DifferenceOrder" -> 2}
>   , StepMonitor :> s++, EvaluationMonitor :> e++]
>
> e==9 and s==3.
>
> Since you seem concerned about performance in both speed and memory, here
> is another idea.
>
> First you cloud call NDSolve like this
>
> if = First[
>    x /. NDSolve[{x''[S] - x'[S] + x[S] == 0, x[0] == 1, x'[0] == 1},
>      x, {S, 10, 10}]]
>
> {S,10,10} stores just the last value in the interpolation function.
>
> if["ValuesOnGrid"]
>
> Compare that to {S,0,10}.
>
> Next, you could separate the equation processing from the solution like
> so:
>
> nds = First@
>     NDSolve`ProcessEquations[{x''[S] - x'[S] + x[S] == 0, x[0] == 1,
>       x'[0] == 0}, {}, {S, 10, 10}];
>
> ClearAll[ff]
> With[{state = nds},
>   ff[a_?NumericQ] := (Module[{sol, tmp, tnds},
>      tnds = First@
>        NDSolve`Reinitialize[state, {x[0] == 1, x'[0] == a}];
>      NDSolve`Iterate[tnds];
>      sol = NDSolve`ProcessSolutions[tnds, 1];
>      tmp = x[10.] /. sol;
>      Print[InputForm[{a, tmp}]]; tmp])]
>
> s = 0; e = 0
> FindRoot[ff[y], {y, 6}
>   , StepMonitor :> s++, EvaluationMonitor :> e++]
>
> gives e==17 and s==5
>
> If you allow caching (May I ask why you do not?)
>
> ClearAll[ff]
> With[{state = nds},
>   ff[a_?NumericQ] := (ff[a] =
>      Module[{sol, tmp, tnds},
>       tnds = First@NDSolve`Reinitialize[state, {x[0] == 1, x'[0] == a}];
>       NDSolve`Iterate[tnds];
>       (*Print["sv: ",tnds@"SolutionVector"];*)
>       sol = NDSolve`ProcessSolutions[tnds, 1];
>       tmp = x[10.] /. sol;
>       Print[InputForm[{a, tmp}]]; tmp])]
>
> s = 0; e = 0
> FindRoot[ff[y], {y, 6}
>   , StepMonitor :> s++, EvaluationMonitor :> e++]
>
> s and e stay the same but as can be seen from the print statement those
> values are fetched. To be quite honest I have not looked at the code and
> do not know how the algorithm works exactly.
>
> Possibly another speed improvement is possible if you do not construct  
> the
> interpolation function but use the value from the tnds@"SolutionVector"
> directly.
>
> A colleague of mine came up with this reformulation. This is very clever
> since then you have access to the Jacobian.
>
> eqns = {Derivative[2, 0][x][S, p] - Derivative[1, 0][x][S, p] +
>       x[S, p] == 0, x[0, p] == 1, Derivative[1, 0][x][0, p] == p};
> seqns = {eqns, D[eqns, p]};
> svars = {x[S, p], Derivative[0, 1][x][S, p]};
>
> s = 0; e = 0;
> FindRoot[f[y], {y, 6}, Jacobian -> J[y]
>   , StepMonitor :> s++, EvaluationMonitor :> e++]
>
> gives
>
> s==3 and e==4
>
> So, if you have the Jacobian it is good to use it. Even if you do not  
> have
> the Jacobian you can sometimes say something about it's structure and  
> then
> use a SparseArray to convey that to FindRoot.
>
> Here are some links to the documentation
>
> (* FindRoot *)
> (*tutorial/UnconstrainedOptimizationNewtonsMethodRoot*)
> (*tutorial/UnconstrainedOptimizationIntroductionNonlinearEquations*)
> (*tutorial/UnconstrainedOptimizationSpecifyingDerivatives*)
>
>
> (* NDSolve`XY *)
> (* tutorial/NDSolveStateData *)
>
> Hope this helps.
>
> Oliver
>


-- 
DrMajorBob@yahoo.com

Back to comp.soft-sys.math.mathematica | Previous | Next | Find similar | Unroll thread


Thread

Re: FindRoot repeatedly evaluating function DrMajorBob <btreat1@austin.rr.com> - 2011-08-28 08:10 +0000

csiph-web