PetscSolverSchur.cc 14.7 KB
Newer Older
Thomas Witkowski's avatar
Thomas Witkowski committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
//
// Software License for AMDiS
//
// Copyright (c) 2010 Dresden University of Technology 
// All rights reserved.
// Authors: Simon Vey, Thomas Witkowski et al.
//
// This file is part of AMDiS
//
// See also license.opensource.txt in the distribution.


#include "parallel/PetscSolverSchur.h"
#include "parallel/StdMpi.h"
#include "parallel/MpiHelper.h"

namespace AMDiS {

  using namespace std;

  void PetscSolverSchur::updateDofData(int nComponents)
  {
    FUNCNAME("PetscSolverSchur::updateDofData()");

    TEST_EXIT_DBG(meshDistributor)("No mesh distributor object defined!\n");
26
    TEST_EXIT_DBG(dofMap)("No parallel DOF map defined!\n");
Thomas Witkowski's avatar
Thomas Witkowski committed
27

28
    const FiniteElemSpace *feSpace = meshDistributor->getFeSpace(0);
Thomas Witkowski's avatar
Thomas Witkowski committed
29 30 31 32 33
    typedef map<int, DofContainer> RankToDofContainer;
    typedef map<DegreeOfFreedom, bool> DofIndexToBool;

    boundaryDofs.clear();
    std::set<DegreeOfFreedom> boundaryLocalDofs;
34
    for (DofComm::Iterator it(meshDistributor->getDofComm().getSendDofs(), feSpace);
35 36 37
	 !it.end(); it.nextRank())
      for (; !it.endDofIter(); it.nextDof()) {
	boundaryLocalDofs.insert(it.getDofIndex());	  
38
	boundaryDofs.insert((*dofMap)[feSpace][it.getDofIndex()].global);
Thomas Witkowski's avatar
Thomas Witkowski committed
39
      }
40

41
      
Thomas Witkowski's avatar
Thomas Witkowski committed
42 43 44 45
    nBoundaryDofs = boundaryDofs.size();
    mpi::getDofNumbering(mpiComm, nBoundaryDofs, 
			 rStartBoundaryDofs, nOverallBoundaryDofs);

46

47
    DofContainerSet& edgeDofs = 
48
      meshDistributor->getBoundaryDofInfo(feSpace, 0).geoDofs[EDGE];
49
    DofContainerSet& vertexDofs = 
50
      meshDistributor->getBoundaryDofInfo(feSpace, 0).geoDofs[VERTEX];
51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
    int nEdgeDofs = edgeDofs.size();
    int nVertexDofs = vertexDofs.size();

    TEST_EXIT_DBG(nEdgeDofs + nVertexDofs == nBoundaryDofs)
      ("Should not happen!\n");

    int rStartEdgeDofs, nOverallEdgeDofs;
    mpi::getDofNumbering(mpiComm, nEdgeDofs, 
			 rStartEdgeDofs, nOverallEdgeDofs);

    int rStartVertexDofs, nOverallVertexDofs;
    mpi::getDofNumbering(mpiComm, nVertexDofs, 
			 rStartVertexDofs, nOverallVertexDofs);

    TEST_EXIT_DBG(nOverallEdgeDofs + nOverallVertexDofs == nOverallBoundaryDofs)
      ("Should not happen!\n");
    

Thomas Witkowski's avatar
Thomas Witkowski committed
69
    mapGlobalBoundaryDof.clear();
70 71 72 73 74
#if 1
    {
      int counter = rStartEdgeDofs;
      for (DofContainerSet::iterator it = edgeDofs.begin();
	   it != edgeDofs.end(); ++it)
75
	mapGlobalBoundaryDof[(*dofMap)[feSpace][**it].global] = 
76 77 78 79 80 81
	  counter++;
    }
    {
      int counter = nOverallEdgeDofs + rStartVertexDofs;
      for (DofContainerSet::iterator it = vertexDofs.begin();
	   it != vertexDofs.end(); ++it)
82
	mapGlobalBoundaryDof[(*dofMap)[feSpace][**it].global] = 
83 84 85 86 87
	  counter++;
    }
#else
 {
    int counter = rStartBoundaryDofs;
Thomas Witkowski's avatar
Thomas Witkowski committed
88 89 90
    for (std::set<DegreeOfFreedom>::iterator it = boundaryDofs.begin();
	 it != boundaryDofs.end(); ++it)
      mapGlobalBoundaryDof[*it] = counter++;
91 92
 }
#endif
Thomas Witkowski's avatar
Thomas Witkowski committed
93 94 95


    std::set<DegreeOfFreedom> otherBoundaryLocalDofs;
96
    for (DofComm::Iterator it(meshDistributor->getDofComm().getRecvDofs(), feSpace);
97 98 99
	 !it.end(); it.nextRank())
      for (; !it.endDofIter(); it.nextDof())
	otherBoundaryLocalDofs.insert(it.getDofIndex());
Thomas Witkowski's avatar
Thomas Witkowski committed
100 101
      
    interiorDofs.clear();
Thomas Witkowski's avatar
Thomas Witkowski committed
102 103 104

    ERROR_EXIT("Rewrite the following code block!\n");
#if 0
105
    DofIndexToBool& isRankDof = meshDistributor->getIsRankDof(feSpace);
Thomas Witkowski's avatar
Thomas Witkowski committed
106 107 108 109 110
    for (DofIndexToBool::iterator dofIt = isRankDof.begin(); 
	 dofIt != isRankDof.end(); ++dofIt) {
      if (dofIt->second && 
	  boundaryLocalDofs.count(dofIt->first) == 0 && 
	  otherBoundaryLocalDofs.count(dofIt->first) == 0)
111
	interiorDofs.insert(meshDistributor->mapDofToGlobal(feSpace, dofIt->first));
Thomas Witkowski's avatar
Thomas Witkowski committed
112
    }
Thomas Witkowski's avatar
Thomas Witkowski committed
113
#endif
Thomas Witkowski's avatar
Thomas Witkowski committed
114 115 116 117 118
      
    nInteriorDofs = interiorDofs.size();
    mpi::getDofNumbering(mpiComm, nInteriorDofs, 
			 rStartInteriorDofs, nOverallInteriorDofs);

119 120 121 122 123 124 125
    {
      int counter = rStartInteriorDofs;
      mapGlobalInteriorDof.clear();
      for (std::set<DegreeOfFreedom>::iterator it = interiorDofs.begin();
	   it != interiorDofs.end(); ++it)
	mapGlobalInteriorDof[*it] = counter++;
    }
Thomas Witkowski's avatar
Thomas Witkowski committed
126 127 128 129 130


    TEST_EXIT_DBG(nInteriorDofs > 0)("Should not happen!\n");


131
    StdMpi<vector<DegreeOfFreedom> > stdMpi(mpiComm);
132
    for (DofComm::Iterator it(meshDistributor->getDofComm().getSendDofs(), feSpace);
133 134 135 136 137
	 !it.end(); it.nextRank()) {
      stdMpi.getSendData(it.getRank()).resize(0);
      stdMpi.getSendData(it.getRank()).reserve(it.getDofs().size());

      for (; !it.endDofIter(); it.nextDof()) {
138
	int globalSendDof = (*dofMap)[feSpace][it.getDofIndex()].global;
Thomas Witkowski's avatar
Thomas Witkowski committed
139 140 141 142

	TEST_EXIT_DBG(mapGlobalBoundaryDof.count(globalSendDof))
	  ("No mapping for boundary DOF %d!\n", globalSendDof);

143
	stdMpi.getSendData(it.getRank()).push_back(mapGlobalBoundaryDof[globalSendDof]);
Thomas Witkowski's avatar
Thomas Witkowski committed
144
      }
145
    }
Thomas Witkowski's avatar
Thomas Witkowski committed
146 147

    stdMpi.updateSendDataSize();
148

149
    for (DofComm::Iterator it(meshDistributor->getDofComm().getRecvDofs(), feSpace);
150 151
	 !it.end(); it.nextRank())
      stdMpi.recv(it.getRank());
Thomas Witkowski's avatar
Thomas Witkowski committed
152

153
    stdMpi.startCommunication();
154

155
    for (DofComm::Iterator it(meshDistributor->getDofComm().getRecvDofs(), feSpace);
156 157
	 !it.end(); it.nextRank())
      for (; !it.endDofIter(); it.nextDof()) {
158
	int globalRecvDof = (*dofMap)[feSpace][it.getDofIndex()].global;
159 160
	mapGlobalBoundaryDof[globalRecvDof] = 
	  stdMpi.getRecvData(it.getRank())[it.getDofCounter()];
Thomas Witkowski's avatar
Thomas Witkowski committed
161 162 163 164 165 166
	boundaryDofs.insert(globalRecvDof);
      }


    // === Create PETSc IS structurs for interior and boundary DOFs. ===

167
    ISCreateStride(mpiComm, 
Thomas Witkowski's avatar
Thomas Witkowski committed
168 169 170 171
		   nInteriorDofs * nComponents,
		   (rStartInteriorDofs + rStartBoundaryDofs) * nComponents, 
		   1, &interiorIs);

172
    ISCreateStride(mpiComm,
Thomas Witkowski's avatar
Thomas Witkowski committed
173 174 175 176 177 178
		   nBoundaryDofs * nComponents,
		   (rStartInteriorDofs + rStartBoundaryDofs + nInteriorDofs) * nComponents, 
		   1, &boundaryIs);
  }


179
  void PetscSolverSchur::fillPetscMatrix(Matrix<DOFMatrix*> *mat)
Thomas Witkowski's avatar
Thomas Witkowski committed
180 181
  {
    FUNCNAME("PetscSolverSchur::fillPetscMatrix()");
182 183

    const FiniteElemSpace *feSpace = meshDistributor->getFeSpace(0);
Thomas Witkowski's avatar
Thomas Witkowski committed
184 185 186 187 188 189 190 191 192
    int nComponents = mat->getNumRows();
    updateDofData(nComponents);

    int nInteriorRows = nInteriorDofs * nComponents;
    int nOverallInteriorRows = nOverallInteriorDofs * nComponents;
    int nBoundaryRows = nBoundaryDofs * nComponents;
    int nOverallBoundaryRows = nOverallBoundaryDofs * nComponents;


193
    MatCreateMPIAIJ(mpiComm, 
Thomas Witkowski's avatar
Thomas Witkowski committed
194 195 196 197
		    nInteriorRows, nInteriorRows, 
		    nOverallInteriorRows, nOverallInteriorRows,
		    100, PETSC_NULL, 100, PETSC_NULL, &matA11);

198
    MatCreateMPIAIJ(mpiComm, 
Thomas Witkowski's avatar
Thomas Witkowski committed
199 200 201 202
		    nBoundaryRows, nBoundaryRows, 
		    nOverallBoundaryRows, nOverallBoundaryRows,
		    100, PETSC_NULL, 100, PETSC_NULL, &matA22);

203
    MatCreateMPIAIJ(mpiComm, 
Thomas Witkowski's avatar
Thomas Witkowski committed
204 205 206 207
		    nInteriorRows, nBoundaryRows, 
		    nOverallInteriorRows, nOverallBoundaryRows,
		    100, PETSC_NULL, 100, PETSC_NULL, &matA12);    

208
    MatCreateMPIAIJ(mpiComm, 
Thomas Witkowski's avatar
Thomas Witkowski committed
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240
		    nBoundaryRows, nInteriorRows, 
		    nOverallBoundaryRows, nOverallInteriorRows,
		    100, PETSC_NULL, 100, PETSC_NULL, &matA21);


    for (int i = 0; i < nComponents; i++)
      for (int j = 0; j < nComponents; j++)
	if ((*mat)[i][j])
	  setDofMatrix((*mat)[i][j], nComponents, i, j);

    MatAssemblyBegin(matA11, MAT_FINAL_ASSEMBLY);
    MatAssemblyEnd(matA11, MAT_FINAL_ASSEMBLY);

    MatAssemblyBegin(matA12, MAT_FINAL_ASSEMBLY);
    MatAssemblyEnd(matA12, MAT_FINAL_ASSEMBLY);

    MatAssemblyBegin(matA21, MAT_FINAL_ASSEMBLY);
    MatAssemblyEnd(matA21, MAT_FINAL_ASSEMBLY);

    MatAssemblyBegin(matA22, MAT_FINAL_ASSEMBLY);
    MatAssemblyEnd(matA22, MAT_FINAL_ASSEMBLY);

    Mat tmpMat[2][2];
    tmpMat[0][0] = matA11;
    tmpMat[0][1] = matA12;
    tmpMat[1][0] = matA21;
    tmpMat[1][1] = matA22;

    IS tmpIS[2];
    tmpIS[0] = interiorIs;
    tmpIS[1] = boundaryIs;

241
    MatCreateNest(mpiComm, 2, &tmpIS[0], 2, &tmpIS[0], &tmpMat[0][0], &petscMatrix);
Thomas Witkowski's avatar
Thomas Witkowski committed
242 243 244 245 246
    MatNestSetVecType(petscMatrix, VECNEST);
    MatAssemblyBegin(petscMatrix, MAT_FINAL_ASSEMBLY);
    MatAssemblyEnd(petscMatrix, MAT_FINAL_ASSEMBLY);


247 248
    int nRankRows = (*dofMap)[feSpace].nRankDofs * nComponents;
    int nOverallRows = (*dofMap)[feSpace].nOverallDofs * nComponents;
Thomas Witkowski's avatar
Thomas Witkowski committed
249

250 251
    VecCreateMPI(mpiComm, nRankRows, nOverallRows, &petscSolVec);
    VecCreateMPI(mpiComm, nRankRows, nOverallRows, &petscTmpVec);
252 253
  }

Thomas Witkowski's avatar
Thomas Witkowski committed
254

255 256 257
  void PetscSolverSchur::fillPetscRhs(SystemVector *vec)
  {
    FUNCNAME("PetscSolverSchur::fillPetscRhs()");
Thomas Witkowski's avatar
Thomas Witkowski committed
258

259
    const FiniteElemSpace *feSpace = meshDistributor->getFeSpace(0);
260
    int nComponents = vec->getSize();
261 262
    int nRankRows = (*dofMap)[feSpace].nRankDofs * nComponents;
    int nOverallRows = (*dofMap)[feSpace].nOverallDofs * nComponents;
Thomas Witkowski's avatar
Thomas Witkowski committed
263

264
    VecCreateMPI(mpiComm, nRankRows, nOverallRows, &petscRhsVec);
Thomas Witkowski's avatar
Thomas Witkowski committed
265 266 267 268 269 270 271 272 273

    for (int i = 0; i < nComponents; i++)
      setDofVector(petscRhsVec, vec->getDOFVector(i), nComponents, i);

    VecAssemblyBegin(petscRhsVec);
    VecAssemblyEnd(petscRhsVec);
  }


274 275
  void PetscSolverSchur::solvePetscMatrix(SystemVector &vec, 
					  AdaptInfo *adaptInfo)
Thomas Witkowski's avatar
Thomas Witkowski committed
276 277 278
  {
    FUNCNAME("PetscSolverSchur::solvePetscMatrix()");

279
    const FiniteElemSpace *feSpace = meshDistributor->getFeSpace(0);
Thomas Witkowski's avatar
Thomas Witkowski committed
280 281
    int nComponents = vec.getSize();

282
    KSPCreate(mpiComm, &solver);
Thomas Witkowski's avatar
Thomas Witkowski committed
283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304

    KSPSetOperators(solver, petscMatrix, petscMatrix, SAME_NONZERO_PATTERN); 
    KSPSetTolerances(solver, 0.0, 1e-8, PETSC_DEFAULT, PETSC_DEFAULT);
    KSPSetFromOptions(solver);

    KSPGetPC(solver, &pc);
    PCSetType(pc, PCFIELDSPLIT);
    PCFieldSplitSetIS(pc, "interior", interiorIs);
    PCFieldSplitSetIS(pc, "boundary", boundaryIs);
    PCSetFromOptions(pc);


    KSPSolve(solver, petscRhsVec, petscSolVec);

    // === Transfere values from PETSc's solution vectors to AMDiS vectors. ===

    PetscScalar *vecPointer;
    VecGetArray(petscSolVec, &vecPointer);

    for (int i = 0; i < nComponents; i++) {
      DOFVector<double>::Iterator dofIt(vec.getDOFVector(i), USED_DOFS);
      for (dofIt.reset(); !dofIt.end(); ++dofIt) {
305
	DegreeOfFreedom globalRowDof = (*dofMap)[feSpace][dofIt.getDOFIndex()].global;
Thomas Witkowski's avatar
Thomas Witkowski committed
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332
	if (boundaryDofs.count(globalRowDof)) {
	  int index =
	    (mapGlobalBoundaryDof[globalRowDof] - rStartBoundaryDofs + nInteriorDofs) * (i + 1);
	  *dofIt = vecPointer[index];
	} else {
	  int index = 
	    (mapGlobalInteriorDof[globalRowDof] - rStartInteriorDofs) * (i + 1);
	  *dofIt = vecPointer[index];
	}
      }
    }

    VecRestoreArray(petscSolVec, &vecPointer);


    // === Synchronize DOFs at common DOFs, i.e., DOFs that correspond to ===
    // === more than one partition.                                       ===
    meshDistributor->synchVector(vec);



    // === Print iteration counter and residual norm of the solution. ===
    printSolutionInfo(adaptInfo);


    // === Destroy PETSC's variables. ===

333 334 335
    VecDestroy(&petscRhsVec);
    VecDestroy(&petscSolVec);
    VecDestroy(&petscTmpVec);
Thomas Witkowski's avatar
Thomas Witkowski committed
336

337 338 339 340 341
    MatDestroy(&matA11);
    MatDestroy(&matA12);
    MatDestroy(&matA21);
    MatDestroy(&matA22);
    MatDestroy(&petscMatrix);
Thomas Witkowski's avatar
Thomas Witkowski committed
342

343
    KSPDestroy(&solver);
Thomas Witkowski's avatar
Thomas Witkowski committed
344 345 346 347 348 349 350 351 352 353
  }
  

  void PetscSolverSchur::setDofMatrix(DOFMatrix* mat, int dispMult, 
				      int dispAddRow, int dispAddCol)
  {
    FUNCNAME("PetscSolverSchur::setDofMatrix()");

    TEST_EXIT(mat)("No DOFMatrix!\n");

354
    const FiniteElemSpace* feSpace = meshDistributor->getFeSpace(0);
Thomas Witkowski's avatar
Thomas Witkowski committed
355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375
    using mtl::tag::row; using mtl::tag::nz; using mtl::begin; using mtl::end;
    namespace traits= mtl::traits;
    typedef DOFMatrix::base_matrix_type Matrix;

    traits::col<Matrix>::type col(mat->getBaseMatrix());
    traits::const_value<Matrix>::type value(mat->getBaseMatrix());

    typedef traits::range_generator<row, Matrix>::type cursor_type;
    typedef traits::range_generator<nz, cursor_type>::type icursor_type;

    vector<int> colsBoundary, colsInterior;
    vector<double> valuesBoundary, valuesInterior;
    colsBoundary.reserve(300);
    colsInterior.reserve(300);
    valuesBoundary.reserve(300);
    valuesInterior.reserve(300);

    for (cursor_type cursor = begin<row>(mat->getBaseMatrix()), 
	   cend = end<row>(mat->getBaseMatrix()); cursor != cend; ++cursor) {

      // Global index of the current row DOF.
376
      int globalRowDof = (*dofMap)[feSpace][*cursor].global;
Thomas Witkowski's avatar
Thomas Witkowski committed
377 378 379 380 381 382 383 384
     
      colsBoundary.clear();
      colsInterior.clear();
      valuesBoundary.clear();
      valuesInterior.clear();
      
      for (icursor_type icursor = begin<nz>(cursor), icend = end<nz>(cursor); 
	   icursor != icend; ++icursor) {
385
	int globalColDof = (*dofMap)[feSpace][col(*icursor)].global;
Thomas Witkowski's avatar
Thomas Witkowski committed
386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439

	if (boundaryDofs.count(globalColDof)) {
	  TEST_EXIT_DBG(mapGlobalBoundaryDof.count(globalColDof))
	    ("Should not happen!\n");

	  int colIndex = 
	    mapGlobalBoundaryDof[globalColDof] * dispMult + dispAddCol;
	  
	  colsBoundary.push_back(colIndex);
	  valuesBoundary.push_back(value(*icursor));
	} else {
	  TEST_EXIT_DBG(mapGlobalInteriorDof.count(globalColDof))
	    ("Cannot find global interior mapping for global column DOF %d!\n", 
	     globalColDof);

	  int colIndex = 
	    mapGlobalInteriorDof[globalColDof] * dispMult + dispAddCol;

	  colsInterior.push_back(colIndex);
	  valuesInterior.push_back(value(*icursor));
	}
      }

      if (boundaryDofs.count(globalRowDof)) {
	TEST_EXIT_DBG(mapGlobalBoundaryDof.count(globalRowDof))
	  ("Should not happen!\n");

	int rowIndex = 
	  mapGlobalBoundaryDof[globalRowDof] * dispMult + dispAddRow;

 	MatSetValues(matA22, 1, &rowIndex, colsBoundary.size(), 
 		     &(colsBoundary[0]), &(valuesBoundary[0]), ADD_VALUES);
 	MatSetValues(matA21, 1, &rowIndex, colsInterior.size(), 
 		     &(colsInterior[0]), &(valuesInterior[0]), ADD_VALUES);
      } else {
	TEST_EXIT_DBG(mapGlobalInteriorDof.count(globalRowDof))
	  ("Cannot find global interior mapping for global row DOF %d!\n", 
	   globalRowDof);

	int rowIndex = 
	  mapGlobalInteriorDof[globalRowDof] * dispMult + dispAddRow;

  	MatSetValues(matA11, 1, &rowIndex, colsInterior.size(), 
  		     &(colsInterior[0]), &(valuesInterior[0]), ADD_VALUES);
  	MatSetValues(matA12, 1, &rowIndex, colsBoundary.size(), 
  		     &(colsBoundary[0]), &(valuesBoundary[0]), ADD_VALUES);
      }
    }
  }


  void PetscSolverSchur::setDofVector(Vec& petscVec, DOFVector<double>* vec,
				      int dispMult, int dispAdd, bool rankOnly)
  {
440 441
    const FiniteElemSpace *feSpace = meshDistributor->getFeSpace(0);

Thomas Witkowski's avatar
Thomas Witkowski committed
442 443
    DOFVector<double>::Iterator dofIt(vec, USED_DOFS);
    for (dofIt.reset(); !dofIt.end(); ++dofIt) {
444
      if (rankOnly && !(*dofMap)[feSpace].isRankDof(dofIt.getDOFIndex()))
Thomas Witkowski's avatar
Thomas Witkowski committed
445 446
	continue;

447
      // Calculate global row index of the DOF.
Thomas Witkowski's avatar
Thomas Witkowski committed
448
      DegreeOfFreedom globalRowDof = 
449
	(*dofMap)[feSpace][dofIt.getDOFIndex()].global;
Thomas Witkowski's avatar
Thomas Witkowski committed
450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473
      double value = *dofIt;

      if (boundaryDofs.count(globalRowDof)) {
	TEST_EXIT_DBG(mapGlobalBoundaryDof.count(globalRowDof))
	  ("Should not happen!\n");

	int index = 
	  (rStartInteriorDofs + 
	   nInteriorDofs +
	   mapGlobalBoundaryDof[globalRowDof]) * dispMult + dispAdd;
	VecSetValues(petscRhsVec, 1, &index, &value, ADD_VALUES);
      } else {
	TEST_EXIT_DBG(mapGlobalInteriorDof.count(globalRowDof))
	  ("Should not happen!\n");
	
	int index = 
	  (rStartBoundaryDofs + 
	   mapGlobalInteriorDof[globalRowDof]) * dispMult + dispAdd;
	VecSetValues(petscRhsVec, 1, &index, &value, ADD_VALUES);
      }
    }
  }

}