commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Phil Steitz <>
Subject Re: [math] Monitoring iterative algorithms
Date Sat, 10 Sep 2011 20:59:21 GMT
On 9/10/11 12:45 AM, S├ębastien Brisard wrote:
> 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.

I agree.  It might actually be best to just not catch the
MaxCountExceededException in the manager and let the enclosing class
decide what to throw (more or less how it works now with the
>> 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?

OK to start without the additional structure.   We may choose later
to add this.
>> 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.

I agree with this.

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

I would say go ahead and commit it and we can see more clearly how
it works with CG and other algorithms.  I am having a little
difficulty understanding separation of concerns in determining
stopping and it will make it clearer to see the fully integrated code.
>> 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?

Good question.  I think the setup above is nice and pretty much
complete.  I would say all of the events above *should* be fired by
classes that use a manager; but some implementations may choose not
to fire all of the events.  I would expect implementations that omit
events to document which ones are omitted.

> Thanks for your comments so far!
> S├ębastien
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message