xref: /petsc/src/snes/impls/ngmres/snesngmres.c (revision e4ed7901070ce1ca36eb7d68dd07557542e66e31)

#include <../src/snes/impls/ngmres/snesngmres.h>
#include <petscblaslapack.h>

#undef __FUNCT__
#define __FUNCT__ "SNESReset_NGMRES"
PetscErrorCode SNESReset_NGMRES(SNES snes)
{
  SNES_NGMRES   *ngmres = (SNES_NGMRES*) snes->data;
  PetscErrorCode ierr;

  PetscFunctionBegin;
  ierr = VecDestroyVecs(ngmres->msize, &ngmres->Fdot);CHKERRQ(ierr);
  ierr = VecDestroyVecs(ngmres->msize, &ngmres->Xdot);CHKERRQ(ierr);
  ierr = SNESLineSearchDestroy(&ngmres->additive_linesearch);CHKERRQ(ierr);

  PetscFunctionReturn(0);
}

#undef __FUNCT__
#define __FUNCT__ "SNESDestroy_NGMRES"
PetscErrorCode SNESDestroy_NGMRES(SNES snes)
{
  PetscErrorCode ierr;
  SNES_NGMRES *ngmres = (SNES_NGMRES*)snes->data;

  PetscFunctionBegin;
  ierr = SNESReset_NGMRES(snes);CHKERRQ(ierr);
  ierr = PetscFree5(ngmres->h, ngmres->beta, ngmres->xi, ngmres->fnorms, ngmres->q);CHKERRQ(ierr);
  ierr = PetscFree(ngmres->s);CHKERRQ(ierr);
#if PETSC_USE_COMPLEX
  ierr = PetscFree(ngmres->rwork);
#endif
  ierr = PetscFree(ngmres->work);
  ierr = PetscFree(snes->data);
  PetscFunctionReturn(0);
}

#undef __FUNCT__
#define __FUNCT__ "SNESSetUp_NGMRES"
PetscErrorCode SNESSetUp_NGMRES(SNES snes)
{
  SNES_NGMRES    *ngmres = (SNES_NGMRES *) snes->data;
  const char     *optionsprefix;
  PetscInt       msize,hsize;
  PetscErrorCode ierr;

  PetscFunctionBegin;
  ierr = SNESDefaultGetWork(snes,5);CHKERRQ(ierr);
  if (!ngmres->Xdot) {ierr = VecDuplicateVecs(snes->vec_sol,ngmres->msize,&ngmres->Xdot);CHKERRQ(ierr);}
  if (!ngmres->Fdot) {ierr = VecDuplicateVecs(snes->vec_sol,ngmres->msize,&ngmres->Fdot);CHKERRQ(ierr);}
  if (!ngmres->setup_called) {
    msize         = ngmres->msize;  /* restart size */
    hsize         = msize * msize;

    /* explicit least squares minimization solve */
    ierr = PetscMalloc5(hsize,PetscScalar,&ngmres->h,
                        msize,PetscScalar,&ngmres->beta,
                        msize,PetscScalar,&ngmres->xi,
                        msize,PetscReal,  &ngmres->fnorms,
                        hsize,PetscScalar,&ngmres->q);CHKERRQ(ierr);
    ngmres->nrhs = 1;
    ngmres->lda = msize;
    ngmres->ldb = msize;
    ierr = PetscMalloc(msize*sizeof(PetscScalar),&ngmres->s);CHKERRQ(ierr);
    ierr = PetscMemzero(ngmres->h,   hsize*sizeof(PetscScalar));CHKERRQ(ierr);
    ierr = PetscMemzero(ngmres->q,   hsize*sizeof(PetscScalar));CHKERRQ(ierr);
    ierr = PetscMemzero(ngmres->xi,  msize*sizeof(PetscScalar));CHKERRQ(ierr);
    ierr = PetscMemzero(ngmres->beta,msize*sizeof(PetscScalar));CHKERRQ(ierr);
    ngmres->lwork = 12*msize;
#if PETSC_USE_COMPLEX
    ierr = PetscMalloc(sizeof(PetscReal)*ngmres->lwork,&ngmres->rwork);
#endif
    ierr = PetscMalloc(sizeof(PetscScalar)*ngmres->lwork,&ngmres->work);
  }

  /* linesearch setup */
  ierr = SNESGetOptionsPrefix(snes, &optionsprefix);CHKERRQ(ierr);

  if (ngmres->additive) {
    ierr = SNESLineSearchCreate(((PetscObject)snes)->comm, &ngmres->additive_linesearch);CHKERRQ(ierr);
    ierr = SNESLineSearchSetSNES(ngmres->additive_linesearch, snes);CHKERRQ(ierr);
    ierr = SNESLineSearchSetType(ngmres->additive_linesearch, SNES_LINESEARCH_L2);CHKERRQ(ierr);
    ierr = SNESLineSearchAppendOptionsPrefix(ngmres->additive_linesearch, "additive_");CHKERRQ(ierr);
    ierr = SNESLineSearchAppendOptionsPrefix(ngmres->additive_linesearch, optionsprefix);CHKERRQ(ierr);
    ierr = SNESLineSearchSetFromOptions(ngmres->additive_linesearch);CHKERRQ(ierr);
  }

  ngmres->setup_called = PETSC_TRUE;
  PetscFunctionReturn(0);
}

#undef __FUNCT__
#define __FUNCT__ "SNESSetFromOptions_NGMRES"
PetscErrorCode SNESSetFromOptions_NGMRES(SNES snes)
{
  SNES_NGMRES   *ngmres = (SNES_NGMRES *) snes->data;
  PetscErrorCode ierr;
  PetscBool      debug;
  SNESLineSearch linesearch;
  PetscFunctionBegin;
  ierr = PetscOptionsHead("SNES NGMRES options");CHKERRQ(ierr);
  ierr = PetscOptionsBool("-snes_ngmres_additive", "Use additive variant vs. choice",    "SNES", ngmres->additive,  &ngmres->additive, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsBool("-snes_ngmres_anderson", "Use Anderson mixing storage",        "SNES", ngmres->anderson,  &ngmres->anderson, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsInt("-snes_ngmres_m",         "Number of directions",               "SNES", ngmres->msize,  &ngmres->msize, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsInt("-snes_ngmres_restart_it","Tolerance iterations before restart","SNES", ngmres->restart_it,  &ngmres->restart_it, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsBool("-snes_ngmres_monitor",  "Monitor actions of NGMRES",          "SNES", ngmres->monitor ? PETSC_TRUE: PETSC_FALSE, &debug, PETSC_NULL);CHKERRQ(ierr);
  if (debug) {
    ngmres->monitor = PETSC_VIEWER_STDOUT_(((PetscObject)snes)->comm);CHKERRQ(ierr);
  }
  ierr = PetscOptionsReal("-snes_ngmres_gammaA",   "Residual selection constant",   "SNES", ngmres->gammaA, &ngmres->gammaA, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsReal("-snes_ngmres_gammaC", "  Residual restart constant",     "SNES", ngmres->gammaC, &ngmres->gammaC, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsReal("-snes_ngmres_epsilonB", "Difference selection constant", "SNES", ngmres->epsilonB, &ngmres->epsilonB, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsReal("-snes_ngmres_deltaB",   "Difference residual selection constant", "SNES", ngmres->deltaB, &ngmres->deltaB, PETSC_NULL);CHKERRQ(ierr);
  ierr = PetscOptionsTail();CHKERRQ(ierr);
  if ((ngmres->gammaA > ngmres->gammaC) && (ngmres->gammaC > 2.)) ngmres->gammaC = ngmres->gammaA;

  /* set the default type of the line search if the user hasn't already. */
  if (!snes->linesearch) {
    ierr = SNESGetSNESLineSearch(snes, &linesearch);CHKERRQ(ierr);
    ierr = SNESLineSearchSetType(linesearch, SNES_LINESEARCH_BASIC);CHKERRQ(ierr);
  }
  PetscFunctionReturn(0);
}

#undef __FUNCT__
#define __FUNCT__ "SNESView_NGMRES"
PetscErrorCode SNESView_NGMRES(SNES snes, PetscViewer viewer)
{
  SNES_NGMRES   *ngmres = (SNES_NGMRES *) snes->data;
  PetscBool      iascii;
  PetscErrorCode ierr;

  PetscFunctionBegin;
  ierr = PetscTypeCompare((PetscObject) viewer, PETSCVIEWERASCII, &iascii);CHKERRQ(ierr);
  if (iascii) {

    ierr = PetscViewerASCIIPrintf(viewer, "  Number of stored past updates: %d\n", ngmres->msize);CHKERRQ(ierr);
    ierr = PetscViewerASCIIPrintf(viewer, "  Residual selection: gammaA=%1.0e, gammaC=%1.0e\n", ngmres->gammaA, ngmres->gammaC);CHKERRQ(ierr);
    ierr = PetscViewerASCIIPrintf(viewer, "  Difference restart: epsilonB=%1.0e, deltaB=%1.0e\n", ngmres->epsilonB, ngmres->deltaB);CHKERRQ(ierr);
  }
  PetscFunctionReturn(0);
}

#undef __FUNCT__
#define __FUNCT__ "SNESSolve_NGMRES"

PetscErrorCode SNESSolve_NGMRES(SNES snes)
{
  SNES_NGMRES        *ngmres = (SNES_NGMRES *) snes->data;
  /* present solution, residual, and preconditioned residual */
  Vec                 X, F, B, D, Y;

  /* candidate linear combination answers */
  Vec                 XA, FA, XM, FM, FPC;

  /* previous iterations to construct the subspace */
  Vec                 *Fdot = ngmres->Fdot;
  Vec                 *Xdot = ngmres->Xdot;

  /* coefficients and RHS to the minimization problem */
  PetscScalar         *beta = ngmres->beta;
  PetscScalar         *xi   = ngmres->xi;
  PetscReal           fnorm, fMnorm, fAnorm, ynorm, xnorm = 0.0;
  PetscReal           nu;
  PetscScalar         alph_total = 0.;
  PetscScalar         qentry;
  PetscInt            i, j, k, k_restart, l, ivec, restart_count = 0;

  /* solution selection data */
  PetscBool           selectA, selectRestart;
  PetscReal           dnorm, dminnorm, dcurnorm;
  PetscReal           fminnorm;

  SNESConvergedReason reason;
  PetscBool           lssucceed;
  PetscErrorCode      ierr;

  PetscFunctionBegin;
  /* variable initialization */
  snes->reason  = SNES_CONVERGED_ITERATING;
  X             = snes->vec_sol;
  F             = snes->vec_func;
  B             = snes->vec_rhs;
  XA            = snes->vec_sol_update;
  FA            = snes->work[0];
  D             = snes->work[1];

  /* work for the line search */
  Y             = snes->work[2];
  XM            = snes->work[3];
  FM            = snes->work[4];

  ierr = PetscObjectTakeAccess(snes);CHKERRQ(ierr);
  snes->iter = 0;
  snes->norm = 0.;
  ierr = PetscObjectGrantAccess(snes);CHKERRQ(ierr);

  /* initialization */

  /* r = F(x) */
  if (!snes->vec_func_init_set) {
    ierr = SNESComputeFunction(snes, X, F);CHKERRQ(ierr);
    if (snes->domainerror) {
      snes->reason = SNES_DIVERGED_FUNCTION_DOMAIN;
      PetscFunctionReturn(0);
    }
  } else {
    snes->vec_func_init_set = PETSC_FALSE;
  }

  if (!snes->norm_init_set) {
    ierr = VecNorm(F, NORM_2, &fnorm);CHKERRQ(ierr);
    if (PetscIsInfOrNanReal(fnorm)) SETERRQ(PETSC_COMM_SELF, PETSC_ERR_FP, "Infinite or not-a-number generated in function evaluation");
  } else {
    fnorm = snes->norm_init;
    snes->norm_init_set = PETSC_FALSE;
  }

  fminnorm = fnorm;
  /* nu = (r, r) */
  nu = fnorm*fnorm;

  /* q_{00} = nu  */
  Q(0,0) = nu;
  ngmres->fnorms[0] = fnorm;
  /* Fdot[0] = F */
  ierr = VecCopy(X, Xdot[0]);CHKERRQ(ierr);
  ierr = VecCopy(F, Fdot[0]);CHKERRQ(ierr);

  ierr = PetscObjectTakeAccess(snes);CHKERRQ(ierr);
  snes->norm = fnorm;
  ierr = PetscObjectGrantAccess(snes);CHKERRQ(ierr);
  SNESLogConvHistory(snes, fnorm, 0);
  ierr = SNESMonitor(snes, 0, fnorm);CHKERRQ(ierr);
  ierr = (*snes->ops->converged)(snes,0,0.0,0.0,fnorm,&snes->reason,snes->cnvP);CHKERRQ(ierr);
  if (snes->reason) PetscFunctionReturn(0);

  k_restart = 1;
  l = 1;
  for (k=1; k < snes->max_its+1; k++) {
    /* select which vector of the stored subspace will be updated */
    ivec = k_restart % ngmres->msize; /* replace the last used part of the subspace */

    /* Computation of x^M */
    if (snes->pc) {
      ierr = VecCopy(X, XM);CHKERRQ(ierr);
      ierr = SNESSetInitialFunction(snes->pc, F);CHKERRQ(ierr);
      ierr = SNESSetInitialFunctionNorm(snes->pc, fnorm);CHKERRQ(ierr);
      ierr = SNESSolve(snes->pc, B, XM);CHKERRQ(ierr);
      ierr = SNESGetConvergedReason(snes->pc,&reason);CHKERRQ(ierr);
      if (reason < 0 && reason != SNES_DIVERGED_MAX_IT) {
        snes->reason = SNES_DIVERGED_INNER;
        PetscFunctionReturn(0);
      }
      ierr = SNESGetFunction(snes->pc, &FPC, PETSC_NULL, PETSC_NULL);CHKERRQ(ierr);
      ierr = VecCopy(FPC, FM);CHKERRQ(ierr);
      ierr = SNESGetFunctionNorm(snes->pc, &fMnorm);CHKERRQ(ierr);
    } else {
      /* no preconditioner -- just take gradient descent with line search */
      ierr = VecCopy(F, Y);CHKERRQ(ierr);
      ierr = VecCopy(F, FM);CHKERRQ(ierr);
      ierr = VecCopy(X, XM);CHKERRQ(ierr);
      fMnorm = fnorm;
      ierr = SNESLineSearchApply(snes->linesearch,XM,FM,&fMnorm,Y);CHKERRQ(ierr);
      ierr = SNESLineSearchGetSuccess(snes->linesearch, &lssucceed);CHKERRQ(ierr);
      if (!lssucceed) {
        if (++snes->numFailures >= snes->maxFailures) {
          snes->reason = SNES_DIVERGED_LINE_SEARCH;
          PetscFunctionReturn(0);
        }
      }
    }

    /* r = F(x) */
    nu = fMnorm*fMnorm;
    if (fminnorm > fMnorm) fminnorm = fMnorm;  /* the minimum norm is now of F^M */

    /* construct the right hand side and xi factors */
    ierr = VecMDot(FM, l, Fdot, xi);CHKERRQ(ierr);

    for (i = 0; i < l; i++) {
      beta[i] = nu - xi[i];
    }

    /* construct h */
    for (j = 0; j < l; j++) {
      for (i = 0; i < l; i++) {
        H(i, j) = Q(i, j) - xi[i] - xi[j] + nu;
      }
    }

    if(l == 1) {
      /* simply set alpha[0] = beta[0] / H[0, 0] */
      beta[0] = beta[0] / H(0, 0);
    } else {
#ifdef PETSC_MISSING_LAPACK_GELSS
    SETERRQ(PETSC_COMM_SELF, PETSC_ERR_SUP, "NGMRES with LS requires the LAPACK GELSS routine.");
#else
    ngmres->m = PetscBLASIntCast(l);
    ngmres->n = PetscBLASIntCast(l);
    ngmres->info = PetscBLASIntCast(0);
    ngmres->rcond = -1.;
    ierr = PetscFPTrapPush(PETSC_FP_TRAP_OFF);CHKERRQ(ierr);
#ifdef PETSC_USE_COMPLEX
    LAPACKgelss_(&ngmres->m,
                 &ngmres->n,
                 &ngmres->nrhs,
                 ngmres->h,
                 &ngmres->lda,
                 ngmres->beta,
                 &ngmres->ldb,
                 ngmres->s,
                 &ngmres->rcond,
                 &ngmres->rank,
                 ngmres->work,
                 &ngmres->lwork,
                 ngmres->rwork,
                 &ngmres->info);
#else
    LAPACKgelss_(&ngmres->m,
                 &ngmres->n,
                 &ngmres->nrhs,
                 ngmres->h,
                 &ngmres->lda,
                 ngmres->beta,
                 &ngmres->ldb,
                 ngmres->s,
                 &ngmres->rcond,
                 &ngmres->rank,
                 ngmres->work,
                 &ngmres->lwork,
                 &ngmres->info);
#endif
    ierr = PetscFPTrapPop();CHKERRQ(ierr);
    if (ngmres->info < 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_LIB,"Bad argument to GELSS");
    if (ngmres->info > 0) SETERRQ(PETSC_COMM_SELF,PETSC_ERR_LIB,"SVD failed to converge");
#endif
    }

    alph_total = 0.;
    for (i = 0; i < l; i++) {
      alph_total += beta[i];
    }

    ierr = VecCopy(XM, XA);CHKERRQ(ierr);
    ierr = VecScale(XA, 1. - alph_total);CHKERRQ(ierr);

    ierr = VecMAXPY(XA, l, beta, Xdot);CHKERRQ(ierr);
    ierr = SNESComputeFunction(snes, XA, FA);CHKERRQ(ierr);
    ierr = VecNorm(FA, NORM_2, &fAnorm);CHKERRQ(ierr);

    /* differences for selection and restart */
    ierr=VecCopy(XA, D);CHKERRQ(ierr);
    ierr=VecAXPY(D, -1.0, X);CHKERRQ(ierr);
    ierr=VecNorm(D, NORM_2, &dnorm);CHKERRQ(ierr);
    dminnorm = -1.0;
    for(i=0;i<l;i++) {
      ierr=VecCopy(XA, D);CHKERRQ(ierr);
      ierr=VecAXPY(D, -1.0, Xdot[i]);CHKERRQ(ierr);
      ierr=VecNorm(D, NORM_2, &dcurnorm);CHKERRQ(ierr);
      if((dcurnorm < dminnorm) || (dminnorm < 0.0)) dminnorm = dcurnorm;
    }

    /* combination (additive) or selection (multiplicative) of the N-GMRES solution */
    if (ngmres->additive) {
      /* X = X + \lambda(XA - X) */
      if (ngmres->monitor) {
        ierr = PetscViewerASCIIPrintf(ngmres->monitor, "||F_A||_2 = %e, ||F_M||_2 = %e\n", fAnorm, fMnorm);CHKERRQ(ierr);
      }
      ierr = VecCopy(XA, Y);CHKERRQ(ierr);
      ierr = VecAYPX(Y, -1.0, X);CHKERRQ(ierr);
      ierr = SNESLineSearchApply(ngmres->additive_linesearch,X,F,&fnorm,Y);CHKERRQ(ierr);
      ierr = SNESLineSearchGetSuccess(ngmres->additive_linesearch, &lssucceed);CHKERRQ(ierr);
      if (!lssucceed) {
        if (++snes->numFailures >= snes->maxFailures) {
          snes->reason = SNES_DIVERGED_LINE_SEARCH;
          PetscFunctionReturn(0);
        }
      }
      ierr = SNESLineSearchGetNorms(ngmres->additive_linesearch, &xnorm, &fnorm, &ynorm);CHKERRQ(ierr);
      if (ngmres->monitor) {
        ierr = PetscViewerASCIIPrintf(ngmres->monitor, "Additive solution: ||F||_2 = %e\n", fnorm);CHKERRQ(ierr);
      }
      ierr = VecCopy(FA, F);CHKERRQ(ierr);
      ierr = VecCopy(XA, X);CHKERRQ(ierr);
    } else {
      selectA = PETSC_TRUE;
      /* Conditions for choosing the accelerated answer */
      /* Criterion A -- the norm of the function isn't increased above the minimum by too much */
      if (fAnorm >= ngmres->gammaA*fminnorm) {
        selectA = PETSC_FALSE;
      }
      /* Criterion B -- the choice of x^A isn't too close to some other choice */
     if (ngmres->epsilonB*dnorm<dminnorm || PetscSqrtReal(fnorm)<ngmres->deltaB*PetscSqrtReal(fminnorm)) {
      } else {
        selectA=PETSC_FALSE;
      }
      if (selectA) {
        if (ngmres->monitor) {
          ierr = PetscViewerASCIIPrintf(ngmres->monitor, "picked X_A, ||F_A||_2 = %e, ||F_M||_2 = %e\n", fAnorm, fMnorm);CHKERRQ(ierr);
        }
        /* copy it over */
        fnorm = fAnorm;
        nu = fnorm*fnorm;
        ierr = VecCopy(FA, F);CHKERRQ(ierr);
        ierr = VecCopy(XA, X);CHKERRQ(ierr);
      } else {
        if (ngmres->monitor) {
          ierr = PetscViewerASCIIPrintf(ngmres->monitor, "picked X_M, ||F_A||_2 = %e, ||F_M||_2 = %e\n", fAnorm, fnorm);CHKERRQ(ierr);
        }
        fnorm = fMnorm;
        nu = fnorm*fnorm;
        ierr = VecCopy(FM, F);CHKERRQ(ierr);
        ierr = VecCopy(XM, X);CHKERRQ(ierr);
      }
    }

    selectRestart = PETSC_FALSE;

    /* difference stagnation restart */
    if((ngmres->epsilonB*dnorm > dminnorm) && (PetscSqrtReal(fAnorm) > ngmres->deltaB*PetscSqrtReal(fminnorm))) {
      if (ngmres->monitor) {
        ierr = PetscViewerASCIIPrintf(ngmres->monitor, "difference restart: %e > %e\n", ngmres->epsilonB*dnorm, dminnorm);CHKERRQ(ierr);
      }
      selectRestart = PETSC_TRUE;
    }
    /* residual stagnation restart */
    if (PetscSqrtReal(fAnorm) > ngmres->gammaC*PetscSqrtReal(fminnorm)) {
      if (ngmres->monitor) {
        ierr = PetscViewerASCIIPrintf(ngmres->monitor, "residual restart: %e > %e\n", PetscSqrtReal(fAnorm), ngmres->gammaC*PetscSqrtReal(fminnorm));CHKERRQ(ierr);
      }
      selectRestart = PETSC_TRUE;
    }

    /* if the restart conditions persist for more than restart_it iterations, restart. */
    if (selectRestart) {
      restart_count++;
    } else {
      restart_count = 0;
    }

    /* restart after restart conditions have persisted for a fixed number of iterations */
    if (restart_count >= ngmres->restart_it) {
      if (ngmres->monitor){
        ierr = PetscViewerASCIIPrintf(ngmres->monitor, "Restarted at iteration %d\n", k_restart);CHKERRQ(ierr);
      }
      restart_count = 0;
      k_restart = 1;
      l = 1;
      /* q_{00} = nu */
      if (ngmres->anderson) {
        ngmres->fnorms[0] = fMnorm;
        nu = fMnorm*fMnorm;
        Q(0,0) = nu;
        /* Fdot[0] = F */
        ierr = VecCopy(XM, Xdot[0]);CHKERRQ(ierr);
        ierr = VecCopy(FM, Fdot[0]);CHKERRQ(ierr);
      } else {
        ngmres->fnorms[0] = fnorm;
        nu = fnorm*fnorm;
        Q(0,0) = nu;
        /* Fdot[0] = F */
        ierr = VecCopy(X, Xdot[0]);CHKERRQ(ierr);
        ierr = VecCopy(F, Fdot[0]);CHKERRQ(ierr);
      }
    } else {
      /* select the current size of the subspace */
      if (l < ngmres->msize) l++;
      k_restart++;
      /* place the current entry in the list of previous entries */
      if (ngmres->anderson) {
        ierr = VecCopy(FM, Fdot[ivec]);CHKERRQ(ierr);
        ierr = VecCopy(XM, Xdot[ivec]);CHKERRQ(ierr);
        ngmres->fnorms[ivec] = fMnorm;
        if (fminnorm > fMnorm) fminnorm = fMnorm;  /* the minimum norm is now of FM */
        for (i = 0; i < l; i++) {
          ierr = VecDot(FM, Fdot[i], &qentry);CHKERRQ(ierr);
          Q(i, ivec) = qentry;
          Q(ivec, i) = qentry;
        }
      } else {
        ierr = VecCopy(F, Fdot[ivec]);CHKERRQ(ierr);
        ierr = VecCopy(X, Xdot[ivec]);CHKERRQ(ierr);
        ngmres->fnorms[ivec] = fnorm;
        if (fminnorm > fnorm) fminnorm = fnorm;  /* the minimum norm is now of FA */
        for (i = 0; i < l; i++) {
          ierr = VecDot(F, Fdot[i], &qentry);CHKERRQ(ierr);
          Q(i, ivec) = qentry;
          Q(ivec, i) = qentry;
        }
      }
    }

    ierr = PetscObjectTakeAccess(snes);CHKERRQ(ierr);
    snes->iter = k;
    snes->norm = fnorm;
    ierr = PetscObjectGrantAccess(snes);CHKERRQ(ierr);
    SNESLogConvHistory(snes, snes->norm, snes->iter);
    ierr = SNESMonitor(snes, snes->iter, snes->norm);CHKERRQ(ierr);

    ierr = (*snes->ops->converged)(snes,snes->iter,xnorm,ynorm,fnorm,&snes->reason,snes->cnvP);CHKERRQ(ierr);
    if (snes->reason) PetscFunctionReturn(0);
  }
  snes->reason = SNES_DIVERGED_MAX_IT;
  PetscFunctionReturn(0);
}

/*MC
  SNESNGMRES - The Nonlinear Generalized Minimum Residual method.

   Level: beginner

   Options Database:
+  -snes_ngmres_additive   - Use a variant that line-searches between the candidate solution and the combined solution.
.  -snes_ngmres_anderson   - Use Anderson mixing NGMRES variant which combines candidate solutions instead of actual solutions.
.  -snes_ngmres_m          - Number of stored previous solutions and residuals.
.  -snes_ngmres_restart_it - Number of iterations the restart conditions hold before restart.
.  -snes_ngmres_gammaA     - Residual tolerance for solution selection between the candidate and combination.
.  -snes_ngmres_gammaC     - Residual tolerance for restart.
.  -snes_ngmres_epsilonB   - Difference tolerance between subsequent solutions triggering restart.
.  -snes_ngmres_deltaB     - Difference tolerance between residuals triggering restart.
.  -snes_ngmres_monitor    - Prints relevant information about the ngmres iteration.
-  -snes_ls <basic,basicnonorms,quadratic,critical> - Line search type.

   Notes:

   The N-GMRES method combines m previous solutions into a minimum-residual solution by solving a small linearized
   optimization problem at each iteration.

   References:

   "Krylov Subspace Acceleration of Nonlinear Multigrid with Application to Recirculating Flows", C. W. Oosterlee and T. Washio,
   SIAM Journal on Scientific Computing, 21(5), 2000.

   This is also the same as the algorithm called Anderson acceleration introduced in "D. G. Anderson. Iterative procedures for nonlinear integral equations.
   J. Assoc. Comput. Mach., 12:547–560, 1965."

.seealso: SNESCreate(), SNES, SNESSetType(), SNESType (for list of available types)
M*/

EXTERN_C_BEGIN
#undef __FUNCT__
#define __FUNCT__ "SNESCreate_NGMRES"
PetscErrorCode SNESCreate_NGMRES(SNES snes)
{
  SNES_NGMRES   *ngmres;
  PetscErrorCode ierr;

  PetscFunctionBegin;
  snes->ops->destroy        = SNESDestroy_NGMRES;
  snes->ops->setup          = SNESSetUp_NGMRES;
  snes->ops->setfromoptions = SNESSetFromOptions_NGMRES;
  snes->ops->view           = SNESView_NGMRES;
  snes->ops->solve          = SNESSolve_NGMRES;
  snes->ops->reset          = SNESReset_NGMRES;

  snes->usespc          = PETSC_TRUE;
  snes->usesksp         = PETSC_FALSE;

  ierr = PetscNewLog(snes, SNES_NGMRES, &ngmres);CHKERRQ(ierr);
  snes->data = (void*) ngmres;
  ngmres->msize = 30;

  if (!snes->tolerancesset) {
    snes->max_funcs = 30000;
    snes->max_its   = 10000;
  }

  ngmres->additive   = PETSC_FALSE;
  ngmres->anderson   = PETSC_FALSE;

  ngmres->additive_linesearch = PETSC_NULL;

  ngmres->restart_it = 2;
  ngmres->gammaA     = 2.0;
  ngmres->gammaC     = 2.0;
  ngmres->deltaB     = 0.9;
  ngmres->epsilonB   = 0.1;

  PetscFunctionReturn(0);
}
EXTERN_C_END