Zoltan2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Zoltan2_Sphynx.hpp
Go to the documentation of this file.
1 // @HEADER
2 // *****************************************************************************
3 // Sphynx
4 //
5 // Copyright 2020 NTESS and the Sphynx contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
10 #ifndef _ZOLTAN2_SPHYNXALGORITHM_HPP_
11 #define _ZOLTAN2_SPHYNXALGORITHM_HPP_
12 
13 
15 // This file contains the Sphynx algorithm.
16 //
17 // Sphynx is a graph partitioning algorithm that is based on a spectral method.
18 // It has three major steps:
19 // 1) compute the Laplacian matrix of the input graph,
20 // 2) compute logK+1 eigenvectors on the Laplacian matrix,
21 // 3) use eigenvector entries as coordinates and compute a K-way partition on
22 // them using a geometric method.
23 //
24 // Step1: Sphynx provides three eigenvalue problems and hence Laplacian matrix:
25 // i) combinatorial (Lx = \lambdax, where L = A - D)
26 // ii) generalized (Lx = \lambdaDx, where L = A - D)
27 // iii) normalized (L_nx, \lambdax, where Ln = D^{-1/2}LD^{-1/2}
28 // and L = A - D)
29 //
30 // Step2: Sphynx calls the LOBPCG algorithm provided in Anasazi to obtain
31 // logK+1 eigenvectors.
32 // (Alternately, uses the experimental Randomized eigensolver.)
33 // Step3: Sphynx calls the MJ algorithm provided in Zoltan2Core to compute the
34 // partition.
36 
37 #include "Zoltan2Sphynx_config.h"
38 
41 
44 
45 #include "AnasaziLOBPCGSolMgr.hpp"
46 #include "AnasaziBlockDavidsonSolMgr.hpp"
47 #include "AnasaziGeneralizedDavidsonSolMgr.hpp"
48 #include "AnasaziBlockKrylovSchurSolMgr.hpp"
49 #include "AnasaziRandomizedSolMgr.hpp"
50 #include "AnasaziBasicEigenproblem.hpp"
51 #include "AnasaziTpetraAdapter.hpp"
52 
53 #include "BelosLinearProblem.hpp"
54 #include "BelosTpetraOperator.hpp"
55 
56 #include "Ifpack2_Factory.hpp"
57 
58 #include "Teuchos_TimeMonitor.hpp"
59 
60 #ifdef HAVE_ZOLTAN2SPHYNX_MUELU
61 #include "MueLu_CreateTpetraPreconditioner.hpp"
62 #endif
63 
64 namespace Zoltan2 {
65 
66  template <typename Adapter>
67  class Sphynx : public Algorithm<Adapter>
68  {
69 
70  public:
71 
72  using scalar_t = double; // Sphynx with scalar_t=double obtains better cutsize
73  using lno_t = typename Adapter::lno_t;
74  using gno_t = typename Adapter::gno_t;
75  using node_t = typename Adapter::node_t;
76  using offset_t = typename Adapter::offset_t;
77  using part_t = typename Adapter::part_t;
78  using weight_t = typename Adapter::scalar_t;
79 
80  using graph_t = Tpetra::CrsGraph<lno_t, gno_t, node_t>;
81  using matrix_t = Tpetra::CrsMatrix<scalar_t, lno_t, gno_t, node_t>;
82  using mvector_t = Tpetra::MultiVector<scalar_t, lno_t, gno_t, node_t>;
83  using op_t = Tpetra::Operator<scalar_t, lno_t, gno_t, node_t>;
84 
86  typedef Anasazi::MultiVecTraits<scalar_t,mvector_t> MVT;
87 
91 
92  // Takes the graph from the input adapter and computes the Laplacian matrix
93  Sphynx(const RCP<const Environment> &env,
94  const RCP<Teuchos::ParameterList> &params,
95  const RCP<Teuchos::ParameterList> &sphynxParams,
96  const RCP<const Comm<int> > &comm,
97  const RCP<const XpetraCrsGraphAdapter<graph_t> > &adapter) :
98  env_(env), params_(params), sphynxParams_(sphynxParams), comm_(comm), adapter_(adapter)
99  {
100 
101  // Don't compute the Laplacian if the number of requested parts is 1
102  const Teuchos::ParameterEntry *pe = params_->getEntryPtr("num_global_parts");
103  numGlobalParts_ = pe->getValue<int>(&numGlobalParts_);
104  if(numGlobalParts_ > 1){
105 
106  Teuchos::TimeMonitor t(*Teuchos::TimeMonitor::getNewTimer("Sphynx::Laplacian"));
107 
108  // The verbosity is common throughout the algorithm, better to check and set now
109  pe = sphynxParams_->getEntryPtr("sphynx_verbosity");
110  if (pe)
111  verbosity_ = pe->getValue<int>(&verbosity_);
112 
113  // Do we need to pre-process the input?
114  pe = sphynxParams_->getEntryPtr("sphynx_skip_preprocessing");
115  if (pe)
116  skipPrep_ = pe->getValue<bool>(&skipPrep_);
117 
118  // Get the graph from XpetraCrsGraphAdapter if skipPrep_ is true
119  // We assume the graph has all of the symmetric and diagonal entries
120  if(skipPrep_)
121  graph_ = adapter_->getUserGraph();
122  else {
123  throw std::runtime_error("\nSphynx Error: Preprocessing has not been implemented yet.\n");
124  }
125 
126  // Check if the graph is regular
128 
129  // Set Sphynx defaults: preconditioner, problem type, tolerance, initial vectors.
130  setDefaults();
131 
132  // Compute the Laplacian matrix
134 
135  if(problemType_ == GENERALIZED)
137 
138  }
139  }
140 
144 
145  void partition(const Teuchos::RCP<PartitioningSolution<Adapter> > &solution);
146 
147  int AnasaziWrapper(const int numEigenVectors);
148 
149  template<typename problem_t>
150  void setPreconditioner(Teuchos::RCP<problem_t> &problem);
151 
152  template<typename problem_t>
153  void setMueLuPreconditioner(Teuchos::RCP<problem_t> &problem);
154 
155  template<typename problem_t>
156  void setJacobiPreconditioner(Teuchos::RCP<problem_t> &problem);
157 
158  template<typename problem_t>
159  void setPolynomialPreconditioner(Teuchos::RCP<problem_t> &problem);
160 
161  void eigenvecsToCoords(Teuchos::RCP<mvector_t> &eigenVectors,
162  int computedNumEv,
163  Teuchos::RCP<mvector_t> &coordinates);
164 
165  void computeWeights(std::vector<const weight_t *> vecweights,
166  std::vector<int> strides);
167 
168  void MJwrapper(const Teuchos::RCP<const mvector_t> &coordinates,
169  std::vector<const weight_t *> weights,
170  std::vector<int> strides,
171  const Teuchos::RCP<PartitioningSolution<Adapter>> &solution);
172 
173  void setUserEigenvectors(const Teuchos::RCP<mvector_t> &userEvects);
177 
179  // Determine input graph's regularity = maxDegree/AvgDegree < 10.
180  // If Laplacian type is not specified, then use combinatorial for regular
181  // and generalized for irregular.
182  // MueLu settings will differ depending on the regularity, too.
184  {
185  // Get the row pointers in the host
186  auto rowOffsets = graph_->getLocalGraphDevice().row_map;
187  auto rowOffsets_h = Kokkos::create_mirror_view(rowOffsets);
188  Kokkos::deep_copy(rowOffsets_h, rowOffsets);
189 
190  // Get size information
191  const size_t numGlobalEntries = graph_->getGlobalNumEntries();
192  const size_t numLocalRows = graph_->getLocalNumRows();
193  const size_t numGlobalRows = graph_->getGlobalNumRows();
194 
195  // Compute local maximum degree
196  size_t localMax = 0;
197  for(size_t i = 0; i < numLocalRows; i++){
198  if(rowOffsets_h(i+1) - rowOffsets_h(i) - 1 > localMax)
199  localMax = rowOffsets_h(i+1) - rowOffsets_h(i) - 1;
200  }
201 
202  // Compute global maximum degree
203  size_t globalMax = 0;
204  Teuchos::reduceAll<int, size_t> (*comm_, Teuchos::REDUCE_MAX, 1, &localMax, &globalMax);
205 
206  double avg = static_cast<double>(numGlobalEntries-numGlobalRows)/numGlobalRows;
207  double maxOverAvg = static_cast<double>(globalMax)/avg;
208 
209  // Use generalized Laplacian on irregular graphs
210  irregular_ = false;
211  if(maxOverAvg > 10) {
212  irregular_ = true;
213  }
214 
215  // Let the user know about what we determined if verbose
216  if(verbosity_ > 0) {
217  if(comm_->getRank() == 0) {
218  std::cout << "Regularity of Graph ----------------" << std::endl;
219  std::cout << " Maximum degree: " << globalMax << std::endl;
220  std::cout << " Average degree: " << avg << std::endl;
221  std::cout << " Max/Avg: " << globalMax/avg << std::endl;
222  std::cout << " Regular graph?: " << !irregular_ << std::endl;
223  }
224  }
225  }
226 
228  // If preconditioner type is not specified:
229  // use muelu if it is enabled, and jacobi otherwise.
230  // If eigenvalue problem type is not specified:
231  // use combinatorial for regular and
232  // normalized for irregular with polynomial preconditioner,
233  // generalized for irregular with other preconditioners.
234  // If convergence tolerance is not specified:
235  // use 1e-3 for regular with jacobi and polynomial, and 1e-2 otherwise.
236  // If how to decide the initial vectors is not specified:
237  // use random for regular and constant for irregular
238  void setDefaults()
239  {
240 
241  // Set the default preconditioner to muelu if it is enabled, jacobi otherwise.
242  precType_ = "jacobi";
243 #ifdef HAVE_ZOLTAN2SPHYNX_MUELU
244  precType_ = "muelu";
245 #endif
246 
247  // Override the preconditioner type with the user's preference
248  const Teuchos::ParameterEntry *pe = sphynxParams_->getEntryPtr("sphynx_preconditioner_type");
249  if (pe) {
250  precType_ = pe->getValue<std::string>(&precType_);
251  if(precType_ != "muelu" && precType_ != "jacobi" && precType_ != "polynomial")
252  throw std::runtime_error("\nSphynx Error: " + precType_ + " is not recognized as a preconditioner.\n"
253  + " Possible values: muelu (if enabled), jacobi, and polynomial\n");
254  }
255 
256  solverType_ = sphynxParams_->get("sphynx_eigensolver","LOBPCG");
257  TEUCHOS_TEST_FOR_EXCEPTION(!(solverType_ == "LOBPCG" || solverType_ == "randomized" || solverType_ == "BlockDavidson" || solverType_ == "GeneralizedDavidson" || solverType_ == "BlockKrylovSchur" ),
258  std::invalid_argument, "Sphynx: sphynx_eigensolver must be set to LOBPCG, randomized, BlockDavidson, GeneralizedDavidson, or BlockKrylovSchur.");
259 
260  // Set the default problem type
261  problemType_ = COMBINATORIAL;
262  if(irregular_) {
263  if(precType_ == "polynomial")
264  problemType_ = NORMALIZED;
265  else
266  problemType_ = GENERALIZED;
267  }
268 
269  // Override the problem type with the user's preference
270  pe = sphynxParams_->getEntryPtr("sphynx_problem_type");
271  if (pe) {
272  std::string probType = "";
273  probType = pe->getValue<std::string>(&probType);
274 
275  if(probType == "combinatorial")
276  problemType_ = COMBINATORIAL;
277  else if(probType == "generalized")
278  problemType_ = GENERALIZED;
279  else if(probType == "normalized")
280  problemType_ = NORMALIZED;
281  else
282  throw std::runtime_error("\nSphynx Error: " + probType + " is not recognized as a problem type.\n"
283  + " Possible values: combinatorial, generalized, and normalized.\n");
284  }
285 
286 
287  // Set the default for tolerance
288  tolerance_ = 1.0e-2;
289  if(!irregular_ && (precType_ == "jacobi" || precType_ == "polynomial"))
290  tolerance_ = 1.0e-3;
291 
292 
293  // Override the tolerance with the user's preference
294  pe = sphynxParams_->getEntryPtr("sphynx_tolerance");
295  if (pe)
296  tolerance_ = pe->getValue<scalar_t>(&tolerance_);
297 
298 
299  // Set the default for initial vectors
300  randomInit_ = true;
301  if(irregular_)
302  randomInit_ = false;
303 
304  // Override the initialization method with the user's preference
305  pe = sphynxParams_->getEntryPtr("sphynx_initial_guess");
306  if (pe) {
307  std::string initialGuess = "";
308  initialGuess = pe->getValue<std::string>(&initialGuess);
309 
310  if(initialGuess == "random")
311  randomInit_ = true;
312  else if(initialGuess == "constants")
313  randomInit_ = false;
314  else
315  throw std::runtime_error("\nSphynx Error: " + initialGuess + " is not recognized as an option for initial guess.\n"
316  + " Possible values: random and constants.\n");
317  }
318 
319  }
320 
322  // Compute the Laplacian matrix depending on the eigenvalue problem type.
323  // There are 3 options for the type: combinatorial, generalized, and normalized.
324  // Combinatorial and generalized share the same Laplacian but generalized
325  // also needs a degree matrix.
327  {
328  if(solverType_ == "randomized")
329  laplacian_ = computeNormalizedLaplacian(true);
330  else if(problemType_ == NORMALIZED)
331  laplacian_ = computeNormalizedLaplacian();
332  else
333  laplacian_ = computeCombinatorialLaplacian();
334  }
335 
337  // Compute a diagonal matrix with the vertex degrees in the input graph
339  {
340 
341  // Get the row pointers in the host
342  auto rowOffsets = graph_->getLocalGraphHost().row_map;
343 
344  // Create the degree matrix with max row size set to 1
345  Teuchos::RCP<matrix_t> degMat(new matrix_t (graph_->getRowMap(),
346  graph_->getRowMap(),
347  1));
348 
349  scalar_t *val = new scalar_t[1];
350  lno_t *ind = new lno_t[1];
351  lno_t numRows = static_cast<lno_t>(graph_->getLocalNumRows());
352 
353  // Insert the diagonal entries as the degrees
354  for (lno_t i = 0; i < numRows; ++i) {
355  val[0] = rowOffsets(i+1) - rowOffsets(i) - 1;
356  ind[0] = i;
357  degMat->insertLocalValues(i, 1, val, ind);
358  }
359  delete [] val;
360  delete [] ind;
361 
362  degMat->fillComplete(graph_->getDomainMap(), graph_->getRangeMap());
363 
364  degMatrix_ = degMat;
365  }
366 
368  // Compute the combinatorial Laplacian: L = D - A.
369  // l_ij = degree of vertex i if i = j
370  // l_ij = -1 if i != j and a_ij != 0
371  // l_ij = 0 if i != j and a_ij = 0
372  Teuchos::RCP<matrix_t> computeCombinatorialLaplacian()
373  {
374  using range_policy = Kokkos::RangePolicy<
375  typename node_t::device_type::execution_space, Kokkos::IndexType<lno_t>>;
376  using values_view_t = Kokkos::View<scalar_t*, typename node_t::device_type>;
377  using offset_view_t = Kokkos::View<size_t*, typename node_t::device_type>;
378 
379  const size_t numEnt = graph_->getLocalNumEntries();
380  const size_t numRows = graph_->getLocalNumRows();
381 
382  // Create new values for the Laplacian, initialize to -1
383  values_view_t newVal (Kokkos::view_alloc("CombLapl::val", Kokkos::WithoutInitializing), numEnt);
384  Kokkos::deep_copy(newVal, -1);
385 
386  // Get the diagonal offsets
387  offset_view_t diagOffsets(Kokkos::view_alloc("Diag Offsets", Kokkos::WithoutInitializing), numRows);
388  graph_->getLocalDiagOffsets(diagOffsets);
389 
390  // Get the row pointers in the host
391  auto rowOffsets = graph_->getLocalGraphDevice().row_map;
392 
393  // Compute the diagonal entries as the vertex degrees
394  Kokkos::parallel_for("Combinatorial Laplacian", range_policy(0, numRows),
395  KOKKOS_LAMBDA(const lno_t i){
396  newVal(rowOffsets(i) + diagOffsets(i)) = rowOffsets(i+1) - rowOffsets(i) - 1;
397  }
398  );
399  Kokkos::fence ();
400 
401  // Create the Laplacian matrix using the input graph and with the new values
402  Teuchos::RCP<matrix_t> laplacian (new matrix_t(graph_, newVal));
403  laplacian->fillComplete (graph_->getDomainMap(), graph_->getRangeMap());
404 
405  // Create the Laplacian maatrix using the input graph and with the new values
406  return laplacian;
407  }
408 
410  // For AHat = false:
411  // Compute the normalized Laplacian: L_N = D^{-1/2} L D^{-1/2}, where L = D - A.
412  // l_ij = 1
413  // l_ij = -1/(sqrt(deg(v_i))sqrt(deg(v_j)) if i != j and a_ij != 0
414  // l_ij = 0 if i != j and a_ij = 0
415  //
416  // For AHat = true:
417  // AHat is turned to true if (and only if) using the randomized Eigensolver.
418  // For the randomized Eigensolver, we find eigenvalues of the matrix
419  // AHat = 2*I - L_N, and this is the matrix computed by this function.
420  Teuchos::RCP<matrix_t> computeNormalizedLaplacian(bool AHat = false)
421  {
422  using range_policy = Kokkos::RangePolicy<
423  typename node_t::device_type::execution_space, Kokkos::IndexType<lno_t>>;
424  using values_view_t = Kokkos::View<scalar_t*, typename node_t::device_type>;
425  using offset_view_t = Kokkos::View<size_t*, typename node_t::device_type>;
426  using vector_t = Tpetra::Vector<scalar_t, lno_t, gno_t, node_t>;
427  using dual_view_t = typename vector_t::dual_view_type;
428 #if KOKKOS_VERSION >= 40799
429  using KAT = KokkosKernels::ArithTraits<scalar_t>;
430 #else
431  using KAT = Kokkos::ArithTraits<scalar_t>;
432 #endif
433 
434  const size_t numEnt = graph_->getLocalNumEntries();
435  const size_t numRows = graph_->getLocalNumRows();
436 
437  // Create new values for the Laplacian, initialize to -1
438  values_view_t newVal (Kokkos::view_alloc("NormLapl::val", Kokkos::WithoutInitializing), numEnt);
439  if(AHat){
440  Kokkos::deep_copy(newVal, 1);
441  }
442  else{
443  Kokkos::deep_copy(newVal, -1);
444  }
445 
446  // D^{-1/2}
447  dual_view_t dv ("MV::DualView", numRows, 1);
448  auto deginvsqrt = dv.view_device();
449 
450  // Get the diagonal offsets
451  offset_view_t diagOffsets(Kokkos::view_alloc("Diag Offsets", Kokkos::WithoutInitializing), numRows);
452  graph_->getLocalDiagOffsets(diagOffsets);
453 
454  // Get the row pointers
455  auto rowOffsets = graph_->getLocalGraphDevice().row_map;
456 
457  // if(!AHat){
458  // Compute the diagonal entries as the vertex degrees
459  Kokkos::parallel_for("Combinatorial Laplacian", range_policy(0, numRows),
460  KOKKOS_LAMBDA(const lno_t i){
461  newVal(rowOffsets(i) + diagOffsets(i)) = rowOffsets(i+1) - rowOffsets(i) - 1;
462  deginvsqrt(i,0) = 1.0/KAT::sqrt(rowOffsets(i+1) - rowOffsets(i) - 1);
463  }
464  );
465  Kokkos::fence ();
466 
467  // Create the Laplacian graph using the same graph structure with the new values
468  Teuchos::RCP<matrix_t> laplacian (new matrix_t(graph_, newVal));
469  laplacian->fillComplete (graph_->getDomainMap(), graph_->getRangeMap());
470 
471  // Create the vector for D^{-1/2}
472  vector_t degInvSqrt(graph_->getRowMap(), dv);
473 
474  // Normalize the laplacian matrix as D^{-1/2} L D^{-1/2}
475  laplacian->leftScale(degInvSqrt);
476  laplacian->rightScale(degInvSqrt);
477 
478  return laplacian;
479  }
480 
484 
485  private:
486 
487  // User-provided members
488  const Teuchos::RCP<const Environment> env_;
489  Teuchos::RCP<Teuchos::ParameterList> params_;
490  Teuchos::RCP<Teuchos::ParameterList> sphynxParams_;
491  const Teuchos::RCP<const Teuchos::Comm<int> > comm_;
492  const Teuchos::RCP<const Adapter> adapter_;
493 
494  // Internal members
495  int numGlobalParts_;
496  Teuchos::RCP<const graph_t> graph_;
497  Teuchos::RCP<matrix_t> laplacian_;
498  Teuchos::RCP<const matrix_t> degMatrix_;
499  Teuchos::RCP<mvector_t> eigenVectors_;
500 
501  bool irregular_; // decided internally
502  std::string precType_; // obtained from user params or decided internally
503  std::string solverType_; // obtained from user params or decided internally
504  problemType problemType_; // obtained from user params or decided internally
505  double tolerance_; // obtained from user params or decided internally
506  bool randomInit_; // obtained from user params or decided internally
507  int verbosity_; // obtained from user params
508  bool skipPrep_; // obtained from user params
509  };
510 
514 
516  // Allows the user to manually set eigenvectors for the Sphynx partitioner
517  // to use rather than solving for them with Anasazi. Mainly intended
518  // for debugging purposes.
520  template <typename Adapter>
521  void Sphynx<Adapter>::setUserEigenvectors(const Teuchos::RCP<mvector_t> &userEvects)
522  {
523  eigenVectors_ = userEvects;
524  }
525 
527  // Compute a partition using the Laplacian matrix (and possibly the degree
528  // matrix as well). First call LOBPCG (or Randomized solver)
529  // to compute logK+1 eigenvectors, then
530  // transform the eigenvectors to coordinates, and finally call MJ to compute
531  // a partition on the coordinates.
532  template <typename Adapter>
533  void Sphynx<Adapter>::partition(const Teuchos::RCP<PartitioningSolution<Adapter>> &solution)
534  {
535  // Return a trivial solution if only one part is requested
536  if(numGlobalParts_ == 1) {
537 
538  size_t numRows =adapter_->getUserGraph()->getLocalNumRows();
539  Teuchos::ArrayRCP<part_t> parts(numRows,0);
540  solution->setParts(parts);
541 
542  return;
543 
544  }
545 
546  // The number of eigenvectors to be computed
547  int numEigenVectors = (int) log2(numGlobalParts_)+1;
548  int computedNumEv;
549 
550  if(eigenVectors_ == Teuchos::null){
551  // Compute the eigenvectors using LOBPCG
552  // or Randomized eigensolver
553  computedNumEv = Sphynx::AnasaziWrapper(numEigenVectors);
554 
555  if(computedNumEv <= 1 && (solverType_ == "LOBPCG" || solverType_ == "GeneralizedDavidson" || solverType_ == "BlockDavidson" || solverType_ == "BlockKrylovSchur")) {
556  throw
557  std::runtime_error("\nAnasazi Error: LOBPCGSolMgr::solve() returned unconverged.\n"
558  "Sphynx Error: LOBPCG could not compute any eigenvectors.\n"
559  " Increase either max iters or tolerance.\n");
560  }
561  }
562  else{
563  // Use eigenvectors provided by user.
564  computedNumEv = (int) eigenVectors_->getNumVectors();
565  if(computedNumEv <= numEigenVectors) {
566  throw
567  std::runtime_error("\nSphynx Error: Number of eigenvectors given by user\n"
568  " is less than number of Eigenvectors needed for partition." );
569  }
570  }
571 
572  // Transform the eigenvectors into coordinates
573  Teuchos::RCP<mvector_t> coordinates;
574 
575  Sphynx::eigenvecsToCoords(eigenVectors_, computedNumEv, coordinates);
576 
577  // Get the weights from the adapter
578  std::vector<const weight_t *> weights;
579  std::vector<int> wstrides;
580  Sphynx::computeWeights(weights, wstrides);
581 
582 
583  // Compute the partition using MJ on coordinates
584  Sphynx::MJwrapper(coordinates, weights, wstrides, solution);
585 
586  }
587 
589  // Call LOBPCG on the Laplacian matrix.
590  // Or use the randomized eigensolver.
591  template <typename Adapter>
592  int Sphynx<Adapter>::AnasaziWrapper(const int numEigenVectors)
593  {
594 
595  Teuchos::TimeMonitor t(*Teuchos::TimeMonitor::getNewTimer("Sphynx::Anasazi"));
596 
597  // Set defaults for the parameters
598  // and get user-set values.
599  std::string which = (solverType_ == "randomized" ? "LM" : "SR");
600  std::string ortho = "SVQB";
601  bool relConvTol = false;
602  int maxIterations = sphynxParams_->get("sphynx_max_iterations",1000);
603  int blockSize = sphynxParams_->get("sphynx_block_size",numEigenVectors);
604  int orthoFreq = sphynxParams_->get("sphynx_ortho_freq", 0);
605  int resFreq = sphynxParams_->get("sphynx_res_freq", 0);
606  bool isHermitian = true;
607  bool relLockTol = false;
608  bool lock = false;
609  bool useFullOrtho = sphynxParams_->get("sphynx_use_full_ortho",true);
610 
611  // Information to output in a verbose run
612  int numfailed = 0;
613  int iter = 0;
614 
615  // Set Anasazi verbosity level
616  int anasaziVerbosity = Anasazi::Errors + Anasazi::Warnings;
617  if (verbosity_ >= 1) // low
618  anasaziVerbosity += Anasazi::FinalSummary + Anasazi::TimingDetails;
619  if (verbosity_ >= 2) // medium
620  anasaziVerbosity += Anasazi::IterationDetails;
621  if (verbosity_ >= 3) // high
622  anasaziVerbosity += Anasazi::StatusTestDetails + Anasazi::OrthoDetails
623  + Anasazi::Debug;
624 
625  // Create the parameter list to pass into solver
626  Teuchos::ParameterList anasaziParams;
627  anasaziParams.set("Verbosity", anasaziVerbosity);
628  anasaziParams.set("Which", which);
629  anasaziParams.set("Convergence Tolerance", tolerance_);
630  anasaziParams.set("Maximum Iterations", maxIterations);
631  anasaziParams.set("Block Size", blockSize);
632  anasaziParams.set("Relative Convergence Tolerance", relConvTol);
633  anasaziParams.set("Orthogonalization", ortho);
634  anasaziParams.set("Use Locking", lock);
635  anasaziParams.set("Relative Locking Tolerance", relLockTol);
636  anasaziParams.set("Full Ortho", useFullOrtho);
637  anasaziParams.set("Orthogonalization Frequency", orthoFreq);
638  anasaziParams.set("Residual Frequency", resFreq);
639 
640  if(solverType_ == "GeneralizedDavidson" || solverType_ == "BlockKrylovSchur" || solverType_ == "BlockDavidson"){
641  anasaziParams.set( "Num Blocks", maxIterations+1 );
642  anasaziParams.set( "Maximum Restarts", 0 );
643  anasaziParams.set( "Maximum Subspace Dimension", (maxIterations+1)*blockSize );
644  }
645 
646  // Create and set initial vectors
647  auto map = laplacian_->getRangeMap();
648  Teuchos::RCP<mvector_t> ivec( new mvector_t(map, numEigenVectors));
649 
650  if (randomInit_) {
651  // 0-th vector constant 1, rest random
652  Anasazi::MultiVecTraits<scalar_t, mvector_t>::MvRandom(*ivec);
653  ivec->getVectorNonConst(0)->putScalar(1.);
654  }
655  else { // This implies we will use constant initial vectors.
656  // 0-th vector constant 1, other vectors constant per block
657  // Create numEigenVectors blocks, but only use numEigenVectors-1 of them.
658  // This assures orthogonality.
659  ivec->getVectorNonConst(0)->putScalar(1.);
660  for (int j = 1; j < numEigenVectors; j++)
661  ivec->getVectorNonConst(j)->putScalar(0.);
662 
663  gno_t blkSize = map->getGlobalNumElements() / numEigenVectors;
664  TEUCHOS_TEST_FOR_EXCEPTION(blkSize <= 0, std::runtime_error, "Blocksize too small for \"constants\" initial guess. Try \"random\".");
665 
666  for (size_t lid = 0; lid < ivec->getLocalLength(); lid++) {
667  gno_t gid = map->getGlobalElement(lid);
668  for (int j = 1; j < numEigenVectors; j++){
669  if (((j-1)*blkSize <= gid) && (j*blkSize > gid))
670  ivec->replaceLocalValue(lid,j,1.);
671  }
672  }
673  }
674 
675  // Create the eigenproblem to be solved
676  using problem_t = Anasazi::BasicEigenproblem<scalar_t, mvector_t, op_t>;
677  Teuchos::RCP<problem_t> problem (new problem_t(laplacian_, ivec));
678  problem->setHermitian(isHermitian);
679  problem->setNEV(numEigenVectors);
680 
681  if(solverType_ != "randomized"){
682  // Set preconditioner
683  Sphynx::setPreconditioner(problem);
684  if(problemType_ == Sphynx::GENERALIZED) problem->setM(degMatrix_);
685  }
686 
687  // Inform the eigenproblem that you are finished passing it information
688  bool boolret = problem->setProblem();
689  if (boolret != true) {
690  throw std::runtime_error("\nAnasazi::BasicEigenproblem::setProblem() returned with error.\n");
691  }
692  // Set Eigensolver
693  Teuchos::RCP<Anasazi::SolverManager<scalar_t, mvector_t, op_t>> solver;
694 
695  if(solverType_ == "LOBPCG"){
696  solver = Teuchos::rcp(new Anasazi::LOBPCGSolMgr<scalar_t, mvector_t, op_t>(problem, anasaziParams));
697  }
698  else if(solverType_ == "BlockDavidson"){
699  solver = Teuchos::rcp(new Anasazi::BlockDavidsonSolMgr<scalar_t, mvector_t, op_t>(problem, anasaziParams));
700  }
701  else if(solverType_ == "GeneralizedDavidson"){
702  solver = Teuchos::rcp(new Anasazi::GeneralizedDavidsonSolMgr<scalar_t, mvector_t, op_t>(problem, anasaziParams));
703  }
704  else if(solverType_ == "BlockKrylovSchur"){
705  solver = Teuchos::rcp(new Anasazi::BlockKrylovSchurSolMgr<scalar_t, mvector_t, op_t>(problem, anasaziParams));
706  }
707  else{
708  solver = Teuchos::rcp(new Anasazi::Experimental::RandomizedSolMgr<scalar_t, mvector_t, op_t>(problem, anasaziParams));
709  //numFailed = solver->getNumFailed();
710  }
711 
712  if (verbosity_ > 0 && comm_->getRank() == 0)
713  anasaziParams.print(std::cout);
714 
715  // Solve the problem
716  Anasazi::ReturnType returnCode = solver->solve();
717 
718  // Check convergence, niters, and solvetime
719  iter = solver->getNumIters();
720  //solvetime = (solver->getTimers()[0])->totalElapsedTime();
721 
722  // Retrieve the solution
723  using solution_t = Anasazi::Eigensolution<scalar_t, mvector_t>;
724  solution_t sol = problem->getSolution();
725  eigenVectors_ = sol.Evecs;
726  int numev = sol.numVecs;
727  std::vector<Anasazi::Value<double>> eigenValues_ = sol.Evals;
728 
729  // Summarize iteration counts and solve time
730  if (verbosity_ > 0 && comm_->getRank() == 0) {
731  std::cout << std::endl;
732  std::cout << "ANASAZI SUMMARY" << std::endl;
733  std::cout << "Failed to converge: " << numfailed << std::endl;
734  std::cout << "No of iterations : " << iter << std::endl;
735  std::cout << "Solve time: " << std::endl; // solvetime << std::endl;
736  std::cout << "No of comp. vecs. : " << numev << std::endl;
737  }
738 
739  std::cout << "Solver type: " << solverType_ << std::endl;
740  // Compute residuals (LOBPCG does this internally)
741  if(solverType_ == "randomized") {
742  std::vector<double> normR(numev);
743  mvector_t Aevec (map, numev);
744 
745  if (numev > 0) {
746  Teuchos::SerialDenseMatrix<int,double> T (numev, numev);
747  T.putScalar(0.0);
748  for (int i = 0; i < numev; ++i) T(i,i) = eigenValues_[i].realpart;
749  laplacian_->apply(*eigenVectors_, Aevec);
750  MVT::MvTimesMatAddMv(-1.0, *eigenVectors_, T, 1.0, Aevec);
751  MVT::MvNorm(Aevec, normR);
752  } // End residual computation
753 
754  if(comm_->getRank() == 0 && verbosity_ > 0) {
755  std::cout << std::endl << "Solver manager returned "
756  << (returnCode == Anasazi::Converged ? "converged." : "unconverged.")
757  << std::endl << std::endl
758  << std::setw(16) << "Eigenvalue"
759  << std::setw(18) << "Direct Residual"
760  << std::endl
761  << "------------------------------------------------------" << std::endl;
762 
763  for (int i = 0; i < numev; ++i) {
764  std::cout << std::setw(16) << 2.0-eigenValues_[i].realpart
765  << std::setw(18) << normR[i] / eigenValues_[i].realpart
766  << std::endl;
767  }
768  std::cout << "------------------------------------------------------" << std::endl;
769  }
770  }
771 
772  return numev;
773 
774  }
775 
777  template <typename Adapter>
778  template <typename problem_t>
779  void Sphynx<Adapter>::setPreconditioner(Teuchos::RCP<problem_t> &problem)
780  {
781  if(comm_->getRank() == 0) std::cout << "precType_ is: " << precType_ << std::endl;
782  // Set the preconditioner
783  if(precType_ == "muelu") {
785  }
786  else if(precType_ == "polynomial") {
788  }
789  else if(precType_ == "jacobi") {
791  }
792  // else: do we want a case where no preconditioning is applied?
793  }
794 
796  template <typename Adapter>
797  template <typename problem_t>
798  void Sphynx<Adapter>::setMueLuPreconditioner(Teuchos::RCP<problem_t> &problem)
799  {
800 #ifdef HAVE_ZOLTAN2SPHYNX_MUELU
801  Teuchos::ParameterList paramList;
802  if(verbosity_ == 0)
803  paramList.set("verbosity", "none");
804  else if(verbosity_ == 1)
805  paramList.set("verbosity", "low");
806  else if(verbosity_ == 2)
807  paramList.set("verbosity", "medium");
808  else if(verbosity_ == 3)
809  paramList.set("verbosity", "high");
810  else if(verbosity_ >= 4)
811  paramList.set("verbosity", "extreme");
812 
813  paramList.set("smoother: type", "CHEBYSHEV");
814  Teuchos::ParameterList smootherParamList;
815  smootherParamList.set("chebyshev: degree", 3);
816  smootherParamList.set("chebyshev: ratio eigenvalue", 7.0);
817  smootherParamList.set("chebyshev: eigenvalue max iterations", irregular_ ? 100 : 10);
818  paramList.set("smoother: params", smootherParamList);
819  paramList.set("use kokkos refactor", true);
820  paramList.set("transpose: use implicit", true);
821 
822  if(irregular_) {
823 
824  paramList.set("multigrid algorithm", "unsmoothed");
825 
826  paramList.set("coarse: type", "CHEBYSHEV");
827  Teuchos::ParameterList coarseParamList;
828  coarseParamList.set("chebyshev: degree", 3);
829  coarseParamList.set("chebyshev: ratio eigenvalue", 7.0);
830  paramList.set("coarse: params", coarseParamList);
831 
832  paramList.set("max levels", 5);
833  paramList.set("aggregation: drop tol", 0.40);
834 
835  }
836  using prec_t = MueLu::TpetraOperator<scalar_t, lno_t, gno_t, node_t>;
837  Teuchos::RCP<prec_t> prec = MueLu::CreateTpetraPreconditioner<
838  scalar_t, lno_t, gno_t, node_t>(laplacian_, paramList);
839 
840  problem->setPrec(prec);
841 
842 #else
843  throw std::runtime_error("\nSphynx Error: MueLu requested but not compiled into Trilinos.\n");
844 #endif
845  }
846 
848  template <typename Adapter>
849  template <typename problem_t>
850  void Sphynx<Adapter>::setPolynomialPreconditioner(Teuchos::RCP<problem_t> &problem)
851  {
852  int verbosity2 = Belos::Errors;
853  if(verbosity_ == 1)
854  verbosity2 += Belos::Warnings;
855  else if(verbosity_ == 2)
856  verbosity2 += Belos::Warnings + Belos::FinalSummary;
857  else if(verbosity_ == 3)
858  verbosity2 += Belos::Warnings + Belos::FinalSummary + Belos::TimingDetails;
859  else if(verbosity_ >= 4)
860  verbosity2 += Belos::Warnings + Belos::FinalSummary + Belos::TimingDetails
861  + Belos::StatusTestDetails;
862 
863  Teuchos::ParameterList paramList;
864  paramList.set("Polynomial Type", "Roots");
865  paramList.set("Orthogonalization","ICGS");
866  paramList.set("Maximum Degree", laplacian_->getGlobalNumRows() > 100 ? 25 : 5);
867  paramList.set("Polynomial Tolerance", 1.0e-6 );
868  paramList.set("Verbosity", verbosity2 );
869  paramList.set("Random RHS", false );
870  paramList.set("Outer Solver", "");
871  paramList.set("Timer Label", "Belos Polynomial Solve" );
872 
873  // Construct a linear problem for the polynomial solver manager
874  using lproblem_t = Belos::LinearProblem<scalar_t, mvector_t, op_t>;
875  Teuchos::RCP<lproblem_t> innerPolyProblem(new lproblem_t());
876  innerPolyProblem->setOperator(laplacian_);
877 
878  using btop_t = Belos::TpetraOperator<scalar_t, lno_t, gno_t, node_t>;
879  Teuchos::RCP<btop_t> polySolver(new btop_t(innerPolyProblem,
880  Teuchos::rcpFromRef(paramList),
881  "GmresPoly", true));
882  problem->setPrec(polySolver);
883  }
884 
886  template <typename Adapter>
887  template <typename problem_t>
888  void Sphynx<Adapter>::setJacobiPreconditioner(Teuchos::RCP<problem_t> &problem)
889  {
890 
891  Teuchos::RCP<Ifpack2::Preconditioner<scalar_t, lno_t, gno_t, node_t>> prec;
892  std::string precType = "RELAXATION";
893 
894  prec = Ifpack2::Factory::create<matrix_t> (precType, laplacian_);
895 
896  Teuchos::ParameterList precParams;
897  precParams.set("relaxation: type", "Jacobi");
898  precParams.set("relaxation: fix tiny diagonal entries", true);
899  precParams.set("relaxation: min diagonal value", 1.0e-8);
900 
901  prec->setParameters(precParams);
902  prec->initialize();
903  prec->compute();
904 
905  problem->setPrec(prec);
906 
907  }
908 
910  // Transform the computed eigenvectors into coordinates
911  template <typename Adapter>
912  void Sphynx<Adapter>::eigenvecsToCoords(Teuchos::RCP<mvector_t> &eigenVectors,
913  int computedNumEv,
914  Teuchos::RCP<mvector_t> &coordinates)
915  {
916  // Extract the meaningful eigenvectors by getting rid of the first one
917  Teuchos::Array<size_t> columns (computedNumEv-1);
918  for (int j = 0; j < computedNumEv-1; ++j) {
919  columns[j] = j+1;
920  }
921  coordinates = eigenVectors->subCopy (columns());
922  coordinates->setCopyOrView (Teuchos::View);
923  }
924 
925 
927  // If user provided some weights, use them by getting them from the adapter.
928  // If user didn't provide weights but told us to use degree as weight, do so.
929  // If user neither provided weights nor told us what to do, use degree as weight.
930  template <typename Adapter>
931  void Sphynx<Adapter>::computeWeights(std::vector<const weight_t *> vecweights,
932  std::vector<int> strides)
933  {
934 
935  int numWeights = adapter_->getNumWeightsPerVertex();
936  int numConstraints = numWeights > 0 ? numWeights : 1;
937 
938  size_t myNumVertices = adapter_->getLocalNumVertices();
939  weight_t ** weights = new weight_t*[numConstraints];
940  for(int j = 0; j < numConstraints; j++)
941  weights[j] = new weight_t[myNumVertices];
942 
943  // Will be needed if we use degree as weight
944  const offset_t *offset;
945  const gno_t *columnId;
946 
947  // If user hasn't set any weights, use vertex degrees as weights
948  if(numWeights == 0) {
949 
950  // Compute the weight of vertex i as the number of nonzeros in row i.
951  adapter_->getEdgesView(offset, columnId);
952  for (size_t i = 0; i < myNumVertices; i++)
953  weights[0][i] = offset[i+1] - offset[i] - 1;
954 
955  vecweights.push_back(weights[0]);
956  strides.push_back(1);
957  }
958  else {
959 
960  // Use the weights if there are any already set in the adapter
961  for(int j = 0; j < numConstraints; j++) {
962 
963  if(adapter_->useDegreeAsVertexWeight(j)) {
964  // Compute the weight of vertex i as the number of nonzeros in row i.
965  adapter_->getEdgesView(offset, columnId);
966  for (size_t i = 0; i < myNumVertices; i++)
967  weights[j][i] = offset[i+1] - offset[i];
968  }
969  else{
970  int stride;
971  const weight_t *wgt = NULL;
972  adapter_->getVertexWeightsView(wgt, stride, j);
973 
974  for (size_t i = 0; i < myNumVertices; i++)
975  weights[j][i] = wgt[i];
976  }
977 
978  vecweights.push_back(weights[j]);
979  strides.push_back(1);
980 
981  }
982  }
983 
984  }
985 
986 
988  // Compute a partition by calling MJ on given coordinates with given weights
989  template <typename Adapter>
990  void Sphynx<Adapter>::MJwrapper(const Teuchos::RCP<const mvector_t> &coordinates,
991  std::vector<const weight_t *> weights,
992  std::vector<int> strides,
993  const Teuchos::RCP<PartitioningSolution<Adapter>> &solution)
994  {
995 
996  Teuchos::TimeMonitor t(*Teuchos::TimeMonitor::getNewTimer("Sphynx::MJ"));
997 
998  using mvector_adapter_t = Zoltan2::XpetraMultiVectorAdapter<mvector_t>;
1002 
1003  size_t myNumVertices = coordinates->getLocalLength();
1004 
1005  // Create the base adapter for the multivector adapter
1006  Teuchos::RCP<mvector_adapter_t> adapcoordinates(new mvector_adapter_t(coordinates,
1007  weights,
1008  strides));
1009  Teuchos::RCP<const base_adapter_t> baseAdapter =
1010  Teuchos::rcp(dynamic_cast<const base_adapter_t *>(adapcoordinates.get()), false);
1011 
1012  // Create the coordinate model using the base multivector adapter
1013  Zoltan2::modelFlag_t flags;
1014 
1015  // Create the MJ object
1016  Teuchos::RCP<const Comm<int>> comm2 = comm_;
1017  Teuchos::RCP<mj_t> mj(new mj_t(env_, comm2, baseAdapter));
1018 
1019  // Partition with MJ
1020  Teuchos::RCP<solution_t> vectorsolution( new solution_t(env_, comm2, 1, mj));
1021  mj->partition(vectorsolution);
1022 
1023  // Transform the solution
1024  Teuchos::ArrayRCP<part_t> parts(myNumVertices);
1025  for(size_t i = 0; i < myNumVertices; i++) parts[i] = vectorsolution->getPartListView()[i];
1026  solution->setParts(parts);
1027  }
1028 
1029 } // namespace Zoltan2
1030 
1031 #endif
Zoltan2::BaseAdapter< userTypes_t > base_adapter_t
void partition(const Teuchos::RCP< PartitioningSolution< Adapter > > &solution)
Sphynx(const RCP< const Environment > &env, const RCP< Teuchos::ParameterList > &params, const RCP< Teuchos::ParameterList > &sphynxParams, const RCP< const Comm< int > > &comm, const RCP< const XpetraCrsGraphAdapter< graph_t > > &adapter)
Anasazi::MultiVecTraits< scalar_t, mvector_t > MVT
void computeWeights(std::vector< const weight_t * > vecweights, std::vector< int > strides)
void setMueLuPreconditioner(Teuchos::RCP< problem_t > &problem)
static ArrayRCP< ArrayRCP< zscalar_t > > weights
std::bitset< NUM_MODEL_FLAGS > modelFlag_t
void eigenvecsToCoords(Teuchos::RCP< mvector_t > &eigenVectors, int computedNumEv, Teuchos::RCP< mvector_t > &coordinates)
map_t::global_ordinal_type gno_t
Definition: mapRemotes.cpp:27
typename Adapter::node_t node_t
void setPolynomialPreconditioner(Teuchos::RCP< problem_t > &problem)
typename Zoltan2::InputTraits< ztcrsmatrix_t >::node_t node_t
Provides access for Zoltan2 to Xpetra::CrsGraph data.
Tpetra::MultiVector< scalar_t, lno_t, gno_t, node_t > mvector_t
void setJacobiPreconditioner(Teuchos::RCP< problem_t > &problem)
Teuchos::RCP< matrix_t > computeCombinatorialLaplacian()
void setUserEigenvectors(const Teuchos::RCP< mvector_t > &userEvects)
Defines the XpetraMultiVectorAdapter.
Defines XpetraCrsGraphAdapter class.
SparseMatrixAdapter_t::part_t part_t
Contains the Multi-jagged algorthm.
Adapter::scalar_t scalar_t
A PartitioningSolution is a solution to a partitioning problem.
static RCP< tMVector_t > coordinates
Tpetra::CrsGraph< lno_t, gno_t, node_t > graph_t
Adapter::part_t part_t
Tpetra::CrsMatrix< scalar_t, lno_t, gno_t, node_t > matrix_t
void MJwrapper(const Teuchos::RCP< const mvector_t > &coordinates, std::vector< const weight_t * > weights, std::vector< int > strides, const Teuchos::RCP< PartitioningSolution< Adapter >> &solution)
Algorithm defines the base class for all algorithms.
map_t::local_ordinal_type lno_t
Definition: mapRemotes.cpp:26
An adapter for Xpetra::MultiVector.
int AnasaziWrapper(const int numEigenVectors)
Tpetra::Operator< scalar_t, lno_t, gno_t, node_t > op_t
Defines the CoordinateModel classes.
typename Adapter::offset_t offset_t
void setPreconditioner(Teuchos::RCP< problem_t > &problem)
typename Adapter::scalar_t weight_t
Teuchos::RCP< matrix_t > computeNormalizedLaplacian(bool AHat=false)
Multi Jagged coordinate partitioning algorithm.