Glas List: [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 
(http://www.osl.iu.edu/research/itl/).

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.

Cheers,
Peter
------------
Peter Gottschling
Research Associate
Open Systems Laboratory
Indiana University
301i Lindley Hall
Bloomington, IN 47405
Tel.: [phone]   Fax: [phone]
http://www.osl.iu.edu/~pgottsch