Boost logo

Glas :

[glas] Generic iterations

From: Peter Gottschling (pgottsch_at_[hidden])
Date: 2005-05-27 17:44:15

Hi Karl,

I looked at the Richardson iteration you checked in. There are a few
things I would make differently. I will first point out my ideas and
provide some code later (after a few iterations of discussion). The
operator and the right hand side vector are better passed as const&.
The latter can be used to create temporary vector(s) if needed. Then I
wouldn't compute the norm in the algorithm and compare it against a
tolerance. Instead, I would use a functor that determines when to stop
the iteration.

This behavior is already realized in the ITL implementation

In contrast to the ITL I wouldn't use a member function but call the
functor itself. This way it could also be a function. IMO counting the
iterations is part of the algorithms and is better done there. The
functor, say stop functor, must be an n-ary predicate. All information
that are available in the iteration should be passed to the stop
functor, like redisuum, number of iterations, preconditioned residuum.
Which of this informations is finally used to decide the stopping is
job of the stop functor and does not matter to the iterative process.
OTOH, information not needed in the algorithm shouldn't be computed
exclusively for the stop functor, e.g. if the algorithm does not need a
residuum then A, x, and b should be given to the stop functor and it
depends than on the implementation of the stop functor whether the
residuum is computed or not. Computing the residuum without ever using
it is a considerable waste of time; passing arguments by reference does
not cost much, if at all (in inline functions).

Data passed to the stop functor should be casted to const to make sure
that they are not unnecessarily changed.

 From the prospective of the iterative algorithms it is invisible
whether the stop functor uses an absolute criterion, like norm(r) <
eps, a relative criterion, like norm(r)/normr0 < eps, or some
combination of it. The number of iterations can also be taken into
account in different ways.

Of course, it is up to the stop functor, which norm is used.

Especially with high condition numbers it is possible that the residuum
is decreased by several orders of magnitude where the error (e=x-x* the
difference vector between the current approximation and the solution)
might still be as large as before or even larger. (If interest exist, I
can provide examples.) Error estimates in the energy norm are less
distorted and thus preferable for relative criteria, if available.
Also, error guesses on preconditioned values can be better if the
preconditioned system has a lower condition number as A (otherwise the
preconditioning isn't worth to be used). In particular with multi-level
preconditioners spectrally equivalent error estimations are possible,
i.e. the error guess decreases in the same speed as the real error from
the beginning.

To make a long story short, we shall not restrict ourselves to stop
criteria that always base on the residuum.

This topic is some steps beyond the scalar-like concepts. We should
include more people with experience in iterative algorithms to figure
out all needs of these algorithms need and how we can support it in the
most flexible way.

Peter Gottschling
Research Associate
Open Systems Laboratory
Indiana University
301i Lindley Hall
Bloomington, IN 47405
Tel.: +1 812 855-8898 Fax: +1 812 856 0853