Actual source code: rqcg.c
slepc-3.11.2 2019-07-30
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: }