commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Luc Maisonobe <Luc.Maison...@free.fr>
Subject Re: [math] puzzled by generics in root solvers
Date Thu, 07 Jul 2011 08:05:13 GMT
Le 07/07/2011 09:35, Dennis Hendriks a écrit :
> Hi Gilles,
>
>  > We also do not have a clear separation between algorithms that take a
>  > bracket (e.g. "BrentSolver") and those that don't (e.g. "NewtonSolver").
>  > If the "solve" methods called by the user contains more parameters than
>  > needed by the algorithm implemented in the instance, they will be
>  > ignored. [In some sense, this is even worst than the bracketing "enum"
>  > case. However, in both cases we could maybe assume that the user has a
>  > minimal knowledge of the concept implemented in the class which he is
>  > using.
>
> Although this could be solved by adding very clear documentation, I
> think it would be about the worst thing we could do. Ignoring what the
> user asks for will confuse many users. While I don't like it that much,
> in this case it would be better to use a fallback bracketing solver to
> guarantee the solution that the user asked for.
>
>  > And, again, not specifying a parameter (in the call to "solve")
>  > won't do any harm ;-).]
>
> Sure. That is always a good idea, as it keeps backward compatibility.
>
>  > Yes, this is probably a good point.
>  > It could be solved by adding a "setBracketingSolver" method to the base
>  > class. If not explicitely specified, which one should be the default?
>
> Of the secant-based methods Pegasus claims the fastest convergence
> rates, so I would suggest that one. If the Brent solver is bracketing,
> as you suggest, then it should probably be adapted to implement the
> allowed solutions as well, and then maybe that one could be used.

Brent solver does not select a specific side of a solution.

>
>  > However, if we do want to provide the utility, maybe that it should be
>  > considered as such and _not_ as a solver by itself. E.g. some method
>  > "refine" in some utility class:
>
> This has the downside of having to handle the different cases in very
> place we use them. For instance, the ODE solver's state event detection
> would have to check whether it is a bracketing solver, and if not, use
> the refine method. Other uses would get a duplication of that block of
> code.

I think arguments on both sides are convincing. I like both the 
separation of concerns and the simplicity of a solve method with just 
additional allowedSide and optional bracketingSolver. I also dislike 
both my too complex class hierarchy with generics and hiding classes and 
the code duplication of a refine method.

Could we use some static methods in the existing 
UnivariateRealSolversUtils utility class ? It's not an ideal solution, 
but it may be a compromise.

>
>  > In principle, you are right.
>  > But in practice, we'd add an efficiency penalty to the algorithm by
>  > checking for unused arguments instead of simply ignoring them and
>  > assuming that the user knows what he does.
>
> I think we should make sure that if an argument can syntactically be
> provided, that it should be taken into account. If it can't be taken
> into account, an exception should be thrown, or the method should not
> have an overload with that argument. So, non-bracketed solvers should
> either:
> - not have an overload to specify the allowed solutions
> - have the overload and implement the desired behavior (fallback
> bracketed solver)
> - have the overload and throw exceptions if they don't support it.

I agree with this.

>
> Once again, ignoring a parameter may make the user think that (s)he gets
> solutions as requested, while the solutions don't actually guarantee
> this. This is very confusing for end users and will most likely result
> in bugs, especially from users who are not that familiar with the CM
> functionality.

Yes.

>
>  >> Question: what other solvers that are available maintain a bracketed
>  >> solution, besides the secant-based methods?
>  >
>  > "BrentSolver" (referring to Luc's nice ASCII art picture a few posts
>  > ago).
>
> I'm confused by your reference to the ASCII art picture. From the
> picture it can not be concluded whether the BrentSolver is bracketing or
> not. Also, the picture does not show all solvers, I think. It seems to
> only show enough examples to indicate the hierarchy.

Yes, it was slightly simplified.

> What is the
> relation between your answer and the picture?
>
> If the BrentSolver, and maybe other solvers, are bracketing, they should
> probably also implement the different allowed solutions directly.

Perhaps there is a confusion between solvers that maintain a bracketing 
search interval internally and solvers that select a solution at a 
specific end of the interval. Base secant maintain a pair of points but 
they may not bracket the root, Brent solver maintains and I think they 
bracket the root but don't select a specific side at the end, Illinois 
and Pegasus bracket the root and select the final solution according to 
the side.

I still hesitate to adapt Brent so it select the final point. This would 
be an interesting  feature, but it would not be the classical Brent 
solver anymore, it would be CM interpretation of Brent (but we could 
document it). Also as we needed an extra layer for the sake of other 
algorithms like Newton which clearly do not have pairs of points 
internally, I thought using this extra layer also on top of Brent was 
sufficient.

best regards,
Luc

>
> Best regards,
> Dennis
>
>
>
> Gilles Sadowski wrote:
>> Hello.
>>
>>> Here are my personal opinions on this entire discussion:
>>>
>>> I'm not sure I like the auto-magic under the hood conversion from
>>> unbracketed solver to bracketed solver.
>>
>> It's not really "under the hood", as the user must specify an enum
>> value to
>> get the "bracketing". The default ("ANY_SIDE") will return the original
>> output.
>>
>>> I think the BracketingWrapperSolver that was proposed would keep the
>>> clear distinction between the two.
>>> This new classs would then have the purpose to do the conversion.
>>> This takes the magic out of the process.
>>> The new class has a very clear purpose that could be easily explained.
>>> It is also a matter of separation of concerns.
>>> Furthermore, using a non-bracketed algorithm you would expect to get
>>> non-bracketed solutions.
>>> Using the auto-magic conversion to bracketed solutions may change the
>>> properties of the algorithms.
>>> I also think it is important to have a clear separation by means of
>>> an interface or base class to separate bracketing algorithms from
>>> non-bracketing algorithms.
>>
>> Really, there is no mixing (cf. above).
>> As a matter of principle, I'd agree with you on having another class etc.
>> But in the current design, this leads to other drawbacks, as this
>> discussion
>> has shown. This design has eliminated shortcomings of the previous
>> one, but
>> it might not be good enough. However, as it is, the
>> "BracketingWrapperSolver"
>> is most probably not the optimal solution.
>>
>> We also do not have a clear separation between algorithms that take a
>> bracket (e.g. "BrentSolver") and those that don't (e.g. "NewtonSolver").
>> If the "solve" methods called by the user contains more parameters than
>> needed by the algorithm implemented in the instance, they will be
>> ignored.
>> [In some sense, this is even worst than the bracketing "enum" case.
>> However,
>> in both cases we could maybe assume that the user has a minimal
>> knowledge of
>> the concept implemented in the class which he is using. And, again, not
>> specifying a parameter (in the call to "solve") won't do any harm ;-).]
>>
>>> I think it would be preferable to not hardcode the PegasusSolver as
>>> 'fallback' bracketing solver.
>>
>> Yes, this is probably a good point.
>> It could be solved by adding a "setBracketingSolver" method to the base
>> class. If not explicitely specified, which one should be the default?
>>
>>> It would be better to have a two parameter version of the
>>> BracketingWrapperSolver constructor:
>>> an instance of the non-bracketing solver, and an instance of the
>>> fallback bracketing solver.
>>> A one argument constructor could be added that does use the Pegasus
>>> as default.
>>> There were also some numbers hard-coded. It would be preferable to
>>> have them configurable.
>>
>> Another reason that I don't like this class is that it is somehow a
>> user-level utility. Let's say that CM provides solvers; some are
>> bracketing,
>> some not. We'd say: "If you need a bracketing one, then use a bracketing
>> one."
>> Adding this interface plus an implementing class, plus three
>> interfaces and
>> three classes to hide the generic parameter is, IMHO, a bit too much to
>> support for this kind of syntactic sugar.
>>
>> However, if we do want to provide the utility, maybe that it should be
>> considered
>> as such and _not_ as a solver by itself. E.g. some method "refine" in
>> some
>> utility class:
>>
>> public static double refine(UnivariateRealFunction f,
>> double baseRoot,
>> BracketingSolver solver,
>> double epsilon,
>> AllowedSolutions solutionType) {
>> // ...
>> }
>> where "baseRoot" is the root to refine (and we don't care how it was
>> obtained).
>>
>>> I'm not sure if it is easy to do, but I think it would be better to
>>> check if it is necessary to use the 'fallback' bracketing solver.
>>> If a non-bracketing solver already returned a solution that is on a
>>> valid side,
>>> then that answer should be used, and the use of the fallback solver
>>> should be avoided.
>>> I think we can do this by evaluating the function that the returned
>>> solution and the
>>> absolute tolerance before or after it (depending on the requested
>>> solution).
>>> Also, the found solution is extended on both sides to obtain an
>>> interval,
>>> which is then passed to the bracketing solver. If there is another
>>> root at the 'wrong'
>>> side of the first solution, can we guarantee that the correct side is
>>> found?
>>> Maybe we should only extend it to the direction where we need to find
>>> the new bracketed solution?
>>
>> Indeed, these are good questions. Once we agree on the interface, they
>> should
>> probably be the next steps to improve the functionality.
>>
>>> I kind of like AllowedSolutions as argument to the solve(...) method.
>>> I think it would be an improvement over a setAllowedSolutions, as it
>>> would make the feature more prominent.
>>> A version of the method without the argument should have the
>>> backwards compatible behavior of
>>> EITHER_SIDE (ANY_SIDE).
>>
>> Indeed, that's what is supposed to happen with the (untested) code I had
>> proposed.
>>
>>> Either non-bracketing solvers should not have to implement the
>>> extended version of the method, or they
>>> should throw UnsupportedExceptions for solutions that they can not
>>> guarantee.
>>
>> In principle, you are right.
>> But in practice, we'd add an efficiency penalty to the algorithm by
>> checking
>> for unused arguments instead of simply ignoring them and assuming that
>> the
>> user knows what he does.
>>
>>> Question: what other solvers that are available maintain a bracketed
>>> solution, besides the secant-based methods?
>>
>> "BrentSolver" (referring to Luc's nice ASCII art picture a few posts
>> ago).
>>
>>
>> Best regards,
>> Gilles
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
>> For additional commands, e-mail: dev-help@commons.apache.org
>>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


Mime
View raw message