[petsc-users] Implementation of Anderson mixing

[Barry Smith]

> On Aug 22, 2016, at 7:36 AM, Jonas Mairhofer <mhofer at itt.uni-stuttgart.de> wrote:
> 
> Dear PETSc-Team,
> 
> I am having a bit of trouble understanding the way the Anderson mixing method is implemented inPETSc.
> 
> On the corresponding website (http://www.mcs.anl.gov/petsc/petsc-3.5/docs/manualpages/SNES/SNESAnderson.html) it says in the 
> "Option database" section 
> 
> X_{update} = X + \beta F

   This is wrong, it is the "mixing" parameter. I will fix it.
> 
> which looks to me as if the new solution is calculated from the old solution plus something which depends on the old residual F.
> 
> However, in the "Notes" section it says that the new solution is found by combining "m previous solutions" which I interpret as the last m values of X.
> 
> In most other sources on Anderson mixing (e.g. the original one referd to on the website mentioned above) the update procedure looks something like  
> 
> X^{k+1} = (1-\beta) \sum_{i=0}^{m} \alpha_i^k X^{k-m+1} + \beta \sum_{i=0}^m \alpha_i^k G(X^{k-m+i}) where G = F + X.
> 
> Therefore, the new value of X is calculated from the last m values of X and F.
> 
> Unfortunately, I was not able to understand and follow the actual source code in src/snes/impls/ngmres/anderson.c

  The computation of the \sum_{i=0}^{m} \alpha_i^k X^{k-m+1} and \sum_{i=0}^m \alpha_i^k G(X^{k-m+i} take place in

  146:     SNESNGMRESFormCombinedSolution_Private(snes,ivec,l,XM,FM,fMnorm,X,XA,FA);

in particular  the 

    ierr = VecMAXPY(XA,l,beta,Xdot);CHKERRQ(ierr); 

 (note this is NOT the same \beta it is more like the \alpha above).

    ierr = VecMAXPY(FA,l,beta,Fdot);CHKERRQ(ierr);

> 
> Could you please tell me whether the last values of X, F or both are used in the update scheme of PETSc's Anderson mixing implementation?

   Both are, see above.
> 
> And is \beta used in a "regular line search way" where X^{new} = X^{old} + \beta* "undamped update" 

No
> 
> or as in the equation above 
> 
> X^{new} = (1-\beta) \sum "function of last m X"   + \beta \sum "function of last m G"

Yes. 

142:       VecAXPY(XM,-ngmres->andersonBeta,FM);

> 
> which would explain to me why beta is not set via -snes_linesearch_damping but using the extra option  -snes_anderson_beta.
> 
> 
> Thank you very much for your help!
> Jonas