Anderson acceleration

[Pavel Solin]

Hi,

  Anderson acceleration (or mixing) is an acceleration technique for fixed-point

iteration methods for the solution of nonlinear equations. While standard 

fixed-point method uses only the last approximation to calculate the new one, 

mixing methods use last several approximations. For us this matters since

some nonlinear equations in Hermes (such as the Richards equation) are

solved using the fixed point iteration. Therefore the Anderson mixing will become 

part of modules that use the fixed point method.

I implemented the Anderson acceleration in the Online Lab 

http://lab.femhub.org/worksheets/497d61e1d28b45bca8b3a8a641867666/

and tested it on a few simple-minded scalar equations. For example for 

the function g(x) = 1/(1 + x*x) with initial guess 5.0 it reduced the number 

of iterations from 42 to 22. That was with beta = 1.0 and unrestricted 

"memory". With beta = 0.8 the number dropped to 11. I also looked at 

the influence of the "memory" on the number of iterations. Usually the

method performed best when I remembered just a few (2-3) last iterates.

Pavel

--
Pavel Solin
University of Nevada, Reno
Home page: http://hpfem.org/~pavel
Hermes: http://hpfem.org/
FEMhub: http://femhub.org/

[Pavel Solin]

On Sun, Jun 19, 2011 at 10:06 AM, Lukas Korous <lukas....@gmail.com> wrote:

Good stuff,

I will try to use this for the Euler equations.

Except that I have a mistake there, give me 30 minutes to 

fix it :)

Pavel 

Lukas

> --
> You received this message because you are subscribed to the Google Groups
> "hermes2d" group.
> To post to this group, send email to herm...@googlegroups.com.
> To unsubscribe from this group, send email to
> hermes2d+u...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/hermes2d?hl=en.
>
>

--
You received this message because you are subscribed to the Google Groups "hermes2d" group.
To post to this group, send email to herm...@googlegroups.com.
To unsubscribe from this group, send email to hermes2d+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/hermes2d?hl=en.

[Pavel Solin]

On Sun, Jun 19, 2011 at 12:14 PM, Lukas Korous <lukas....@gmail.com> wrote:

On Sun, Jun 19, 2011 at 5:45 PM, Pavel Solin <so...@unr.edu> wrote:
>
>
> On Sun, Jun 19, 2011 at 10:06 AM, Lukas Korous <lukas....@gmail.com>
> wrote:
>>
>> Good stuff,
>>
>> I will try to use this for the Euler equations.
>
> Except that I have a mistake there, give me 30 minutes to
> fix it :)

I am not planning to work on that in next week or more, take your time
:). But if the fix radically changes the reported usefulness in terms
of number of steps reduction, please post the new results.

Sure, now it is even faster, and less dependent on beta.

Instead of 42 iterations I get the following which 

pretty much resembles Newton:

step: 1 approximation: 0.0384615384615 residual: 4.96153846154

step: 2 approximation: 0.998522895126 residual: 0.960061356664

step: 3 approximation: 0.58464871603 residual: 0.258220667062

step: 4 approximation: 0.688665779792 residual: 0.0162944638023

step: 5 approximation: 0.682223732147 residual: 0.0002678805791

step: 6 approximation: 0.682327726016 residual: 2.00284064888e-07

step: 7 approximation: 0.682327803829 residual: 2.5293100947e-12

Done.

The Anderson technique in fact implements GMRES into 

the fixed-point iteration, and one can feel it. 

The URL is the same as before,

http://lab.femhub.org/worksheets/497d61e1d28b45bca8b3a8a641867666/.

Best,

Pavel

 

Thanks,
Lukas