commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From luc.maison...@free.fr
Subject Re: [math] puzzled by generics in root solvers
Date Tue, 05 Jul 2011 11:25:27 GMT
Hi Gilles,

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

> Hi.
> 
> > 
> > I am a little puzzled by our use of generics in the
> analysis.solvers
> > package.
> > 
> > Hoping the following ASCII art will survive mail,
> 
> It's very nice! :-)
> 
> > here is a rough
> > overview (simplified) of what we have.
> > 
> >               BaseUnivariateRealSolver<FUNC>
> >                           |
> >         +-----------------+---------------------+
> >         |                                       |
> >         |                                       |
> >  UnivariateRealSolver,        
> BaseAbstractUnivariateRealSolver<FUNC>
> >    PolynomialSolver,                            |
> > DifferentiableUnivariateRealSolver              |
> >         |                                       |
> >         |                                       |
> >         +-----------------------+---------------+
> >                                 |
> >                                 |
> >            +--------------------+-----+----------------+
> >            |                          |                |
> > AbstractUnivariate...   AbstractPolynomial...
> AbstractDifferentiable...
> >            |                          |                |
> >      +-----+----------+               |                |
> >      |                |               |                |
> >  BrentSolver, BaseSecantSolver   LaguerreSolver    NewtonSolver
> >                      |
> >                      |
> >                      |
> >          BaseBracketedSecantSolver
> >                      |
> >                      |
> >                      |
> >       +--------------+---------------+
> >       |              |               |
> >       |              |               |
> >       |              |               |
> >   Illinois      Pegasus        RegulaFalsi
> > 
> > [...]
> > 
> > The first point is we use "UnivariateReal" both as the name of the
> > topmost level type when nothing is specified (just as in the name
> of
> > the level 0 interface and level 1b abstract class), and as the name
> > of generic functions, in parallel with polynomial and
> differentiable
> > functions. Shouldn't we have a different name for both notions ? We
> > could have for example UnivariateRealFunction at top level and
> > GeneralRealFunction at low level. This would help separate the
> > meanings from level 1b and level 2.
> 
> "UnivariateReal" is equivalent to your proposed "GeneralReal"
> "Polynomial" and "Differentiable" are sub-types.
> 
> > The second point is I don't understand the purpose of interfaces
> > from level 1a.
> 
> They are not really necessary. At first, I left them to avoid
> breaking
> compatibility.
> But the main usefulness is that API users can manipulate those
> "interface"
> types instead of "BaseAbstractUnivariateRealSolver<XxxFunction>" or
> "AbstractDifferentiableUnivariateRealSolver" which are more
> cumbersome
> to write. Also there is an asymmetry in the above two classes, due to
> the
> fact that they are not at the same level of the hierarchy.
> The generic base class is not supposed to be used by API users but
> only by
> CM developers (as in "AbstractDifferentiableUnivariateRealSolver").
> 
> > If on the one hand someone implements a solver by taking advantage
> > of the generified BaseAbstractUnivariateRealSolver we provide,
> these
> > interface merely force to add a redundant implement clause with
> > declarations like the ones found at level 2:
> > 
> >   AbstractXxxsolver extends BaseAbstractXxxSolver<XxxFunction>
> >                     implements  XxxSolver
> > 
> > instead of using only
> > 
> >   AbstractXxxsolver extends BaseAbstractXxxSolver<XxxFunction>
> 
> That's true: as indicated above, this "intricate" code is CM
> developer's
> problem. Applications that use CM should never contain any
> "AbstractXxx..."
> types; they should use the interfaces.

OK. This seems fair.

> 
> > If on the other hand someone implements a solver without taking
> > advantage of the generified BaseAbstractXxxSolver we provide, these
> > interface simply allow to write:
> > 
> >   AbstractXxxsolver implements  XxxSolver
> > 
> > instead of using only
> > 
> >   AbstractXxxsolver implements
> BaseUnivariateRealSolver<XxxFunction>
> 
> This is outside CM's realm. [I don't see why someone would inherit
> from a CM
> interface but not use the boiler-plate code in
> "BaseUnivariateRealSolver<T>".]

Mainly when you hit a limitation in the API like I did yesterday. See below.

> 
> 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 think removing the interfaces from level 1b would simplify the
> > architecture and help users understand. We would avoid the
> > losange-shape inheritance between levels 0, 1a/1b and 2.
> 
> We should probably make it clear that users should not use the
> generic
> base class nor the abstract classes, but only the interfaces; maybe
> adding
> in the Javadoc a statement like:
> /**
>  * [...]
>  *
>  * This class is not intended for use outside of the Commons Math
> library.
>  * @see UnivariateRealSolver
>  * @see PolynomialSolver
>  * @see DifferentiableUnivariateRealSolver
>  */

Good Idea. I'll add that.

> 
> > The third point is I think I messed thing when I inserted
> > BracketedUnivariateRealSolver interface back in the hierarchy a few
> > days ago by extending UnivariateRealSolver. I should probably have
> > generified it and have it extend BaseUnivariateRealSolver<FUNC
> > extends UnivariateRealSolver>, thus allowing to have bracketing
> > solvers also for polynomials and differentiable functions. Do you
> > agree with this ?
> 
> Yes.
> 
> > The fourth point is the generified BaseAbstractUnivariateRealSolver
> > we provide (level 1b, right of the losange). It forces to implement
> > a doSolve but in this method we cannot access the function itself
> > and we cannot reset the evaluations: the fields are private and
> have
> > no accessors, even protected, we can only call the function and
> > incrementing the evaluation at the same time, counting from a
> > setting the derived class cannot change.
> 
> It was done on purpose (so as to forbid evaluations that would not
> increment the counter).

I understand, but this is cumbersome for my needs.

> 
> > 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 though about overriding solve and pick up the function as follows, but I don't like the
idea, as it would force me to override all three implementations of solve, to make sure they
work as I want:

  public double solve(int maxEval, FUNC f, double min, double max, double startValue) {
      myFunction = f;  // store function in a local field, so doSolve can reuse it later
      super.solve(maxEval, f, min, max, startValue);
  }

I also thought about providing a local function like :
  new UnivariateRealFunction()  {
    public double value(double x) {
      return computeObjectiveValue(x);
    }
  }

But this would work only for UnivariateRealFunction, not for PolynomialFunction or DifferentiableUnivariateRealFunction.

For now, my preference is on getFunction, perhaps with a warning in the javadoc against using
it without also checking the calls count.

best regards,
Luc

> 
> > Well, sorry for this long message and the ugly picture. You have a
> > few hours to read it, as I will not be able to discuss in the few
> > next hours.
> > 
> > thanks for your attention ;-)
> 
> 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


Mime
View raw message