commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hendriks, D." <D.Hendr...@tue.nl>
Subject RE: [math] puzzled by generics in root solvers
Date Wed, 06 Jul 2011 17:07:28 GMT
Hi all,

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. 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.

I think it would be preferable to not hardcode the PegasusSolver as 'fallback' bracketing
solver. 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.

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?

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). 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.

Question: what other solvers that are available maintain a bracketed solution, besides the
secant-based methods?

Best regards,
Dennis



________________________________________
Van: luc.maisonobe@free.fr [luc.maisonobe@free.fr]
Verzonden: dinsdag 5 juli 2011 22:39
Aan: Commons Developers List
Onderwerp: Re: [math] puzzled by generics in root solvers

Hi Gilles,

----- "Gilles Sadowski" <gilles@harfang.homelinux.org> a écrit :

> Hello.
>
> > [...]
> > >
> > > The purpose of the "BaseUnivariateRealSolver<T>" is to avoid code
> > > duplication in CM. It must be general enough so that CM
> developers
> > > should
> > > not implement an "AbstractXxxsolver" that would not inherit from
> it.
> >
> > OK, so I think we need to introduce slight changes.
> >
> > [...]
> > >
> > > > I need access to the
> > > > function and I need access to the counter. So i think I will
> add
> > > > some accessors for them. Does this seems reasonable to other
> > > > developers ?
> > >
> > > In refactoring the "solvers" package, I removed a lot of
> "protected"
> > > fields.
> > > The current design shows that they were not necessary. Also they
> are
> > > not
> > > desirable because they break encapsulation. I'd rather find a way
> to
> > > avoid
> > > accessors, and figure out why the new interface does not fit in
> the
> > > design;
> > > if we can change it to fit or if we can improve the design so that
> it
> > > fits...
> >
> > I'm still trying to find a way to solve my use case without adding
> these accessors, but up to now I failed.
> >
> > Here is my problem: we have introduced bracketed solvers that allow
> to drive the solver in selecting a specific side when converging close
> to a root. This is a very interesting feature as it really simplifies
> lots of top level management of epsilon values and small ugly tricks
> when the solver converges just on the wrong side from user point of
> view. The three new secant based solvers implement this feature
> autonomously, but it would be really interesting to have it available
> also for other regular solvers. So I started to implement a wrapper
> that would take a regular (non-bracketing) solver, use it to come
> close to a root and then add some checks and post-processing to
> slightly shift it to the right side in case the non-bracketing solver
> happens to have chosen the wrong side.
> >
> > At first, I thought this could be done as follows:
> >
> > public class BracketingWrapperSolver<FUNC extends
> UnivariateRealFunction>
> >     extends BaseAbstractUnivariateRealSolver<FUNC>
> >     implements BracketedUnivariateRealSolver<FUNC> {
> >
> >   private final BaseUnivariateRealSolver<FUNC> solver;
> >
> >   protected double doSolve() {
> >
> >     // call the underlying non-bracketing solver
> >     double x0 = solver.solve(getMaxEvaluations(), getFunction(),
> >                              getMin(), getMax(), getStartValue());
> >
> >     // create a bracketing solver for the very small neighborhood of
> the root
> >     PegasusSolver bracketing = new
> PegasusSolver(solver.getRelativeAccuracy(),
> >
> solver.getAbsoluteAccuracy());
> >
> >     // select the side
> >     bracketing.setAllowedSolutions(getAllowedSolutions());
> >
> >     // compute a safety margin
> >     // TODO: add a loop with incresing size and bracketing checks
> >     double margin = 10 * solver.getAbsoluteAccuracy();
> >
> >     // compute the root on the selected side
> >     return bracketing.solve(getMaxEvaluations() -
> solver.getEvaluations(),
> >                             getFunction(),
> >                             x0 - margin, x0 + margin, x0);
> >
> >   }
> >
> > }
> >
> > This does the trick, but needs access to the function thanks to a
> getFunction() accessor.
>
> I understand the idea from the coding point-of-view.
> But IIUC, I'm afraid that this whole class is rather contorted; and
> you did
> not show how a user would instantiate it. It seems that it would bring
> the
> "cumbersomeness" of generics back to the user level:
>
>   BracketedUnivariateRealSolver<DifferentiableUnivariateRealFunction>
> solver
>     = new
> BracketingWrapperSolver<DifferentiableUnivariateRealFunction>(new
> NewtonSolver());

Yes. We could also hide this by creating specialized class with
empty bodies and the generic parameter already instanciated, as you did
with the top level interfaces.

>
> If such a fine control ("AllowedSolutions") is a desirable/necessary
> feature, couldn't we directly add it at the level of the base class
> (and
> interface)?  I.e. the main "solve" method would become:
>
> public abstract class BaseAbstractUnivariateRealSolver<FUNC extends
> UnivariateRealFunction>
>     implements BaseUnivariateRealSolver<FUNC> {
>
>     // ...
>
>     public double solve(int maxEval, FUNC f,
>                         double min, double max, double startValue,
>                         AllowedSolutions solutionType) {
>         // Initialization.
>         setup(maxEval, f, min, max, startValue, solutionType);
>
>         // Perform computation.
>         final double baseRoot = doSolve();
>
>       if (solutionType == EITHER_SIDE ||
>             this instanceof BracketedUnivariateRealSolver) {
>             return baseRoot;
>       } else {
>             PegasusSolver bracketing = new
> PegasusSolver(relativeAccuracy,
>
> absoluteAccuracy);
>             double margin = 10 * absoluteAccuracy;
>             return bracketing.solve(getMaxEvaluations() -
> getEvaluations(), f,
>                                     baseRoot - margin, baseRoot +
> margin,
>                                     baseRoot, solutionType);
>         }
>     }
> }

Yes, it is a smarter solution than mine, I like it, thanks!

We should be careful when documenting this method, since it allows *all*
solvers to use the bracketing feature magically and without user help,
even the non-bracketing ones. I hope we can explain that without causing
headache to our users or raising question like "hey, but then what is the
difference between bracketing and non bracketing solvers?".

best regards,
Luc

>
> > [...]
>
>
> Best,
> 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