// @HEADER // ***************************************************************************** // MueLu: A package for multigrid based preconditioning // // Copyright 2012 NTESS and the MueLu contributors. // SPDX-License-Identifier: BSD-3-Clause // ***************************************************************************** // @HEADER #include "MueLu_SmootherBase.hpp" #ifndef MUELU_SMOOVECCOALESCEDROPFACTORY_DEF_HPP #define MUELU_SMOOVECCOALESCEDROPFACTORY_DEF_HPP #include #include #include #include #include #include #include #include #include #include #include "MueLu_SmooVecCoalesceDropFactory_decl.hpp" #include "MueLu_Exceptions.hpp" #include "MueLu_LWGraph.hpp" #include "MueLu_Level.hpp" #include "MueLu_LWGraph.hpp" #include "MueLu_MasterList.hpp" #include "MueLu_Monitor.hpp" #include "MueLu_PreDropFunctionBaseClass.hpp" #include #include #include #include // If defined, read environment variables. // Should be removed once we are confident that this works. // #define DJS_READ_ENV_VARIABLES #include #include #include #define poly0thOrderCoef 0 #define poly1stOrderCoef 1 #define poly2ndOrderCoef 2 #define poly3rdOrderCoef 3 #define poly4thOrderCoef 4 namespace MueLu { template RCP SmooVecCoalesceDropFactory::GetValidParameterList() const { RCP validParamList = rcp(new ParameterList()); #define SET_VALID_ENTRY(name) validParamList->setEntry(name, MasterList::getEntry(name)) SET_VALID_ENTRY("aggregation: drop scheme"); { validParamList->getEntry("aggregation: drop scheme").setValidator(rcp(new Teuchos::StringValidator(Teuchos::tuple("classical", "distance laplacian", "unsupported vector smoothing")))); } SET_VALID_ENTRY("aggregation: number of random vectors"); SET_VALID_ENTRY("aggregation: number of times to pre or post smooth"); SET_VALID_ENTRY("aggregation: penalty parameters"); #undef SET_VALID_ENTRY validParamList->set >("A", Teuchos::null, "Generating factory of the matrix A"); validParamList->set >("PreSmoother", Teuchos::null, "Generating factory of the PreSmoother"); validParamList->set >("PostSmoother", Teuchos::null, "Generating factory of the PostSmoother"); return validParamList; } template SmooVecCoalesceDropFactory::SmooVecCoalesceDropFactory() : predrop_(Teuchos::null) {} template void SmooVecCoalesceDropFactory::DeclareInput(Level& currentLevel) const { Input(currentLevel, "A"); if (currentLevel.IsAvailable("PreSmoother")) { // rst: totally unsure that this is legal Input(currentLevel, "PreSmoother"); // my guess is that this is not yet available } // so this always comes out false. else if (currentLevel.IsAvailable("PostSmoother")) { // perhaps we can look on the param list? Input(currentLevel, "PostSmoother"); } } template void SmooVecCoalesceDropFactory::Build(Level& currentLevel) const { FactoryMonitor m(*this, "Build", currentLevel); typedef Teuchos::ScalarTraits STS; if (predrop_ != Teuchos::null) GetOStream(Parameters0) << predrop_->description(); RCP A = Get >(currentLevel, "A"); const ParameterList& pL = GetParameterList(); LO nPDEs = A->GetFixedBlockSize(); RCP testVecs; RCP nearNull; #ifdef takeOut testVecs = Xpetra::IO::ReadMultiVector("TpetraTVecs.mm", A->getRowMap()); #endif size_t numRandom = as(pL.get("aggregation: number of random vectors")); testVecs = MultiVectorFactory::Build(A->getRowMap(), numRandom, true); // use random test vectors but should be positive in order to not get // crummy results ... so take abs() of randomize(). testVecs->randomize(); for (size_t kk = 0; kk < testVecs->getNumVectors(); kk++) { Teuchos::ArrayRCP curVec = testVecs->getDataNonConst(kk); for (size_t ii = kk; ii < as(A->getRowMap()->getLocalNumElements()); ii++) curVec[ii] = Teuchos::ScalarTraits::magnitude(curVec[ii]); } nearNull = MultiVectorFactory::Build(A->getRowMap(), nPDEs, true); // initialize null space to constants for (size_t kk = 0; kk < nearNull->getNumVectors(); kk++) { Teuchos::ArrayRCP curVec = nearNull->getDataNonConst(kk); for (size_t ii = kk; ii < as(A->getRowMap()->getLocalNumElements()); ii += nearNull->getNumVectors()) curVec[ii] = Teuchos::ScalarTraits::one(); } RCP zeroVec_TVecs; RCP zeroVec_Null; zeroVec_TVecs = MultiVectorFactory::Build(A->getRowMap(), testVecs->getNumVectors(), true); zeroVec_Null = MultiVectorFactory::Build(A->getRowMap(), nPDEs, true); zeroVec_TVecs->putScalar(Teuchos::ScalarTraits::zero()); zeroVec_Null->putScalar(Teuchos::ScalarTraits::zero()); size_t nInvokeSmoother = as(pL.get("aggregation: number of times to pre or post smooth")); if (currentLevel.IsAvailable("PreSmoother")) { RCP preSmoo = currentLevel.Get >("PreSmoother"); for (size_t ii = 0; ii < nInvokeSmoother; ii++) preSmoo->Apply(*testVecs, *zeroVec_TVecs, false); for (size_t ii = 0; ii < nInvokeSmoother; ii++) preSmoo->Apply(*nearNull, *zeroVec_Null, false); } else if (currentLevel.IsAvailable("PostSmoother")) { RCP postSmoo = currentLevel.Get >("PostSmoother"); for (size_t ii = 0; ii < nInvokeSmoother; ii++) postSmoo->Apply(*testVecs, *zeroVec_TVecs, false); for (size_t ii = 0; ii < nInvokeSmoother; ii++) postSmoo->Apply(*nearNull, *zeroVec_Null, false); } else TEUCHOS_TEST_FOR_EXCEPTION(true, Exceptions::RuntimeError, "Must set a smoother"); Teuchos::ArrayRCP penaltyPolyCoef(5); Teuchos::ArrayView inputPolyCoef; penaltyPolyCoef[poly0thOrderCoef] = 12.; penaltyPolyCoef[poly1stOrderCoef] = -.2; penaltyPolyCoef[poly2ndOrderCoef] = 0.0; penaltyPolyCoef[poly3rdOrderCoef] = 0.0; penaltyPolyCoef[poly4thOrderCoef] = 0.0; if (pL.isParameter("aggregation: penalty parameters") && pL.get >("aggregation: penalty parameters").size() > 0) { if (pL.get >("aggregation: penalty parameters").size() > penaltyPolyCoef.size()) TEUCHOS_TEST_FOR_EXCEPTION(true, Exceptions::RuntimeError, "Number of penalty parameters must be " << penaltyPolyCoef.size() << " or less"); inputPolyCoef = pL.get >("aggregation: penalty parameters")(); for (size_t i = 0; i < as(inputPolyCoef.size()); i++) penaltyPolyCoef[i] = as(inputPolyCoef[i]); for (size_t i = as(inputPolyCoef.size()); i < as(penaltyPolyCoef.size()); i++) penaltyPolyCoef[i] = Teuchos::ScalarTraits::zero(); } RCP filteredGraph; badGuysCoalesceDrop(*A, penaltyPolyCoef, nPDEs, *testVecs, *nearNull, filteredGraph); #ifdef takeOut /* write out graph for serial debugging purposes only. */ FILE* fp = fopen("codeOutput", "w"); fprintf(fp, "%d %d %d\n", (int)filteredGraph->GetNodeNumVertices(), (int)filteredGraph->GetNodeNumVertices(), (int)filteredGraph->GetNodeNumEdges()); for (size_t i = 0; i < filteredGraph->GetNodeNumVertices(); i++) { auto inds = filteredGraph->getNeighborVertices(as(i)); for (size_t j = 0; j < as(inds.size()); j++) { fprintf(fp, "%d %d 1.00e+00\n", (int)i + 1, (int)inds[j] + 1); } } fclose(fp); #endif SC threshold = .01; Set(currentLevel, "Filtering", (threshold != STS::zero())); Set(currentLevel, "Graph", filteredGraph); Set(currentLevel, "DofsPerNode", 1); } // Build template void SmooVecCoalesceDropFactory::badGuysCoalesceDrop(const Matrix& Amat, Teuchos::ArrayRCP& penaltyPolyCoef, LO nPDEs, const MultiVector& testVecs, const MultiVector& nearNull, RCP& filteredGraph) const { /* * Compute coalesce/drop graph (in filteredGraph) for A. The basic idea is to * balance trade-offs associated with * * (I - P inv(R P) R ) testVecs * * being worse for larger aggregates (less dropping) while MG cycle costs are * cheaper with larger aggregates. MG costs are "penalties" in the * optimization while (I - P inv(R P) R ) is the "fit" (how well a * a fine grid function can be approximated on the coarse grid). * * For MG costs, we don't actually approximate the cost. Instead, we * have just hardwired penalties below. Specifically, * * penalties[j] is the cost if aggregates are of size j+1, where right * now a linear function of the form const*(60-j) is used. * * (I - P inv(P^T P) P^T ) testVecs is estimated by just looking locally at * the vector portion corresponding to a possible aggregate defined by * all non-dropped connections in the ith row. A tentative prolognator is * used for P. This prolongator corresponds to a null space vector given * by 'nearNull', which is provided to dropper(). In initial testing, nearNull is * first set as a vector of all 1's and then smoothed with a relaxation * method applied to a nice matrix (with the same sparsity pattern as A). * Originally, nearNull was used to handle Dir bcs where relaxation of the * vector of 1's has a more pronounced effect. * * For PDE systems, fit only considers the same dof at each node. That is, * it effectively assumes that we have a tentative prolongator with no * coupling between different dof types. When checking the fit for the kth * dof at a paritcular node, it only considers the kth dof of this node * and neighboring nodes. * * Note: testVecs is supplied by the user, but normally is the result of * applying a relaxation scheme to Au = 0 where u is initial random. */ GO numMyNnz = Teuchos::as(Amat.getLocalNumEntries()); size_t nLoc = Amat.getRowMap()->getLocalNumElements(); size_t nBlks = nLoc / nPDEs; if (nBlks * nPDEs != nLoc) TEUCHOS_TEST_FOR_EXCEPTION(true, Exceptions::RuntimeError, "Number of local dofs not divisible by BlkSize"); typename LWGraph::row_type::non_const_type newRowPtr("newRowPtr", nBlks + 1); /* coalesce & drop matrix */ Teuchos::ArrayRCP newCols(numMyNnz); /* arrays */ Teuchos::ArrayRCP bcols(nBlks); /* returned by dropfun(j,...) */ Teuchos::ArrayRCP keepOrNot(nBlks); /* gives cols for jth row and */ /* whether or not entry is */ /* kept or dropped. */ LO maxNzPerRow = 200; Teuchos::ArrayRCP penalties(maxNzPerRow); /* Penalty function */ /* described above. */ Teuchos::ArrayRCP keepStatus(nBlks, true); /* accumulated keepOrNot info */ Teuchos::ArrayRCP bColList(nBlks); /* accumulated bcols info */ /* for an entire block as */ /* opposed to a single row */ /* Additionally, keepOrNot[j] */ /* refers to status of jth */ /* entry in a row while */ /* keepStatus[j] refers to */ /* whether the jth block is */ /* kept within the block row. */ Teuchos::ArrayRCP alreadyOnBColList(nBlks, false); /* used to avoid recording the*/ /* same block column when */ /* processing different pt */ /* rows within a block. */ typename LWGraph::boundary_nodes_type boundaryNodes("boundaryNodes", nBlks); Kokkos::deep_copy(boundaryNodes, false); for (LO i = 0; i < maxNzPerRow; i++) penalties[i] = penaltyPolyCoef[poly0thOrderCoef] + penaltyPolyCoef[poly1stOrderCoef] * (as(i)) + penaltyPolyCoef[poly2ndOrderCoef] * (as(i * i)) + (penaltyPolyCoef[poly3rdOrderCoef] * (as(i * i)) * (as(i))) + // perhaps avoids overflow? (penaltyPolyCoef[poly4thOrderCoef] * (as(i * i)) * (as(i * i))); LO nzTotal = 0, numBCols = 0, row = -1, Nbcols, bcol; newRowPtr(0) = 0; /* proceed block by block */ for (LO i = 0; i < as(nBlks); i++) { newRowPtr[i + 1] = newRowPtr[i]; for (LO j = 0; j < nPDEs; j++) { row = row + 1; Teuchos::ArrayView indices; Teuchos::ArrayView vals; Amat.getLocalRowView(row, indices, vals); if (indices.size() > maxNzPerRow) { LO oldSize = maxNzPerRow; maxNzPerRow = indices.size() + 100; penalties.resize(as(maxNzPerRow), 0.0); for (LO k = oldSize; k < maxNzPerRow; k++) penalties[k] = penaltyPolyCoef[poly0thOrderCoef] + penaltyPolyCoef[poly1stOrderCoef] * (as(i)) + penaltyPolyCoef[poly2ndOrderCoef] * (as(i * i)) + (penaltyPolyCoef[poly3rdOrderCoef] * (as(i * i)) * (as(i))) + (penaltyPolyCoef[poly4thOrderCoef] * (as(i * i)) * (as(i * i))); } badGuysDropfunc(row, indices, vals, testVecs, nPDEs, penalties, nearNull, bcols, keepOrNot, Nbcols, nLoc); for (LO k = 0; k < Nbcols; k++) { bcol = bcols[k]; /* add to bColList if not already on it */ if (alreadyOnBColList[bcol] == false) { /* for PDE systems only record */ bColList[numBCols++] = bcol; /* neighboring block one time */ alreadyOnBColList[bcol] = true; } /* drop if any pt row within block indicates entry should be dropped */ if (keepOrNot[k] == false) keepStatus[bcol] = false; } /* for (k=0; k < Nbcols; k++) */ } /* for (j = 0; i < nPDEs; j++) */ /* finished with block row. Now record block entries that we keep */ /* and reset keepStatus, bColList, and alreadyOnBColList. */ if (numBCols < 2) boundaryNodes[i] = true; for (LO j = 0; j < numBCols; j++) { bcol = bColList[j]; if (keepStatus[bcol] == true) { newCols[nzTotal] = bColList[j]; newRowPtr(i + 1)++; nzTotal = nzTotal + 1; } keepStatus[bcol] = true; alreadyOnBColList[bcol] = false; bColList[j] = 0; } numBCols = 0; } /* for (i = 0; i < nBlks; i++) */ /* create array of the correct size and copy over newCols to it */ typename LWGraph::entries_type::non_const_type finalCols("finalCols", nzTotal); for (LO i = 0; i < nzTotal; i++) finalCols(i) = newCols[i]; // Not using column map because we do not allow for any off-proc stuff. // Not sure if this is okay. FIXME RCP rowMap = Amat.getRowMap(); // , colMap = Amat.getColMap(); LO nAmalgNodesOnProc = rowMap->getLocalNumElements() / nPDEs; Teuchos::Array nodalGIDs(nAmalgNodesOnProc); typename Teuchos::ScalarTraits::coordinateType temp; for (size_t i = 0; i < as(nAmalgNodesOnProc); i++) { GO gid = rowMap->getGlobalElement(i * nPDEs); temp = ((typename Teuchos::ScalarTraits::coordinateType)(gid)) / ((typename Teuchos::ScalarTraits::coordinateType)(nPDEs)); nodalGIDs[i] = as(floor(temp)); } GO nAmalgNodesGlobal = rowMap->getGlobalNumElements(); GO nBlkGlobal = nAmalgNodesGlobal / nPDEs; if (nBlkGlobal * nPDEs != nAmalgNodesGlobal) TEUCHOS_TEST_FOR_EXCEPTION(true, Exceptions::RuntimeError, "Number of global dofs not divisible by BlkSize"); Teuchos::RCP AmalgRowMap = MapFactory::Build(rowMap->lib(), nBlkGlobal, nodalGIDs(), 0, rowMap->getComm()); filteredGraph = rcp(new LWGraph(newRowPtr, finalCols, AmalgRowMap, AmalgRowMap, "thresholded graph of A")); filteredGraph->SetBoundaryNodeMap(boundaryNodes); } template void SmooVecCoalesceDropFactory::badGuysDropfunc(LO row, const Teuchos::ArrayView& cols, const Teuchos::ArrayView& vals, const MultiVector& testVecs, LO nPDEs, Teuchos::ArrayRCP& penalties, const MultiVector& nearNull, Teuchos::ArrayRCP& Bcols, Teuchos::ArrayRCP& keepOrNot, LO& Nbcols, LO nLoc) const { using TST = Teuchos::ScalarTraits; LO nLeng = cols.size(); typename TST::coordinateType temp; temp = ((typename TST::coordinateType)(row)) / ((typename TST::coordinateType)(nPDEs)); LO blkRow = as(floor(temp)); Teuchos::ArrayRCP badGuy(nLeng, 0.0); Teuchos::ArrayRCP subNull(nLeng, 0.0); /* subset of nearNull */ /* associated with current */ /* dof within node. */ /* Only consider testVecs associated with same dof & on processor. Further */ /* collapse testVecs to a single badGuy vector by basically taking the worst */ /* (least smooth) values for each of the off diags. In particular, we look at*/ /* the ratio of each off-diag test value / diag test value and compare this */ /* with the nearNull vector ratio. The further the testVec ratio is from the */ /* nearNull ratio, the harder is will be to accurately interpolate is these */ /* two guys are aggregated. So, the biggest ratio mismatch is used to choose */ /* the testVec entry associated with each off-diagonal entry. */ for (LO i = 0; i < nLeng; i++) keepOrNot[i] = false; LO diagInd = -1; Nbcols = 0; LO rowDof = row - blkRow * nPDEs; Teuchos::ArrayRCP oneNull = nearNull.getData(as(rowDof)); for (LO i = 0; i < nLeng; i++) { if ((cols[i] < nLoc) && (TST::magnitude(vals[i]) != 0.0)) { /* on processor */ temp = ((typename TST::coordinateType)(cols[i])) / ((typename TST::coordinateType)(nPDEs)); LO colDof = cols[i] - (as(floor(temp))) * nPDEs; if (colDof == rowDof) { /* same dof within node as row */ Bcols[Nbcols] = (cols[i] - colDof) / nPDEs; subNull[Nbcols] = oneNull[cols[i]]; if (cols[i] != row) { /* not diagonal */ Scalar worstRatio = -TST::one(); Scalar targetRatio = subNull[Nbcols] / oneNull[row]; Scalar actualRatio; for (size_t kk = 0; kk < testVecs.getNumVectors(); kk++) { Teuchos::ArrayRCP curVec = testVecs.getData(kk); actualRatio = curVec[cols[i]] / curVec[row]; if (TST::magnitude(actualRatio - targetRatio) > TST::magnitude(worstRatio)) { badGuy[Nbcols] = actualRatio; worstRatio = Teuchos::ScalarTraits::magnitude(actualRatio - targetRatio); } } } else { badGuy[Nbcols] = 1.; keepOrNot[Nbcols] = true; diagInd = Nbcols; } (Nbcols)++; } } } /* Make sure that diagonal entry is in block col list */ if (diagInd == -1) { Bcols[Nbcols] = (row - rowDof) / nPDEs; subNull[Nbcols] = 1.; badGuy[Nbcols] = 1.; keepOrNot[Nbcols] = true; diagInd = Nbcols; (Nbcols)++; } Scalar currentRP = oneNull[row] * oneNull[row]; Scalar currentRTimesBadGuy = oneNull[row] * badGuy[diagInd]; Scalar currentScore = penalties[0]; /* (I - P inv(R*P)*R )=0 for size */ /* size 1 agg, so fit is perfect */ /* starting from a set that only includes the diagonal entry consider adding */ /* one off-diagonal at a time until the fitValue exceeds the penalty term. */ /* Here, the fit value is (I - P inv(R P) R ) and we always consider the */ /* lowest fitValue that is not currently in the set. R and P correspond to */ /* a simple tentaive grid transfer associated with an aggregate that */ /* includes the diagonal, all already determined neighbors, and the potential*/ /* new neighbor */ LO nKeep = 1, flag = 1, minId; Scalar minFit, minFitRP = 0., minFitRTimesBadGuy = 0.; Scalar newRP, newRTimesBadGuy; while (flag == 1) { /* compute a fit for each possible off-diagonal neighbor */ /* that has not already been added as a neighbor */ minFit = 1000000.; minId = -1; for (LO i = 0; i < Nbcols; i++) { if (keepOrNot[i] == false) { keepOrNot[i] = true; /* temporarily view i as non-dropped neighbor */ newRP = currentRP + subNull[i] * subNull[i]; newRTimesBadGuy = currentRTimesBadGuy + subNull[i] * badGuy[i]; Scalar ratio = newRTimesBadGuy / newRP; Scalar newFit = 0.0; for (LO k = 0; k < Nbcols; k++) { if (keepOrNot[k] == true) { Scalar diff = badGuy[k] - ratio * subNull[k]; newFit = newFit + diff * diff; } } if (Teuchos::ScalarTraits::magnitude(newFit) < Teuchos::ScalarTraits::magnitude(minFit)) { minId = i; minFit = newFit; minFitRP = newRP; minFitRTimesBadGuy = newRTimesBadGuy; } keepOrNot[i] = false; } } if (minId == -1) flag = 0; else { minFit = sqrt(minFit); Scalar newScore = penalties[nKeep] + minFit; if (Teuchos::ScalarTraits::magnitude(newScore) < Teuchos::ScalarTraits::magnitude(currentScore)) { nKeep = nKeep + 1; keepOrNot[minId] = true; currentScore = newScore; currentRP = minFitRP; currentRTimesBadGuy = minFitRTimesBadGuy; } else flag = 0; } } } } // namespace MueLu #endif // MUELU_SMOOVECCOALESCEDROPFACTORY_DEF_HPP