Actual source code: rqcg.c

slepc-3.11.2 2019-07-30
Report Typos and Errors
  1: /*
  2:    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  3:    SLEPc - Scalable Library for Eigenvalue Problem Computations
  4:    Copyright (c) 2002-2019, Universitat Politecnica de Valencia, Spain

  6:    This file is part of SLEPc.
  7:    SLEPc is distributed under a 2-clause BSD license (see LICENSE).
  8:    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  9: */
 10: /*
 11:    SLEPc eigensolver: "rqcg"

 13:    Method: Rayleigh Quotient Conjugate Gradient

 15:    Algorithm:

 17:        Conjugate Gradient minimization of the Rayleigh quotient with
 18:        periodic Rayleigh-Ritz acceleration.

 20:    References:

 22:        [1] L. Bergamaschi et al., "Parallel preconditioned conjugate gradient
 23:            optimization of the Rayleigh quotient for the solution of sparse
 24:            eigenproblems", Appl. Math. Comput. 175(2):1694-1715, 2006.
 25: */

 27: #include <slepc/private/epsimpl.h>                /*I "slepceps.h" I*/

 29: PetscErrorCode EPSSolve_RQCG(EPS);

 31: typedef struct {
 32:   PetscInt nrest;         /* user-provided reset parameter */
 33:   PetscInt allocsize;     /* number of columns of work BV's allocated at setup */
 34:   BV       AV,W,P,G;
 35: } EPS_RQCG;

 37: PetscErrorCode EPSSetUp_RQCG(EPS eps)
 38: {
 40:   PetscInt       nmat;
 41:   EPS_RQCG       *ctx = (EPS_RQCG*)eps->data;

 44:   if (!eps->ishermitian || (eps->isgeneralized && !eps->ispositive)) SETERRQ(PetscObjectComm((PetscObject)eps),PETSC_ERR_SUP,"RQCG only works for Hermitian problems");
 45:   EPSSetDimensions_Default(eps,eps->nev,&eps->ncv,&eps->mpd);
 46:   if (!eps->max_it) eps->max_it = PetscMax(100,2*eps->n/eps->ncv);
 47:   if (!eps->which) eps->which = EPS_SMALLEST_REAL;
 48:   if (eps->which!=EPS_SMALLEST_REAL) SETERRQ(PetscObjectComm((PetscObject)eps),1,"Wrong value of eps->which");
 49:   if (!eps->extraction) {
 50:     EPSSetExtraction(eps,EPS_RITZ);
 51:   } else if (eps->extraction!=EPS_RITZ) SETERRQ(PetscObjectComm((PetscObject)eps),PETSC_ERR_SUP,"Unsupported extraction type");
 52:   if (eps->arbitrary) SETERRQ(PetscObjectComm((PetscObject)eps),PETSC_ERR_SUP,"Arbitrary selection of eigenpairs not supported in this solver");

 54:   if (!ctx->nrest) ctx->nrest = 20;

 56:   EPSAllocateSolution(eps,0);
 57:   EPS_SetInnerProduct(eps);

 59:   STGetNumMatrices(eps->st,&nmat);
 60:   if (!ctx->allocsize) {
 61:     ctx->allocsize = eps->mpd;
 62:     BVDuplicateResize(eps->V,eps->mpd,&ctx->AV);
 63:     PetscLogObjectParent((PetscObject)eps,(PetscObject)ctx->AV);
 64:     if (nmat>1) {
 65:       BVDuplicate(ctx->AV,&ctx->W);
 66:       PetscLogObjectParent((PetscObject)eps,(PetscObject)ctx->W);
 67:     }
 68:     BVDuplicate(ctx->AV,&ctx->P);
 69:     PetscLogObjectParent((PetscObject)eps,(PetscObject)ctx->P);
 70:     BVDuplicate(ctx->AV,&ctx->G);
 71:     PetscLogObjectParent((PetscObject)eps,(PetscObject)ctx->G);
 72:   } else if (ctx->allocsize!=eps->mpd) {
 73:     ctx->allocsize = eps->mpd;
 74:     BVResize(ctx->AV,eps->mpd,PETSC_FALSE);
 75:     if (nmat>1) {
 76:       BVResize(ctx->W,eps->mpd,PETSC_FALSE);
 77:     }
 78:     BVResize(ctx->P,eps->mpd,PETSC_FALSE);
 79:     BVResize(ctx->G,eps->mpd,PETSC_FALSE);
 80:   }
 81:   DSSetType(eps->ds,DSHEP);
 82:   DSAllocate(eps->ds,eps->ncv);
 83:   EPSSetWorkVecs(eps,1);
 84:   return(0);
 85: }

 87: /*
 88:    ExtractSubmatrix - Returns B = A(k+1:end,k+1:end).
 89: */
 90: static PetscErrorCode ExtractSubmatrix(Mat A,PetscInt k,Mat *B)
 91: {
 93:   PetscInt       j,m,n;
 94:   PetscScalar    *pA,*pB;

 97:   MatGetSize(A,&m,&n);
 98:   MatCreateSeqDense(PETSC_COMM_SELF,m-k,n-k,NULL,B);
 99:   MatDenseGetArray(A,&pA);
100:   MatDenseGetArray(*B,&pB);
101:   for (j=k;j<n;j++) {
102:     PetscMemcpy(pB+(j-k)*(m-k),pA+j*m+k,(m-k)*sizeof(PetscScalar));
103:   }
104:   MatDenseRestoreArray(A,&pA);
105:   MatDenseRestoreArray(*B,&pB);
106:   return(0);
107: }

109: PetscErrorCode EPSSolve_RQCG(EPS eps)
110: {
112:   EPS_RQCG       *ctx = (EPS_RQCG*)eps->data;
113:   PetscInt       i,j,k,ld,nv,ncv = eps->ncv,kini,nmat;
114:   PetscScalar    *C,*gamma,g,pap,pbp,pbx,pax,nu,mu,alpha,beta;
115:   PetscReal      resnorm,a,b,c,disc,t;
116:   PetscBool      reset;
117:   Mat            A,B,Q,Q1;
118:   Vec            v,av,bv,p,w=eps->work[0];

121:   DSGetLeadingDimension(eps->ds,&ld);
122:   STGetNumMatrices(eps->st,&nmat);
123:   STGetMatrix(eps->st,0,&A);
124:   if (nmat>1) { STGetMatrix(eps->st,1,&B); }
125:   else B = NULL;
126:   PetscMalloc1(eps->mpd,&gamma);

128:   kini = eps->nini;
129:   while (eps->reason == EPS_CONVERGED_ITERATING) {
130:     eps->its++;
131:     nv = PetscMin(eps->nconv+eps->mpd,ncv);
132:     DSSetDimensions(eps->ds,nv,0,eps->nconv,0);
133:     for (;kini<nv;kini++) { /* Generate more initial vectors if necessary */
134:       BVSetRandomColumn(eps->V,kini);
135:       BVOrthonormalizeColumn(eps->V,kini,PETSC_TRUE,NULL,NULL);
136:     }
137:     reset = (eps->its>1 && (eps->its-1)%ctx->nrest==0)? PETSC_TRUE: PETSC_FALSE;

139:     if (reset) {
140:       /* Prevent BVDotVec below to use B-product, restored at the end */
141:       BVSetMatrix(eps->V,NULL,PETSC_FALSE);

143:       /* Compute Rayleigh quotient */
144:       BVSetActiveColumns(eps->V,eps->nconv,nv);
145:       BVSetActiveColumns(ctx->AV,0,nv-eps->nconv);
146:       BVMatMult(eps->V,A,ctx->AV);
147:       DSGetArray(eps->ds,DS_MAT_A,&C);
148:       for (i=eps->nconv;i<nv;i++) {
149:         BVSetActiveColumns(eps->V,eps->nconv,i+1);
150:         BVGetColumn(ctx->AV,i-eps->nconv,&av);
151:         BVDotVec(eps->V,av,C+eps->nconv+i*ld);
152:         BVRestoreColumn(ctx->AV,i-eps->nconv,&av);
153:         for (j=eps->nconv;j<i-1;j++) C[i+j*ld] = PetscConj(C[j+i*ld]);
154:       }
155:       DSRestoreArray(eps->ds,DS_MAT_A,&C);
156:       DSSetState(eps->ds,DS_STATE_RAW);

158:       /* Solve projected problem */
159:       DSSolve(eps->ds,eps->eigr,eps->eigi);
160:       DSSort(eps->ds,eps->eigr,eps->eigi,NULL,NULL,NULL);
161:       DSSynchronize(eps->ds,eps->eigr,eps->eigi);

163:       /* Update vectors V(:,idx) = V * Y(:,idx) */
164:       DSGetMat(eps->ds,DS_MAT_Q,&Q);
165:       BVMultInPlace(eps->V,Q,eps->nconv,nv);
166:       ExtractSubmatrix(Q,eps->nconv,&Q1);
167:       BVMultInPlace(ctx->AV,Q1,0,nv-eps->nconv);
168:       MatDestroy(&Q);
169:       MatDestroy(&Q1);
170:       if (B) { BVSetMatrix(eps->V,B,PETSC_FALSE); }
171:     } else {
172:       /* No need to do Rayleigh-Ritz, just take diag(V'*A*V) */
173:       for (i=eps->nconv;i<nv;i++) {
174:         BVGetColumn(eps->V,i,&v);
175:         BVGetColumn(ctx->AV,i-eps->nconv,&av);
176:         MatMult(A,v,av);
177:         VecDot(av,v,eps->eigr+i);
178:         BVRestoreColumn(eps->V,i,&v);
179:         BVRestoreColumn(ctx->AV,i-eps->nconv,&av);
180:       }
181:     }

183:     /* Compute gradient and check convergence */
184:     k = -1;
185:     for (i=eps->nconv;i<nv;i++) {
186:       BVGetColumn(eps->V,i,&v);
187:       BVGetColumn(ctx->AV,i-eps->nconv,&av);
188:       BVGetColumn(ctx->G,i-eps->nconv,&p);
189:       if (B) {
190:         BVGetColumn(ctx->W,i-eps->nconv,&bv);
191:         MatMult(B,v,bv);
192:         VecWAXPY(p,-eps->eigr[i],bv,av);
193:         BVRestoreColumn(ctx->W,i-eps->nconv,&bv);
194:       } else {
195:         VecWAXPY(p,-eps->eigr[i],v,av);
196:       }
197:       BVRestoreColumn(eps->V,i,&v);
198:       BVRestoreColumn(ctx->AV,i-eps->nconv,&av);
199:       VecNorm(p,NORM_2,&resnorm);
200:       BVRestoreColumn(ctx->G,i-eps->nconv,&p);
201:       (*eps->converged)(eps,eps->eigr[i],0.0,resnorm,&eps->errest[i],eps->convergedctx);
202:       if (k==-1 && eps->errest[i] >= eps->tol) k = i;
203:     }
204:     if (k==-1) k = nv;
205:     (*eps->stopping)(eps,eps->its,eps->max_it,k,eps->nev,&eps->reason,eps->stoppingctx);

207:     /* The next lines are necessary to avoid DS zeroing eigr */
208:     DSGetArray(eps->ds,DS_MAT_A,&C);
209:     for (i=eps->nconv;i<k;i++) C[i+i*ld] = eps->eigr[i];
210:     DSRestoreArray(eps->ds,DS_MAT_A,&C);

212:     if (eps->reason == EPS_CONVERGED_ITERATING) {

214:       /* Search direction */
215:       for (i=0;i<nv-eps->nconv;i++) {
216:         BVGetColumn(ctx->G,i,&v);
217:         STMatSolve(eps->st,v,w);
218:         VecDot(w,v,&g);
219:         BVRestoreColumn(ctx->G,i,&v);
220:         beta = (!reset && eps->its>1)? g/gamma[i]: 0.0;
221:         gamma[i] = g;
222:         BVGetColumn(ctx->P,i,&v);
223:         VecAXPBY(v,1.0,beta,w);
224:         if (i+eps->nconv>0) {
225:           BVSetActiveColumns(eps->V,0,i+eps->nconv);
226:           BVOrthogonalizeVec(eps->V,v,NULL,NULL,NULL);
227:         }
228:         BVRestoreColumn(ctx->P,i,&v);
229:       }

231:       /* Minimization problem */
232:       for (i=eps->nconv;i<nv;i++) {
233:         BVGetColumn(eps->V,i,&v);
234:         BVGetColumn(ctx->AV,i-eps->nconv,&av);
235:         BVGetColumn(ctx->P,i-eps->nconv,&p);
236:         VecDot(av,v,&nu);
237:         VecDot(av,p,&pax);
238:         MatMult(A,p,w);
239:         VecDot(w,p,&pap);
240:         if (B) {
241:           BVGetColumn(ctx->W,i-eps->nconv,&bv);
242:           VecDot(bv,v,&mu);
243:           VecDot(bv,p,&pbx);
244:           BVRestoreColumn(ctx->W,i-eps->nconv,&bv);
245:           MatMult(B,p,w);
246:           VecDot(w,p,&pbp);
247:         } else {
248:           VecDot(v,v,&mu);
249:           VecDot(v,p,&pbx);
250:           VecDot(p,p,&pbp);
251:         }
252:         BVRestoreColumn(ctx->AV,i-eps->nconv,&av);
253:         a = PetscRealPart(pap*pbx-pax*pbp);
254:         b = PetscRealPart(nu*pbp-mu*pap);
255:         c = PetscRealPart(mu*pax-nu*pbx);
256:         t = PetscMax(PetscMax(PetscAbsReal(a),PetscAbsReal(b)),PetscAbsReal(c));
257:         if (t!=0.0) { a /= t; b /= t; c /= t; }
258:         disc = PetscSqrtReal(PetscAbsReal(b*b-4.0*a*c));
259:         if (b>=0.0 && a!=0.0) alpha = (b+disc)/(2.0*a);
260:         else if (b!=disc) alpha = 2.0*c/(b-disc);
261:         else alpha = 0;
262:         /* Next iterate */
263:         if (alpha!=0.0) {
264:           VecAXPY(v,alpha,p);
265:         }
266:         BVRestoreColumn(eps->V,i,&v);
267:         BVRestoreColumn(ctx->P,i-eps->nconv,&p);
268:         BVOrthonormalizeColumn(eps->V,i,PETSC_TRUE,NULL,NULL);
269:       }
270:     }

272:     EPSMonitor(eps,eps->its,k,eps->eigr,eps->eigi,eps->errest,nv);
273:     eps->nconv = k;
274:   }

276:   PetscFree(gamma);
277:   return(0);
278: }

280: static PetscErrorCode EPSRQCGSetReset_RQCG(EPS eps,PetscInt nrest)
281: {
282:   EPS_RQCG *ctx = (EPS_RQCG*)eps->data;

285:   ctx->nrest = nrest;
286:   return(0);
287: }

289: /*@
290:    EPSRQCGSetReset - Sets the reset parameter of the RQCG iteration. Every
291:    nrest iterations, the solver performs a Rayleigh-Ritz projection step.

293:    Logically Collective on EPS

295:    Input Parameters:
296: +  eps - the eigenproblem solver context
297: -  nrest - the number of iterations between resets

299:    Options Database Key:
300: .  -eps_rqcg_reset - Sets the reset parameter

302:    Level: advanced

304: .seealso: EPSRQCGGetReset()
305: @*/
306: PetscErrorCode EPSRQCGSetReset(EPS eps,PetscInt nrest)
307: {

313:   PetscTryMethod(eps,"EPSRQCGSetReset_C",(EPS,PetscInt),(eps,nrest));
314:   return(0);
315: }

317: static PetscErrorCode EPSRQCGGetReset_RQCG(EPS eps,PetscInt *nrest)
318: {
319:   EPS_RQCG *ctx = (EPS_RQCG*)eps->data;

322:   *nrest = ctx->nrest;
323:   return(0);
324: }

326: /*@
327:    EPSRQCGGetReset - Gets the reset parameter used in the RQCG method.

329:    Not Collective

331:    Input Parameter:
332: .  eps - the eigenproblem solver context

334:    Output Parameter:
335: .  nrest - the reset parameter

337:    Level: advanced

339: .seealso: EPSRQCGSetReset()
340: @*/
341: PetscErrorCode EPSRQCGGetReset(EPS eps,PetscInt *nrest)
342: {

348:   PetscUseMethod(eps,"EPSRQCGGetReset_C",(EPS,PetscInt*),(eps,nrest));
349:   return(0);
350: }

352: PetscErrorCode EPSReset_RQCG(EPS eps)
353: {
355:   EPS_RQCG       *ctx = (EPS_RQCG*)eps->data;

358:   BVDestroy(&ctx->AV);
359:   BVDestroy(&ctx->W);
360:   BVDestroy(&ctx->P);
361:   BVDestroy(&ctx->G);
362:   ctx->allocsize = 0;
363:   return(0);
364: }

366: PetscErrorCode EPSSetFromOptions_RQCG(PetscOptionItems *PetscOptionsObject,EPS eps)
367: {
369:   PetscBool      flg;
370:   PetscInt       nrest;

373:   PetscOptionsHead(PetscOptionsObject,"EPS RQCG Options");

375:     PetscOptionsInt("-eps_rqcg_reset","Reset parameter","EPSRQCGSetReset",20,&nrest,&flg);
376:     if (flg) { EPSRQCGSetReset(eps,nrest); }

378:   PetscOptionsTail();
379:   return(0);
380: }

382: PetscErrorCode EPSDestroy_RQCG(EPS eps)
383: {

387:   PetscFree(eps->data);
388:   PetscObjectComposeFunction((PetscObject)eps,"EPSRQCGSetReset_C",NULL);
389:   PetscObjectComposeFunction((PetscObject)eps,"EPSRQCGGetReset_C",NULL);
390:   return(0);
391: }

393: PetscErrorCode EPSView_RQCG(EPS eps,PetscViewer viewer)
394: {
396:   EPS_RQCG       *ctx = (EPS_RQCG*)eps->data;
397:   PetscBool      isascii;

400:   PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&isascii);
401:   if (isascii) {
402:     PetscViewerASCIIPrintf(viewer,"  reset every %D iterations\n",ctx->nrest);
403:   }
404:   return(0);
405: }

407: SLEPC_EXTERN PetscErrorCode EPSCreate_RQCG(EPS eps)
408: {
409:   EPS_RQCG       *rqcg;

413:   PetscNewLog(eps,&rqcg);
414:   eps->data = (void*)rqcg;

416:   eps->useds = PETSC_TRUE;
417:   eps->categ = EPS_CATEGORY_PRECOND;

419:   eps->ops->solve          = EPSSolve_RQCG;
420:   eps->ops->setup          = EPSSetUp_RQCG;
421:   eps->ops->setfromoptions = EPSSetFromOptions_RQCG;
422:   eps->ops->destroy        = EPSDestroy_RQCG;
423:   eps->ops->reset          = EPSReset_RQCG;
424:   eps->ops->view           = EPSView_RQCG;
425:   eps->ops->backtransform  = EPSBackTransform_Default;
426:   eps->ops->setdefaultst   = EPSSetDefaultST_GMRES;

428:   PetscObjectComposeFunction((PetscObject)eps,"EPSRQCGSetReset_C",EPSRQCGSetReset_RQCG);
429:   PetscObjectComposeFunction((PetscObject)eps,"EPSRQCGGetReset_C",EPSRQCGGetReset_RQCG);
430:   return(0);
431: }