Actual source code: stcg.c
2: #include <../src/ksp/ksp/impls/cg/stcg/stcgimpl.h>
4: #define STCG_PRECONDITIONED_DIRECTION 0
5: #define STCG_UNPRECONDITIONED_DIRECTION 1
6: #define STCG_DIRECTION_TYPES 2
8: static const char *DType_Table[64] = {"preconditioned", "unpreconditioned"};
10: static PetscErrorCode KSPCGSolve_STCG(KSP ksp)
11: {
12: #if defined(PETSC_USE_COMPLEX)
13: SETERRQ(PetscObjectComm((PetscObject)ksp), PETSC_ERR_SUP, "STCG is not available for complex systems");
14: #else
15: KSPCG_STCG *cg = (KSPCG_STCG *)ksp->data;
16: Mat Qmat, Mmat;
17: Vec r, z, p, d;
18: PC pc;
19: PetscReal norm_r, norm_d, norm_dp1, norm_p, dMp;
20: PetscReal alpha, beta, kappa, rz, rzm1;
21: PetscReal rr, r2, step;
22: PetscInt max_cg_its;
23: PetscBool diagonalscale;
25: /***************************************************************************/
26: /* Check the arguments and parameters. */
27: /***************************************************************************/
29: PCGetDiagonalScale(ksp->pc, &diagonalscale);
33: /***************************************************************************/
34: /* Get the workspace vectors and initialize variables */
35: /***************************************************************************/
37: r2 = cg->radius * cg->radius;
38: r = ksp->work[0];
39: z = ksp->work[1];
40: p = ksp->work[2];
41: d = ksp->vec_sol;
42: pc = ksp->pc;
44: PCGetOperators(pc, &Qmat, &Mmat);
46: VecGetSize(d, &max_cg_its);
47: max_cg_its = PetscMin(max_cg_its, ksp->max_it);
48: ksp->its = 0;
50: /***************************************************************************/
51: /* Initialize objective function and direction. */
52: /***************************************************************************/
54: cg->o_fcn = 0.0;
56: VecSet(d, 0.0); /* d = 0 */
57: cg->norm_d = 0.0;
59: /***************************************************************************/
60: /* Begin the conjugate gradient method. Check the right-hand side for */
61: /* numerical problems. The check for not-a-number and infinite values */
62: /* need be performed only once. */
63: /***************************************************************************/
65: VecCopy(ksp->vec_rhs, r); /* r = -grad */
66: VecDot(r, r, &rr); /* rr = r^T r */
67: KSPCheckDot(ksp, rr);
69: /***************************************************************************/
70: /* Check the preconditioner for numerical problems and for positive */
71: /* definiteness. The check for not-a-number and infinite values need be */
72: /* performed only once. */
73: /***************************************************************************/
75: KSP_PCApply(ksp, r, z); /* z = inv(M) r */
76: VecDot(r, z, &rz); /* rz = r^T inv(M) r */
77: if (PetscIsInfOrNanScalar(rz)) {
78: /*************************************************************************/
79: /* The preconditioner contains not-a-number or an infinite value. */
80: /* Return the gradient direction intersected with the trust region. */
81: /*************************************************************************/
83: ksp->reason = KSP_DIVERGED_NANORINF;
84: PetscInfo(ksp, "KSPCGSolve_STCG: bad preconditioner: rz=%g\n", (double)rz);
86: if (cg->radius != 0) {
87: if (r2 >= rr) {
88: alpha = 1.0;
89: cg->norm_d = PetscSqrtReal(rr);
90: } else {
91: alpha = PetscSqrtReal(r2 / rr);
92: cg->norm_d = cg->radius;
93: }
95: VecAXPY(d, alpha, r); /* d = d + alpha r */
97: /***********************************************************************/
98: /* Compute objective function. */
99: /***********************************************************************/
101: KSP_MatMult(ksp, Qmat, d, z);
102: VecAYPX(z, -0.5, ksp->vec_rhs);
103: VecDot(d, z, &cg->o_fcn);
104: cg->o_fcn = -cg->o_fcn;
105: ++ksp->its;
106: }
107: return 0;
108: }
110: if (rz < 0.0) {
111: /*************************************************************************/
112: /* The preconditioner is indefinite. Because this is the first */
113: /* and we do not have a direction yet, we use the gradient step. Note */
114: /* that we cannot use the preconditioned norm when computing the step */
115: /* because the matrix is indefinite. */
116: /*************************************************************************/
118: ksp->reason = KSP_DIVERGED_INDEFINITE_PC;
119: PetscInfo(ksp, "KSPCGSolve_STCG: indefinite preconditioner: rz=%g\n", (double)rz);
121: if (cg->radius != 0.0) {
122: if (r2 >= rr) {
123: alpha = 1.0;
124: cg->norm_d = PetscSqrtReal(rr);
125: } else {
126: alpha = PetscSqrtReal(r2 / rr);
127: cg->norm_d = cg->radius;
128: }
130: VecAXPY(d, alpha, r); /* d = d + alpha r */
132: /***********************************************************************/
133: /* Compute objective function. */
134: /***********************************************************************/
136: KSP_MatMult(ksp, Qmat, d, z);
137: VecAYPX(z, -0.5, ksp->vec_rhs);
138: VecDot(d, z, &cg->o_fcn);
139: cg->o_fcn = -cg->o_fcn;
140: ++ksp->its;
141: }
142: return 0;
143: }
145: /***************************************************************************/
146: /* As far as we know, the preconditioner is positive semidefinite. */
147: /* Compute and log the residual. Check convergence because this */
148: /* initializes things, but do not terminate until at least one conjugate */
149: /* gradient iteration has been performed. */
150: /***************************************************************************/
152: switch (ksp->normtype) {
153: case KSP_NORM_PRECONDITIONED:
154: VecNorm(z, NORM_2, &norm_r); /* norm_r = |z| */
155: break;
157: case KSP_NORM_UNPRECONDITIONED:
158: norm_r = PetscSqrtReal(rr); /* norm_r = |r| */
159: break;
161: case KSP_NORM_NATURAL:
162: norm_r = PetscSqrtReal(rz); /* norm_r = |r|_M */
163: break;
165: default:
166: norm_r = 0.0;
167: break;
168: }
170: KSPLogResidualHistory(ksp, norm_r);
171: KSPMonitor(ksp, ksp->its, norm_r);
172: ksp->rnorm = norm_r;
174: (*ksp->converged)(ksp, ksp->its, norm_r, &ksp->reason, ksp->cnvP);
176: /***************************************************************************/
177: /* Compute the first direction and update the iteration. */
178: /***************************************************************************/
180: VecCopy(z, p); /* p = z */
181: KSP_MatMult(ksp, Qmat, p, z); /* z = Q * p */
182: ++ksp->its;
184: /***************************************************************************/
185: /* Check the matrix for numerical problems. */
186: /***************************************************************************/
188: VecDot(p, z, &kappa); /* kappa = p^T Q p */
189: if (PetscIsInfOrNanScalar(kappa)) {
190: /*************************************************************************/
191: /* The matrix produced not-a-number or an infinite value. In this case, */
192: /* we must stop and use the gradient direction. This condition need */
193: /* only be checked once. */
194: /*************************************************************************/
196: ksp->reason = KSP_DIVERGED_NANORINF;
197: PetscInfo(ksp, "KSPCGSolve_STCG: bad matrix: kappa=%g\n", (double)kappa);
199: if (cg->radius) {
200: if (r2 >= rr) {
201: alpha = 1.0;
202: cg->norm_d = PetscSqrtReal(rr);
203: } else {
204: alpha = PetscSqrtReal(r2 / rr);
205: cg->norm_d = cg->radius;
206: }
208: VecAXPY(d, alpha, r); /* d = d + alpha r */
210: /***********************************************************************/
211: /* Compute objective function. */
212: /***********************************************************************/
214: KSP_MatMult(ksp, Qmat, d, z);
215: VecAYPX(z, -0.5, ksp->vec_rhs);
216: VecDot(d, z, &cg->o_fcn);
217: cg->o_fcn = -cg->o_fcn;
218: ++ksp->its;
219: }
220: return 0;
221: }
223: /***************************************************************************/
224: /* Initialize variables for calculating the norm of the direction. */
225: /***************************************************************************/
227: dMp = 0.0;
228: norm_d = 0.0;
229: switch (cg->dtype) {
230: case STCG_PRECONDITIONED_DIRECTION:
231: norm_p = rz;
232: break;
234: default:
235: VecDot(p, p, &norm_p);
236: break;
237: }
239: /***************************************************************************/
240: /* Check for negative curvature. */
241: /***************************************************************************/
243: if (kappa <= 0.0) {
244: /*************************************************************************/
245: /* In this case, the matrix is indefinite and we have encountered a */
246: /* direction of negative curvature. Because negative curvature occurs */
247: /* during the first step, we must follow a direction. */
248: /*************************************************************************/
250: ksp->reason = KSP_CONVERGED_CG_NEG_CURVE;
251: PetscInfo(ksp, "KSPCGSolve_STCG: negative curvature: kappa=%g\n", (double)kappa);
253: if (cg->radius != 0.0 && norm_p > 0.0) {
254: /***********************************************************************/
255: /* Follow direction of negative curvature to the boundary of the */
256: /* trust region. */
257: /***********************************************************************/
259: step = PetscSqrtReal(r2 / norm_p);
260: cg->norm_d = cg->radius;
262: VecAXPY(d, step, p); /* d = d + step p */
264: /***********************************************************************/
265: /* Update objective function. */
266: /***********************************************************************/
268: cg->o_fcn += step * (0.5 * step * kappa - rz);
269: } else if (cg->radius != 0.0) {
270: /***********************************************************************/
271: /* The norm of the preconditioned direction is zero; use the gradient */
272: /* step. */
273: /***********************************************************************/
275: if (r2 >= rr) {
276: alpha = 1.0;
277: cg->norm_d = PetscSqrtReal(rr);
278: } else {
279: alpha = PetscSqrtReal(r2 / rr);
280: cg->norm_d = cg->radius;
281: }
283: VecAXPY(d, alpha, r); /* d = d + alpha r */
285: /***********************************************************************/
286: /* Compute objective function. */
287: /***********************************************************************/
289: KSP_MatMult(ksp, Qmat, d, z);
290: VecAYPX(z, -0.5, ksp->vec_rhs);
291: VecDot(d, z, &cg->o_fcn);
293: cg->o_fcn = -cg->o_fcn;
294: ++ksp->its;
295: }
296: return 0;
297: }
299: /***************************************************************************/
300: /* Run the conjugate gradient method until either the problem is solved, */
301: /* we encounter the boundary of the trust region, or the conjugate */
302: /* gradient method breaks down. */
303: /***************************************************************************/
305: while (1) {
306: /*************************************************************************/
307: /* Know that kappa is nonzero, because we have not broken down, so we */
308: /* can compute the steplength. */
309: /*************************************************************************/
311: alpha = rz / kappa;
313: /*************************************************************************/
314: /* Compute the steplength and check for intersection with the trust */
315: /* region. */
316: /*************************************************************************/
318: norm_dp1 = norm_d + alpha * (2.0 * dMp + alpha * norm_p);
319: if (cg->radius != 0.0 && norm_dp1 >= r2) {
320: /***********************************************************************/
321: /* In this case, the matrix is positive definite as far as we know. */
322: /* However, the full step goes beyond the trust region. */
323: /***********************************************************************/
325: ksp->reason = KSP_CONVERGED_CG_CONSTRAINED;
326: PetscInfo(ksp, "KSPCGSolve_STCG: constrained step: radius=%g\n", (double)cg->radius);
328: if (norm_p > 0.0) {
329: /*********************************************************************/
330: /* Follow the direction to the boundary of the trust region. */
331: /*********************************************************************/
333: step = (PetscSqrtReal(dMp * dMp + norm_p * (r2 - norm_d)) - dMp) / norm_p;
334: cg->norm_d = cg->radius;
336: VecAXPY(d, step, p); /* d = d + step p */
338: /*********************************************************************/
339: /* Update objective function. */
340: /*********************************************************************/
342: cg->o_fcn += step * (0.5 * step * kappa - rz);
343: } else {
344: /*********************************************************************/
345: /* The norm of the direction is zero; there is nothing to follow. */
346: /*********************************************************************/
347: }
348: break;
349: }
351: /*************************************************************************/
352: /* Now we can update the direction and residual. */
353: /*************************************************************************/
355: VecAXPY(d, alpha, p); /* d = d + alpha p */
356: VecAXPY(r, -alpha, z); /* r = r - alpha Q p */
357: KSP_PCApply(ksp, r, z); /* z = inv(M) r */
359: switch (cg->dtype) {
360: case STCG_PRECONDITIONED_DIRECTION:
361: norm_d = norm_dp1;
362: break;
364: default:
365: VecDot(d, d, &norm_d);
366: break;
367: }
368: cg->norm_d = PetscSqrtReal(norm_d);
370: /*************************************************************************/
371: /* Update objective function. */
372: /*************************************************************************/
374: cg->o_fcn -= 0.5 * alpha * rz;
376: /*************************************************************************/
377: /* Check that the preconditioner appears positive semidefinite. */
378: /*************************************************************************/
380: rzm1 = rz;
381: VecDot(r, z, &rz); /* rz = r^T z */
382: if (rz < 0.0) {
383: /***********************************************************************/
384: /* The preconditioner is indefinite. */
385: /***********************************************************************/
387: ksp->reason = KSP_DIVERGED_INDEFINITE_PC;
388: PetscInfo(ksp, "KSPCGSolve_STCG: cg indefinite preconditioner: rz=%g\n", (double)rz);
389: break;
390: }
392: /*************************************************************************/
393: /* As far as we know, the preconditioner is positive semidefinite. */
394: /* Compute the residual and check for convergence. */
395: /*************************************************************************/
397: switch (ksp->normtype) {
398: case KSP_NORM_PRECONDITIONED:
399: VecNorm(z, NORM_2, &norm_r); /* norm_r = |z| */
400: break;
402: case KSP_NORM_UNPRECONDITIONED:
403: VecNorm(r, NORM_2, &norm_r); /* norm_r = |r| */
404: break;
406: case KSP_NORM_NATURAL:
407: norm_r = PetscSqrtReal(rz); /* norm_r = |r|_M */
408: break;
410: default:
411: norm_r = 0.0;
412: break;
413: }
415: KSPLogResidualHistory(ksp, norm_r);
416: KSPMonitor(ksp, ksp->its, norm_r);
417: ksp->rnorm = norm_r;
419: (*ksp->converged)(ksp, ksp->its, norm_r, &ksp->reason, ksp->cnvP);
420: if (ksp->reason) {
421: /***********************************************************************/
422: /* The method has converged. */
423: /***********************************************************************/
425: PetscInfo(ksp, "KSPCGSolve_STCG: truncated step: rnorm=%g, radius=%g\n", (double)norm_r, (double)cg->radius);
426: break;
427: }
429: /*************************************************************************/
430: /* We have not converged yet. Check for breakdown. */
431: /*************************************************************************/
433: beta = rz / rzm1;
434: if (PetscAbsScalar(beta) <= 0.0) {
435: /***********************************************************************/
436: /* Conjugate gradients has broken down. */
437: /***********************************************************************/
439: ksp->reason = KSP_DIVERGED_BREAKDOWN;
440: PetscInfo(ksp, "KSPCGSolve_STCG: breakdown: beta=%g\n", (double)beta);
441: break;
442: }
444: /*************************************************************************/
445: /* Check iteration limit. */
446: /*************************************************************************/
448: if (ksp->its >= max_cg_its) {
449: ksp->reason = KSP_DIVERGED_ITS;
450: PetscInfo(ksp, "KSPCGSolve_STCG: iterlim: its=%" PetscInt_FMT "\n", ksp->its);
451: break;
452: }
454: /*************************************************************************/
455: /* Update p and the norms. */
456: /*************************************************************************/
458: VecAYPX(p, beta, z); /* p = z + beta p */
460: switch (cg->dtype) {
461: case STCG_PRECONDITIONED_DIRECTION:
462: dMp = beta * (dMp + alpha * norm_p);
463: norm_p = beta * (rzm1 + beta * norm_p);
464: break;
466: default:
467: VecDot(d, p, &dMp);
468: VecDot(p, p, &norm_p);
469: break;
470: }
472: /*************************************************************************/
473: /* Compute the new direction and update the iteration. */
474: /*************************************************************************/
476: KSP_MatMult(ksp, Qmat, p, z); /* z = Q * p */
477: VecDot(p, z, &kappa); /* kappa = p^T Q p */
478: ++ksp->its;
480: /*************************************************************************/
481: /* Check for negative curvature. */
482: /*************************************************************************/
484: if (kappa <= 0.0) {
485: /***********************************************************************/
486: /* In this case, the matrix is indefinite and we have encountered */
487: /* a direction of negative curvature. Follow the direction to the */
488: /* boundary of the trust region. */
489: /***********************************************************************/
491: ksp->reason = KSP_CONVERGED_CG_NEG_CURVE;
492: PetscInfo(ksp, "KSPCGSolve_STCG: negative curvature: kappa=%g\n", (double)kappa);
494: if (cg->radius != 0.0 && norm_p > 0.0) {
495: /*********************************************************************/
496: /* Follow direction of negative curvature to boundary. */
497: /*********************************************************************/
499: step = (PetscSqrtReal(dMp * dMp + norm_p * (r2 - norm_d)) - dMp) / norm_p;
500: cg->norm_d = cg->radius;
502: VecAXPY(d, step, p); /* d = d + step p */
504: /*********************************************************************/
505: /* Update objective function. */
506: /*********************************************************************/
508: cg->o_fcn += step * (0.5 * step * kappa - rz);
509: } else if (cg->radius != 0.0) {
510: /*********************************************************************/
511: /* The norm of the direction is zero; there is nothing to follow. */
512: /*********************************************************************/
513: }
514: break;
515: }
516: }
517: return 0;
518: #endif
519: }
521: static PetscErrorCode KSPCGSetUp_STCG(KSP ksp)
522: {
523: /***************************************************************************/
524: /* Set work vectors needed by conjugate gradient method and allocate */
525: /***************************************************************************/
527: KSPSetWorkVecs(ksp, 3);
528: return 0;
529: }
531: static PetscErrorCode KSPCGDestroy_STCG(KSP ksp)
532: {
533: /***************************************************************************/
534: /* Clear composed functions */
535: /***************************************************************************/
537: PetscObjectComposeFunction((PetscObject)ksp, "KSPCGSetRadius_C", NULL);
538: PetscObjectComposeFunction((PetscObject)ksp, "KSPCGGetNormD_C", NULL);
539: PetscObjectComposeFunction((PetscObject)ksp, "KSPCGGetObjFcn_C", NULL);
541: /***************************************************************************/
542: /* Destroy KSP object. */
543: /***************************************************************************/
545: KSPDestroyDefault(ksp);
546: return 0;
547: }
549: static PetscErrorCode KSPCGSetRadius_STCG(KSP ksp, PetscReal radius)
550: {
551: KSPCG_STCG *cg = (KSPCG_STCG *)ksp->data;
553: cg->radius = radius;
554: return 0;
555: }
557: static PetscErrorCode KSPCGGetNormD_STCG(KSP ksp, PetscReal *norm_d)
558: {
559: KSPCG_STCG *cg = (KSPCG_STCG *)ksp->data;
561: *norm_d = cg->norm_d;
562: return 0;
563: }
565: static PetscErrorCode KSPCGGetObjFcn_STCG(KSP ksp, PetscReal *o_fcn)
566: {
567: KSPCG_STCG *cg = (KSPCG_STCG *)ksp->data;
569: *o_fcn = cg->o_fcn;
570: return 0;
571: }
573: static PetscErrorCode KSPCGSetFromOptions_STCG(KSP ksp, PetscOptionItems *PetscOptionsObject)
574: {
575: KSPCG_STCG *cg = (KSPCG_STCG *)ksp->data;
577: PetscOptionsHeadBegin(PetscOptionsObject, "KSPCG STCG options");
578: PetscOptionsReal("-ksp_cg_radius", "Trust Region Radius", "KSPCGSetRadius", cg->radius, &cg->radius, NULL);
579: PetscOptionsEList("-ksp_cg_dtype", "Norm used for direction", "", DType_Table, STCG_DIRECTION_TYPES, DType_Table[cg->dtype], &cg->dtype, NULL);
580: PetscOptionsHeadEnd();
581: return 0;
582: }
584: /*MC
585: KSPSTCG - Code to run conjugate gradient method subject to a constraint on the solution norm.
587: Options Database Keys:
588: . -ksp_cg_radius <r> - Trust Region Radius
590: Notes:
591: This is rarely used directly, it is used in Trust Region methods for nonlinear equations, `SNESNEWTONTR`
593: Use preconditioned conjugate gradient to compute
594: an approximate minimizer of the quadratic function
596: q(s) = g^T * s + 0.5 * s^T * H * s
598: subject to the trust region constraint
600: || s || <= delta,
602: where
604: delta is the trust region radius,
605: g is the gradient vector,
606: H is the Hessian approximation, and
607: M is the positive definite preconditioner matrix.
609: `KSPConvergedReason` may be
610: .vb
611: KSP_CONVERGED_CG_NEG_CURVE if convergence is reached along a negative curvature direction,
612: KSP_CONVERGED_CG_CONSTRAINED if convergence is reached along a constrained step,
613: .ve
614: other `KSP` converged/diverged reasons
616: The preconditioner supplied should be symmetric and positive definite.
618: References:
619: + * - Steihaug, T. (1983): The conjugate gradient method and trust regions in large scale optimization. SIAM J. Numer. Anal. 20, 626--637
620: - * - Toint, Ph.L. (1981): Towards an efficient sparsity exploiting Newton method for minimization. In: Duff, I., ed., Sparse Matrices and Their Uses, pp. 57--88. Academic Press
622: Level: developer
624: .seealso: [](chapter_ksp), `KSPCreate()`, `KSPCGSetType()`, `KSPType`, `KSP`, `KSPCGSetRadius()`, `KSPCGGetNormD()`, `KSPCGGetObjFcn()`, `KSPNASH`, `KSPGLTR`, `KSPQCG`
625: M*/
627: PETSC_EXTERN PetscErrorCode KSPCreate_STCG(KSP ksp)
628: {
629: KSPCG_STCG *cg;
631: PetscNew(&cg);
633: cg->radius = 0.0;
634: cg->dtype = STCG_UNPRECONDITIONED_DIRECTION;
636: ksp->data = (void *)cg;
637: KSPSetSupportedNorm(ksp, KSP_NORM_UNPRECONDITIONED, PC_LEFT, 3);
638: KSPSetSupportedNorm(ksp, KSP_NORM_PRECONDITIONED, PC_LEFT, 2);
639: KSPSetSupportedNorm(ksp, KSP_NORM_NATURAL, PC_LEFT, 2);
640: KSPSetSupportedNorm(ksp, KSP_NORM_NONE, PC_LEFT, 1);
642: /***************************************************************************/
643: /* Sets the functions that are associated with this data structure */
644: /* (in C++ this is the same as defining virtual functions). */
645: /***************************************************************************/
647: ksp->ops->setup = KSPCGSetUp_STCG;
648: ksp->ops->solve = KSPCGSolve_STCG;
649: ksp->ops->destroy = KSPCGDestroy_STCG;
650: ksp->ops->setfromoptions = KSPCGSetFromOptions_STCG;
651: ksp->ops->buildsolution = KSPBuildSolutionDefault;
652: ksp->ops->buildresidual = KSPBuildResidualDefault;
653: ksp->ops->view = NULL;
655: PetscObjectComposeFunction((PetscObject)ksp, "KSPCGSetRadius_C", KSPCGSetRadius_STCG);
656: PetscObjectComposeFunction((PetscObject)ksp, "KSPCGGetNormD_C", KSPCGGetNormD_STCG);
657: PetscObjectComposeFunction((PetscObject)ksp, "KSPCGGetObjFcn_C", KSPCGGetObjFcn_STCG);
658: return 0;
659: }