## Glas :## [glas] Generic iterations |

**From:** Peter Gottschling (*pgottsch_at_[hidden]*)

**Date:** 2005-05-27 17:44:15

**Next message:**Karl Meerbergen: "Re: [glas] Generic iterations"**Previous message:**Toon Knapen: "Re: [glas] pure algebraic concepts cfr additive"**Next in thread:**Karl Meerbergen: "Re: [glas] Generic iterations"**Reply:**Karl Meerbergen: "Re: [glas] Generic iterations"

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.: +1 812 855-8898 Fax: +1 812 856 0853

http://www.osl.iu.edu/~pgottsch

**Next message:**Karl Meerbergen: "Re: [glas] Generic iterations"**Previous message:**Toon Knapen: "Re: [glas] pure algebraic concepts cfr additive"**Next in thread:**Karl Meerbergen: "Re: [glas] Generic iterations"**Reply:**Karl Meerbergen: "Re: [glas] Generic iterations"