Actual source code: qmrcgs.c
1: /*
2: This file implements QMRCGS (QMRCGStab).
4: References:
5: . * - Chan, Gallopoulos, Simoncini, Szeto, and Tong (SISC 1994), Ghai, Lu, and Jiao (NLAA 2019)
6: */
7: #include <../src/ksp/ksp/impls/bcgs/bcgsimpl.h>
9: static PetscErrorCode KSPSetUp_QMRCGS(KSP ksp)
10: {
11: PetscFunctionBegin;
12: PetscCall(KSPSetWorkVecs(ksp, 14));
13: PetscFunctionReturn(PETSC_SUCCESS);
14: }
16: /* Only need a few hacks from KSPSolve_BCGS */
18: static PetscErrorCode KSPSolve_QMRCGS(KSP ksp)
19: {
20: PetscInt i;
21: PetscScalar eta, rho1, rho2, alpha, eta2, omega, beta, cf, cf1, uu;
22: Vec X, B, R, P, PH, V, D2, X2, S, SH, T, D, S2, RP, AX, Z;
23: PetscReal dp = 0.0, final, tau, tau2, theta, theta2, c, F, NV, vv;
24: KSP_BCGS *bcgs = (KSP_BCGS *)ksp->data;
25: PC pc;
26: Mat mat;
28: PetscFunctionBegin;
29: X = ksp->vec_sol;
30: B = ksp->vec_rhs;
31: R = ksp->work[0];
32: P = ksp->work[1];
33: PH = ksp->work[2];
34: V = ksp->work[3];
35: D2 = ksp->work[4];
36: X2 = ksp->work[5];
37: S = ksp->work[6];
38: SH = ksp->work[7];
39: T = ksp->work[8];
40: D = ksp->work[9];
41: S2 = ksp->work[10];
42: RP = ksp->work[11];
43: AX = ksp->work[12];
44: Z = ksp->work[13];
46: /* Only supports right preconditioning */
47: PetscCheck(ksp->pc_side == PC_RIGHT, PetscObjectComm((PetscObject)ksp), PETSC_ERR_SUP, "KSP qmrcgs does not support %s", PCSides[ksp->pc_side]);
48: if (!ksp->guess_zero) {
49: if (!bcgs->guess) PetscCall(VecDuplicate(X, &bcgs->guess));
50: PetscCall(VecCopy(X, bcgs->guess));
51: } else {
52: PetscCall(VecSet(X, 0.0));
53: }
55: /* Compute initial residual */
56: PetscCall(KSPGetPC(ksp, &pc));
57: PetscCall(PCGetOperators(pc, &mat, NULL));
58: if (!ksp->guess_zero) {
59: PetscCall(KSP_MatMult(ksp, mat, X, S2));
60: PetscCall(VecCopy(B, R));
61: PetscCall(VecAXPY(R, -1.0, S2));
62: } else {
63: PetscCall(VecCopy(B, R));
64: }
66: /* Test for nothing to do */
67: if (ksp->normtype != KSP_NORM_NONE) PetscCall(VecNorm(R, NORM_2, &dp));
68: PetscCall(PetscObjectSAWsTakeAccess((PetscObject)ksp));
69: ksp->its = 0;
70: ksp->rnorm = dp;
71: PetscCall(PetscObjectSAWsGrantAccess((PetscObject)ksp));
72: PetscCall(KSPLogResidualHistory(ksp, dp));
73: PetscCall(KSPMonitor(ksp, 0, dp));
74: PetscCall((*ksp->converged)(ksp, 0, dp, &ksp->reason, ksp->cnvP));
75: if (ksp->reason) PetscFunctionReturn(PETSC_SUCCESS);
77: /* Make the initial Rp == R */
78: PetscCall(VecCopy(R, RP));
80: eta = 1.0;
81: theta = 1.0;
82: if (dp == 0.0) {
83: PetscCall(VecNorm(R, NORM_2, &tau));
84: } else {
85: tau = dp;
86: }
88: PetscCall(VecDot(RP, RP, &rho1));
89: PetscCall(VecCopy(R, P));
91: i = 0;
92: do {
93: PetscCall(KSP_PCApply(ksp, P, PH)); /* ph <- K p */
94: PetscCall(KSP_MatMult(ksp, mat, PH, V)); /* v <- A ph */
96: PetscCall(VecDot(V, RP, &rho2)); /* rho2 <- (v,rp) */
97: if (rho2 == 0.0) {
98: PetscCheck(!ksp->errorifnotconverged, PetscObjectComm((PetscObject)ksp), PETSC_ERR_NOT_CONVERGED, "KSPSolve has not converged due to division by zero");
99: ksp->reason = KSP_DIVERGED_NANORINF;
100: break;
101: }
103: if (rho1 == 0) {
104: PetscCheck(!ksp->errorifnotconverged, PetscObjectComm((PetscObject)ksp), PETSC_ERR_NOT_CONVERGED, "KSPSolve has stagnated");
105: ksp->reason = KSP_DIVERGED_BREAKDOWN; /* Stagnation */
106: break;
107: }
109: alpha = rho1 / rho2;
110: PetscCall(VecWAXPY(S, -alpha, V, R)); /* s <- r - alpha v */
112: /* First quasi-minimization step */
113: PetscCall(VecNorm(S, NORM_2, &F)); /* f <- norm(s) */
114: theta2 = F / tau;
116: c = 1.0 / PetscSqrtReal(1.0 + theta2 * theta2);
118: tau2 = tau * theta2 * c;
119: eta2 = c * c * alpha;
120: cf = theta * theta * eta / alpha;
121: PetscCall(VecWAXPY(D2, cf, D, PH)); /* d2 <- ph + cf d */
122: PetscCall(VecWAXPY(X2, eta2, D2, X)); /* x2 <- x + eta2 d2 */
124: /* Apply the right preconditioner again */
125: PetscCall(KSP_PCApply(ksp, S, SH)); /* sh <- K s */
126: PetscCall(KSP_MatMult(ksp, mat, SH, T)); /* t <- A sh */
128: PetscCall(VecDotNorm2(S, T, &uu, &vv));
129: if (vv == 0.0) {
130: PetscCall(VecDot(S, S, &uu));
131: if (uu != 0.0) {
132: PetscCheck(!ksp->errorifnotconverged, PetscObjectComm((PetscObject)ksp), PETSC_ERR_NOT_CONVERGED, "KSPSolve has not converged due to division by zero");
133: ksp->reason = KSP_DIVERGED_NANORINF;
134: break;
135: }
136: PetscCall(VecAXPY(X, alpha, SH)); /* x <- x + alpha sh */
137: PetscCall(PetscObjectSAWsTakeAccess((PetscObject)ksp));
138: ksp->its++;
139: ksp->rnorm = 0.0;
140: ksp->reason = KSP_CONVERGED_RTOL;
141: PetscCall(PetscObjectSAWsGrantAccess((PetscObject)ksp));
142: PetscCall(KSPLogResidualHistory(ksp, dp));
143: PetscCall(KSPMonitor(ksp, i + 1, 0.0));
144: break;
145: }
146: PetscCall(VecNorm(V, NORM_2, &NV)); /* nv <- norm(v) */
148: if (NV == 0) {
149: PetscCheck(!ksp->errorifnotconverged, PetscObjectComm((PetscObject)ksp), PETSC_ERR_NOT_CONVERGED, "KSPSolve has not converged due to singular matrix");
150: ksp->reason = KSP_DIVERGED_BREAKDOWN;
151: break;
152: }
154: if (uu == 0) {
155: PetscCheck(!ksp->errorifnotconverged, PetscObjectComm((PetscObject)ksp), PETSC_ERR_NOT_CONVERGED, "KSPSolve has stagnated");
156: ksp->reason = KSP_DIVERGED_BREAKDOWN; /* Stagnation */
157: break;
158: }
159: omega = uu / vv; /* omega <- uu/vv; */
161: /* Computing the residual */
162: PetscCall(VecWAXPY(R, -omega, T, S)); /* r <- s - omega t */
164: /* Second quasi-minimization step */
165: if (ksp->normtype != KSP_NORM_NONE && ksp->chknorm < i + 2) PetscCall(VecNorm(R, NORM_2, &dp));
167: if (tau2 == 0) {
168: PetscCheck(!ksp->errorifnotconverged, PetscObjectComm((PetscObject)ksp), PETSC_ERR_NOT_CONVERGED, "KSPSolve has not converged due to division by zero");
169: ksp->reason = KSP_DIVERGED_NANORINF;
170: break;
171: }
172: theta = dp / tau2;
173: c = 1.0 / PetscSqrtReal(1.0 + theta * theta);
174: if (dp == 0.0) {
175: PetscCall(VecNorm(R, NORM_2, &tau));
176: } else {
177: tau = dp;
178: }
179: tau = tau * c;
180: eta = c * c * omega;
182: cf1 = theta2 * theta2 * eta2 / omega;
183: PetscCall(VecWAXPY(D, cf1, D2, SH)); /* d <- sh + cf1 d2 */
184: PetscCall(VecWAXPY(X, eta, D, X2)); /* x <- x2 + eta d */
186: PetscCall(VecDot(R, RP, &rho2));
187: PetscCall(PetscObjectSAWsTakeAccess((PetscObject)ksp));
188: ksp->its++;
189: ksp->rnorm = dp;
190: PetscCall(PetscObjectSAWsGrantAccess((PetscObject)ksp));
191: PetscCall(KSPLogResidualHistory(ksp, dp));
192: PetscCall(KSPMonitor(ksp, i + 1, dp));
194: beta = (alpha * rho2) / (omega * rho1);
195: PetscCall(VecAXPBYPCZ(P, 1.0, -omega * beta, beta, R, V)); /* p <- r - omega * beta* v + beta * p */
196: rho1 = rho2;
197: PetscCall(KSP_MatMult(ksp, mat, X, AX)); /* Ax <- A x */
198: PetscCall(VecWAXPY(Z, -1.0, AX, B)); /* r <- b - Ax */
199: PetscCall(VecNorm(Z, NORM_2, &final));
200: PetscCall((*ksp->converged)(ksp, i + 1, dp, &ksp->reason, ksp->cnvP));
201: if (ksp->reason) break;
202: i++;
203: } while (i < ksp->max_it);
205: /* mark lack of convergence */
206: if (ksp->its >= ksp->max_it && !ksp->reason) ksp->reason = KSP_DIVERGED_ITS;
207: PetscFunctionReturn(PETSC_SUCCESS);
208: }
210: /*MC
211: KSPQMRCGS - Implements the QMRCGStab method.
213: Level: beginner
215: Note:
216: Only right preconditioning is supported.
218: Contributed by:
219: Xiangmin Jiao (xiangmin.jiao@stonybrook.edu)
221: References:
222: + * - Chan, Gallopoulos, Simoncini, Szeto, and Tong (SISC 1994)
223: - * - Ghai, Lu, and Jiao (NLAA 2019)
225: .seealso: [](ch_ksp), `KSPCreate()`, `KSPSetType()`, `KSPType`, `KSP`, `KSPBICG`, `KSPFBICGS`, `KSPBCGSL`, `KSPSetPCSide()`
226: M*/
227: PETSC_EXTERN PetscErrorCode KSPCreate_QMRCGS(KSP ksp)
228: {
229: KSP_BCGS *bcgs;
230: static const char citations[] = "@article{chan1994qmrcgs,\n"
231: " title={A quasi-minimal residual variant of the {Bi-CGSTAB} algorithm for nonsymmetric systems},\n"
232: " author={Chan, Tony F and Gallopoulos, Efstratios and Simoncini, Valeria and Szeto, Tedd and Tong, Charles H},\n"
233: " journal={SIAM Journal on Scientific Computing},\n"
234: " volume={15},\n"
235: " number={2},\n"
236: " pages={338--347},\n"
237: " year={1994},\n"
238: " publisher={SIAM}\n"
239: "}\n"
240: "@article{ghai2019comparison,\n"
241: " title={A comparison of preconditioned {K}rylov subspace methods for large-scale nonsymmetric linear systems},\n"
242: " author={Ghai, Aditi and Lu, Cao and Jiao, Xiangmin},\n"
243: " journal={Numerical Linear Algebra with Applications},\n"
244: " volume={26},\n"
245: " number={1},\n"
246: " pages={e2215},\n"
247: " year={2019},\n"
248: " publisher={Wiley Online Library}\n"
249: "}\n";
250: PetscBool cite = PETSC_FALSE;
252: PetscFunctionBegin;
253: PetscCall(PetscCitationsRegister(citations, &cite));
254: PetscCall(PetscNew(&bcgs));
256: ksp->data = bcgs;
257: ksp->ops->setup = KSPSetUp_QMRCGS;
258: ksp->ops->solve = KSPSolve_QMRCGS;
259: ksp->ops->destroy = KSPDestroy_BCGS;
260: ksp->ops->reset = KSPReset_BCGS;
261: ksp->ops->buildresidual = KSPBuildResidualDefault;
262: ksp->ops->setfromoptions = KSPSetFromOptions_BCGS;
263: ksp->pc_side = PC_RIGHT; /* set default PC side */
265: PetscCall(KSPSetSupportedNorm(ksp, KSP_NORM_UNPRECONDITIONED, PC_RIGHT, 2));
266: PetscCall(KSPSetSupportedNorm(ksp, KSP_NORM_NONE, PC_RIGHT, 1));
267: PetscFunctionReturn(PETSC_SUCCESS);
268: }