Boost logo

Glas :

Re: [glas] Generic iterations

From: Karl Meerbergen (Karl.Meerbergen_at_[hidden])
Date: 2005-05-30 01:34:55

Peter Gottschling wrote:

> 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 code was just meant as an illustration of the concepts. A lot has
to be changed to make it a practical code, but therefore we need to
introduce a few more concepts I think.
Using the right-hand side vector to store the residual is not bad
because it saves the creation of an auxiliary vector.

> 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.
> Cheers,
> Peter
> ------------
> 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
> _______________________________________________
> glas mailing list
> glas_at_[hidden]

Look at our unique training program and
Register on-line at
Karl Meerbergen
Free Field Technologies
16 place de l'Université
B-1348 Louvain-la-Neuve - BELGIUM
Company Phone:  +32 10 45 12 26
Company Fax:    +32 10 45 46 26
Mobile Phone:   +32 474 26 66 59
Home Phone:     +32 2 306 38 10