Actual source code: tsirm.c
petsc-3.9.4 2018-09-11
3: #include <petsc/private/kspimpl.h>
5: typedef struct {
6: PetscReal tol_ls;
7: PetscInt size_ls,maxiter_ls,cgls,size,Istart,Iend;
8: Mat A,S;
9: Vec Alpha,r;
10: } KSP_TSIRM;
12: static PetscErrorCode KSPSetUp_TSIRM(KSP ksp)
13: {
15: KSP_TSIRM *tsirm = (KSP_TSIRM*)ksp->data;
16:
18: /* Initialization */
19: #if defined(PETSC_USE_REAL_SINGLE)
20: tsirm->tol_ls = 1e-25;
21: #else
22: tsirm->tol_ls = 1e-50;
23: #endif
24: tsirm->size_ls = 12;
25: tsirm->maxiter_ls = 15;
26: tsirm->cgls = 0;
27:
28: /* Matrix of the system */
29: KSPGetOperators(ksp,&tsirm->A,NULL); /* Matrix of the system */
30: MatGetSize(tsirm->A,&tsirm->size,NULL); /* Size of the system */
31: MatGetOwnershipRange(tsirm->A,&tsirm->Istart,&tsirm->Iend);
32:
33: /* Matrix S of residuals */
34: MatCreate(PETSC_COMM_WORLD,&tsirm->S);
35: MatSetSizes(tsirm->S,tsirm->Iend-tsirm->Istart,PETSC_DECIDE,tsirm->size,tsirm->size_ls);
36: MatSetType(tsirm->S,MATDENSE);
37: MatSetUp(tsirm->S);
38:
39: /* Residual and vector Alpha computed in the minimization step */
40: MatCreateVecs(tsirm->S,&tsirm->Alpha,&tsirm->r);
41: return(0);
42: }
44: PetscErrorCode KSPSolve_TSIRM(KSP ksp)
45: {
47: KSP_TSIRM *tsirm = (KSP_TSIRM*)ksp->data;
48: KSP sub_ksp;
49: PC pc;
50: Mat AS = NULL;
51: Vec x,b;
52: PetscScalar *array;
53: PetscReal norm = 20;
54: PetscInt i,*ind_row,first_iteration = 1,its = 0,total = 0,col = 0;
55: PetscInt restart = 30;
56: KSP ksp_min; /* KSP for minimization */
57: PC pc_min; /* PC for minimization */
58:
60: x = ksp->vec_sol; /* Solution vector */
61: b = ksp->vec_rhs; /* Right-hand side vector */
62:
63: /* Row indexes (these indexes are global) */
64: PetscMalloc1(tsirm->Iend-tsirm->Istart,&ind_row);
65: for (i=0;i<tsirm->Iend-tsirm->Istart;i++) ind_row[i] = i+tsirm->Istart;
66:
67: /* Inner solver */
68: KSPGetPC(ksp,&pc);
69: PCKSPGetKSP(pc,&sub_ksp);
70: if (!sub_ksp) SETERRQ(PetscObjectComm((PetscObject)pc),PETSC_ERR_USER,"PC must be of type PCKSP");
71: KSPSetTolerances(sub_ksp,PETSC_DEFAULT,PETSC_DEFAULT,PETSC_DEFAULT,restart);
72:
73: /* previously it seemed good but with SNES it seems not good... */
74: KSP_MatMult(sub_ksp,tsirm->A,x,tsirm->r);
75: VecAXPY(tsirm->r,-1,b);
76: VecNorm(tsirm->r,NORM_2,&norm);
77: ksp->its = 0;
78: KSPConvergedDefault(ksp,ksp->its,norm,&ksp->reason,ksp->cnvP);
79: KSPSetInitialGuessNonzero(sub_ksp,PETSC_TRUE);
80: do {
81: for (col=0;col<tsirm->size_ls && ksp->reason==0;col++) {
82: /* Solve (inner iteration) */
83: KSPSolve(sub_ksp,b,x);
84: KSPGetIterationNumber(sub_ksp,&its);
85: total += its;
86:
87: /* Build S^T */
88: VecGetArray(x,&array);
89: MatSetValues(tsirm->S,tsirm->Iend-tsirm->Istart,ind_row,1,&col,array,INSERT_VALUES);
90: VecRestoreArray(x,&array);
91:
92: KSPGetResidualNorm(sub_ksp,&norm);
93: ksp->rnorm = norm;
94: ksp->its ++;
95: KSPConvergedDefault(ksp,ksp->its,norm,&ksp->reason,ksp->cnvP);
96: KSPMonitor(ksp,ksp->its,norm);
97: }
98:
99: /* Minimization step */
100: if (!ksp->reason) {
101: MatAssemblyBegin(tsirm->S,MAT_FINAL_ASSEMBLY);
102: MatAssemblyEnd(tsirm->S,MAT_FINAL_ASSEMBLY);
103: if (first_iteration) {
104: MatMatMult(tsirm->A,tsirm->S,MAT_INITIAL_MATRIX,PETSC_DEFAULT,&AS);
105: first_iteration = 0;
106: } else {
107: MatMatMult(tsirm->A,tsirm->S,MAT_REUSE_MATRIX,PETSC_DEFAULT,&AS);
108: }
109:
110: /* CGLS or LSQR method to minimize the residuals*/
111:
112: KSPCreate(PETSC_COMM_WORLD,&ksp_min);
113: if (tsirm->cgls) {
114: KSPSetType(ksp_min,KSPCGLS);
115: } else {
116: KSPSetType(ksp_min,KSPLSQR);
117: }
118: KSPSetOperators(ksp_min,AS,AS);
119: KSPSetTolerances(ksp_min,tsirm->tol_ls,PETSC_DEFAULT,PETSC_DEFAULT,tsirm->maxiter_ls);
120: KSPGetPC(ksp_min,&pc_min);
121: PCSetType(pc_min,PCNONE);
122: KSPSolve(ksp_min,b,tsirm->Alpha); /* Find Alpha such that ||AS Alpha = b|| */
123: KSPDestroy(&ksp_min);
124: /* Apply minimization */
125: MatMult(tsirm->S,tsirm->Alpha,x); /* x = S * Alpha */
126: }
127: } while (ksp->its<ksp->max_it && !ksp->reason);
128: MatDestroy(&AS);
129: PetscFree(ind_row);
130: ksp->its = total;
131: return(0);
132: }
134: PetscErrorCode KSPSetFromOptions_TSIRM(PetscOptionItems *PetscOptionsObject,KSP ksp)
135: {
137: KSP_TSIRM *tsirm = (KSP_TSIRM*)ksp->data;
140: PetscOptionsHead(PetscOptionsObject,"KSP TSIRM options");
141: PetscOptionsInt("-ksp_tsirm_cgls","Method used for the minimization step","",tsirm->cgls,&tsirm->cgls,NULL); /*0:LSQR, 1:CGLS*/
142: PetscOptionsReal("-ksp_tsirm_tol_ls","Tolerance threshold for the minimization step","",tsirm->tol_ls,&tsirm->tol_ls,NULL);
143: PetscOptionsInt("-ksp_tsirm_max_it_ls","Maximum number of iterations for the minimization step","",tsirm->maxiter_ls,&tsirm->maxiter_ls,NULL);
144: PetscOptionsInt("-ksp_tsirm_size_ls","Number of residuals for minimization","",tsirm->size_ls,&tsirm->size_ls,NULL);
145: PetscOptionsTail();
146: return(0);
147: }
149: PetscErrorCode KSPDestroy_TSIRM(KSP ksp)
150: {
151: KSP_TSIRM *tsirm = (KSP_TSIRM*)ksp->data;
155: MatDestroy(&tsirm->S);
156: VecDestroy(&tsirm->Alpha);
157: VecDestroy(&tsirm->r);
158: PetscFree(ksp->data);
159: return(0);
160: }
162: /*MC
163: KSPTSIRM - Implements the two-stage iteration with least-squares residual minimization method.
166: Options Database Keys:
167: + -ksp_ksp_type <solver> - the type of the inner solver (GMRES or any of its variants for instance)
168: . -ksp_pc_type <preconditioner> - the type of the preconditioner applied to the inner solver
169: . -ksp_ksp_max_it <maxits> - the maximum number of inner iterations (iterations of the inner solver)
170: . -ksp_ksp_rtol <tol> - sets the relative convergence tolerance of the inner solver
171: . -ksp_tsirm_cgls <number> - if 1 use CGLS solver in the minimization step, otherwise use LSQR solver
172: . -ksp_tsirm_max_it_ls <maxits> - the maximum number of iterations for the least-squares minimization solver
173: . -ksp_tsirm_tol_ls <tol> - sets the convergence tolerance of the least-squares minimization solver
174: - -ksp_tsirm_size_ls <size> - the number of residuals for the least-squares minimization step
176: Level: advanced
178: Notes: TSIRM is a new two-stage iteration method for solving large sparse linear systems of the form Ax=b. The main idea behind this new
179: method is the use a least-squares residual minimization to improve the convergence of Krylov based iterative methods, typically those of GMRES variants.
180: The principle of TSIRM algorithm is to build an outer iteration over a Krylov method, called inner solver, and to frequently store the current residual
181: computed by the given Krylov method in a matrix of residuals S. After a few outer iterations, a least-squares minimization step is applied on the matrix
182: composed by the saved residuals, in order to compute a better solution and to make new iterations if required. The GMRES method , or any of its variants,
183: can potentially be used as inner solver. The minimization step consists in solving the least-squares problem min||b-ASa|| to find 'a' which minimizes the
184: residuals (b-AS). The minimization step is performed using two solvers of linear least-squares problems: CGLS or LSQR. A new solution x with
185: a minimal residual is computed with x=Sa.
187: References:
188: . 1 R. Couturier, L. Ziane Khodja, and C. Guyeux. TSIRM: A Two-Stage Iteration with least-squares Residual Minimization algorithm to solve large sparse linear systems. In PDSEC 2015, 16th IEEE Int. Workshop on Parallel and Distributed Scientific and Engineering Computing (in conjunction with IPDPS 2015), Hyderabad, India, 2015.
190: Contributed by: Lilia Ziane Khodja
192: .seealso: KSPCreate(), KSPSetType(), KSPType (for list of available types), KSP, KSPFGMRES, KSPLGMRES,
193: KSPGMRESSetRestart(), KSPGMRESSetHapTol(), KSPGMRESSetPreAllocateVectors(), KSPGMRESSetOrthogonalization(), KSPGMRESGetOrthogonalization(),
194: KSPGMRESClassicalGramSchmidtOrthogonalization(), KSPGMRESModifiedGramSchmidtOrthogonalization(),
195: KSPGMRESCGSRefinementType, KSPGMRESSetCGSRefinementType(), KSPGMRESGetCGSRefinementType(), KSPGMRESMonitorKrylov(), KSPSetPCSide()
197: M*/
198: PETSC_EXTERN PetscErrorCode KSPCreate_TSIRM(KSP ksp)
199: {
201: KSP_TSIRM *tsirm;
202:
204: PetscNewLog(ksp,&tsirm);
205: ksp->data = (void*)tsirm;
206: KSPSetSupportedNorm(ksp,KSP_NORM_PRECONDITIONED,PC_LEFT,2);
207: KSPSetSupportedNorm(ksp,KSP_NORM_UNPRECONDITIONED,PC_RIGHT,1);
208: ksp->ops->setup = KSPSetUp_TSIRM;
209: ksp->ops->solve = KSPSolve_TSIRM;
210: ksp->ops->destroy = KSPDestroy_TSIRM;
211: ksp->ops->buildsolution = KSPBuildSolutionDefault;
212: ksp->ops->buildresidual = KSPBuildResidualDefault;
213: ksp->ops->setfromoptions = KSPSetFromOptions_TSIRM;
214: ksp->ops->view = 0;
215: #if defined(PETSC_USE_COMPLEX)
216: SETERRQ(PetscObjectComm((PetscObject)ksp),PETSC_ERR_SUP,"This is not supported for complex numbers");
217: #endif
218: return(0);
219: }