Glas List: 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 
> (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
>
> _______________________________________________
> glas mailing list
> glas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/glas
>

-- 
==============================================
Look at our unique training program and
Register on-line at http://www.fft.be/?id=35
----------------------------------------------
Karl Meerbergen
Free Field Technologies
16 place de l'Université
B-1348 Louvain-la-Neuve - BELGIUM
Company Phone:  [phone]
Company Fax:    [phone]
Mobile Phone:   [phone]
Home Phone:     [phone]
mailto:Karl.Meerbergen_at_[hidden]
http://www.fft.be
==============================================