commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Sébastien Brisard <sebastien.bris...@m4x.org>
Subject Re: [math] Monitoring iterative algorithms
Date Sat, 10 Sep 2011 07:45:21 GMT
Thanks to you both for your review.

>
> 0) maybe incrementIterationCount in the manager should be called
> startIteration
>
OK
>
> 1) I guess TooManyEvaluations is the only thing left to throw, but
> MaxIterationsExceeded or even something new like IllegalIteration
> might make sense here (bad name, but once we introduce
> StoppingCriteria, something like that will make sense).
>
As I said, TooManyEvaluations was just temporary. For the time being,
I wanted to avoid the burden of defining a new exception with
localized messages, until we agreed on the general outline. I would
have defined a TooManyIterationsException in the end, but I think I
like Gilles solution much better. This would avoid defining a new
exception which would not be very instructive in any case. Much better
to define a particular exception for the particular type of iterative
algorithm.
>
> 2) It is tempting to go ahead and define the StoppingCondition and
> add it as a constructor parameter for the manager.
>
In fact, that's the purpose of the shouldStop() method. By default, it
returns false, but you can override it, which effectively allows you
to define a custom stopping criterion, without having to define a
general framework for stopping criteria, which previous discussions
showed it would be difficult to do... So I would say that we do not
need to add a new constructor parameter. What do you think?
>
> 3) Incrementor is a little crippled not exposing a constructor with
> the max  - could be we should add that and use it in the manager.
>
> 4) Similarly Incrementor could expose a hasMore() or somesuch, which
> would provide a meaningful default for shouldStop and also provide
> the basis for an iterationsExhausted event.
>
I should first mention that I've tried the present framework with
iterative linear solvers, just to check things worked properly. The
way I see things is as follows. As Gilles mentioned in a previous
thread, a default stopping criterion *should* be embedded into the
iterative algorithm. The reason for this is twofold: i. simplify most
user's life, and ii. allow for optimized implementation of these
stopping criteria. Regarding point ii., computation of the norm of the
residual comes as a by-product of the Conjugate Gradient method, while
evaluation by a custom stopping criterion would require an extra
matrix-vector product *at each iteration*.
Having in mind this, I decided that IterationManager.shouldStop()
should provide an *additional* stopping criterion, meaning that the
iterations are stopped if one of these conditions are fulfilled
1. maximum number of iterations reached ===> throws an exception,
already handled by the manager (nothing to do with shouldStop())
2. the default stopping criterion is fulfilled
3. manager.shouldStop() returns true (which it does not in the default
implementation, but that can be overriden).
It should be noted that bypassing the default stopping criterion
should be fairly easy, by providing "impossible" tolerance
requirements. Then only the custom criterion would be checked.

As I said, I've implemented this into my CG, it leads to fairly easily
readable code (but certainly improvable, too).
So what do you think of this way of thinking of stopping criteria? It
seems to me that it is a very general framework, since it does not
define any framework at all. It just opens a door to let some external
objects inform the Iterative Algorithm that it should stop. Would it
be regarded as acceptable design, or very ugly trick?
>
> 5) It may be extra noise and I know we need to be careful with this,
> but a fireIterationStarted source might be useful in some contexts.
>
If I understand correctly, here is what you would like to have in a
typical iterative algorithm
{code}
// Do initialization work
manager.fireInitializationEvent()
while(true){
    manager.fireIterationStarted()
    // do some work
    manager.fireIterationPerformed()
}
manager.fireTerminationEvent()
// do some closing work and return
{code}
I have no objection to that. However, do we require that *all* these
events are fired by *all* iterative algorithms, or only by iterative
algorithms where it is thought meaningful/useful?

Thanks for your comments so far!
Sébastien

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


Mime
View raw message