Ifpack2 Templated Preconditioning Package  Version 1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Ifpack2_OverlappingPartitioner_def.hpp
1 // @HEADER
2 // *****************************************************************************
3 // Ifpack2: Templated Object-Oriented Algebraic Preconditioner Package
4 //
5 // Copyright 2009 NTESS and the Ifpack2 contributors.
6 // SPDX-License-Identifier: BSD-3-Clause
7 // *****************************************************************************
8 // @HEADER
9 
10 #ifndef IFPACK2_OVERLAPPINGPARTITIONER_DEF_HPP
11 #define IFPACK2_OVERLAPPINGPARTITIONER_DEF_HPP
12 #include <vector>
13 #include <string>
14 #include <algorithm>
15 #include "Ifpack2_ConfigDefs.hpp"
16 #include "Ifpack2_OverlappingPartitioner_decl.hpp"
17 #include "Teuchos_Array.hpp"
18 #include "Teuchos_ArrayRCP.hpp"
19 
20 namespace Ifpack2 {
21 
22 template <class GraphType>
25  : NumLocalParts_(1)
26  , Graph_(graph)
27  , OverlappingLevel_(0)
28  , IsComputed_(false)
29  , verbose_(false)
30  , maintainSparsity_(false) {}
31 
32 template <class GraphType>
34 
35 template <class GraphType>
37  return NumLocalParts_;
38 }
39 
40 template <class GraphType>
42  return OverlappingLevel_;
43 }
44 
45 template <class GraphType>
46 typename GraphType::local_ordinal_type
48 operator()(const local_ordinal_type MyRow) const {
50  MyRow < 0 || Teuchos::as<size_t>(MyRow) > Graph_->getLocalNumRows(),
51  std::runtime_error,
52  "Ifpack2::OverlappingPartitioner::operator(): "
53  "Invalid local row index "
54  << MyRow << ".");
55 
56  return Partition_[MyRow];
57 }
58 
59 //==============================================================================
60 template <class GraphType>
61 typename GraphType::local_ordinal_type
63 operator()(const local_ordinal_type i, const local_ordinal_type j) const {
65  i < 0 || i > Teuchos::as<local_ordinal_type>(NumLocalParts_),
66  std::runtime_error,
67  "Ifpack2::OverlappingPartitioner::operator(): "
68  "Invalid local row index i="
69  << i << ".");
71  j < 0 || j > Teuchos::as<local_ordinal_type>(Parts_[i].size()),
72  std::runtime_error,
73  "Ifpack2::OverlappingPartitioner::operator(): "
74  "Invalid node index j="
75  << j << ".");
76  return Parts_[i][j];
77 }
78 
79 //==============================================================================
80 template <class GraphType>
81 size_t
83  numRowsInPart(const local_ordinal_type Part) const {
85  Part < 0 || Part > Teuchos::as<local_ordinal_type>(NumLocalParts_),
86  std::runtime_error,
87  "Ifpack2::OverlappingPartitioner::numRowsInPart: "
88  "Invalid partition index Part="
89  << Part << ".");
90  return Parts_[Part].size();
91 }
92 
93 //==============================================================================
94 template <class GraphType>
96  rowsInPart(const local_ordinal_type Part,
98  // Let numRowsInPart do the sanity checking...
99  const size_t numRows = numRowsInPart(Part);
100  for (size_t i = 0; i < numRows; ++i) {
101  List[i] = Parts_[Part][i];
102  }
103 }
104 
105 //==============================================================================
106 template <class GraphType>
109  return Partition_.view(0, Graph_->getLocalNumRows());
110 }
111 
112 //==============================================================================
113 template <class GraphType>
116  NumLocalParts_ = List.get("partitioner: local parts", NumLocalParts_);
117  OverlappingLevel_ = List.get("partitioner: overlap", OverlappingLevel_);
118  verbose_ = List.get("partitioner: print level", verbose_);
119  maintainSparsity_ = List.get("partitioner: maintain sparsity", false);
122 
123  // when using overlapping schwarz wth combineMode ADD, we need import and
124  // overlap row map to adjust weights for ith dof. Specifically, we sum
125  // all blocks (including off processor ones) that contain i.
126  import_type theImport = Graph_->getImporter();
127  if (theImport != Teuchos::null) List.set<import_type>("theImport", theImport);
128  List.set<map_type>("OverlapRowMap", Graph_->getRowMap());
129 
130  if (NumLocalParts_ < 0) {
131  NumLocalParts_ = Graph_->getLocalNumRows() / (-NumLocalParts_);
132  }
133  if (NumLocalParts_ == 0) {
134  NumLocalParts_ = 1;
135  }
136 
137  // Sanity checking
139  NumLocalParts_ < 0 ||
140  Teuchos::as<size_t>(NumLocalParts_) > Graph_->getLocalNumRows(),
141  std::runtime_error,
142  "Ifpack2::OverlappingPartitioner::setParameters: "
143  "Invalid NumLocalParts_ = "
144  << NumLocalParts_ << ".");
146  OverlappingLevel_ < 0, std::runtime_error,
147  "Ifpack2::OverlappingPartitioner::setParameters: "
148  "Invalid OverlappingLevel_ = "
149  << OverlappingLevel_ << ".");
150 
151  setPartitionParameters(List);
152 }
153 
154 //==============================================================================
155 template <class GraphType>
157  using std::cout;
158  using std::endl;
159 
161  NumLocalParts_ < 1 || OverlappingLevel_ < 0,
162  std::runtime_error,
163  "Ifpack2::OverlappingPartitioner::compute: "
164  "Invalid NumLocalParts_ or OverlappingLevel_.");
165 
166  // std::string's constructor has some overhead, so it's better to
167  // use const char[] for local constant strings.
168  const char printMsg[] = "OverlappingPartitioner: ";
169 
170  if (verbose_ && (Graph_->getComm()->getRank() == 0)) {
171  cout << printMsg << "Number of local parts = "
172  << NumLocalParts_ << endl;
173  cout << printMsg << "Approx. Number of global parts = "
174  << NumLocalParts_ * Graph_->getComm()->getSize() << endl;
175  cout << printMsg << "Amount of overlap = "
176  << OverlappingLevel_ << endl;
177  }
178 
179  // 1.- allocate memory
180  Partition_.resize(Graph_->getLocalNumRows());
181  // Parts_ is allocated in computeOverlappingPartitions_, where it is used
182 
183  // 2.- sanity checks on input graph
185  !Graph_->isFillComplete(), std::runtime_error,
186  "Ifpack2::OverlappingPartitioner::compute: "
187  "The input graph must be fill complete.");
188 
190  Graph_->getGlobalNumRows() != Graph_->getGlobalNumCols(),
191  std::runtime_error,
192  "Ifpack2::OverlappingPartitioner::compute: "
193  "The input graph must be (globally) square.");
194 
195  // 3.- perform non-overlapping partition
196  computePartitions();
197 
198  // 4.- compute the partitions with overlapping
199  computeOverlappingPartitions();
200 
201  // 5.- mark as computed
202  IsComputed_ = true;
203 }
204 
205 //==============================================================================
206 template <class GraphType>
208  // If user has explicitly specified parts, then Partition_ size has been set to 0.
209  // In this case, there is no need to compute Parts_.
210  if (Partition_.size() == 0)
211  return;
212 
213  const local_ordinal_type invalid =
215 
216  // Old FIXME from Ifpack: the first part of this function should be elsewhere
217 
218  // start defining the subgraphs for no overlap
219 
220  std::vector<size_t> sizes;
221  sizes.resize(NumLocalParts_);
222 
223  // 1.- compute how many rows are in each subgraph
224  for (int i = 0; i < NumLocalParts_; ++i) {
225  sizes[i] = 0;
226  }
227 
228  for (size_t i = 0; i < Graph_->getLocalNumRows(); ++i) {
230  Partition_[i] >= NumLocalParts_, std::runtime_error,
231  "Ifpack2::OverlappingPartitioner::computeOverlappingPartitions: "
232  "Partition_[i] > NumLocalParts_.");
233  // invalid indicates that this unknown is not in a nonoverlapping
234  // partition
235  if (Partition_[i] != invalid) {
236  sizes[Partition_[i]]++;
237  }
238  }
239 
240  // 2.- allocate space for each subgraph
241  Parts_.resize(NumLocalParts_);
242  for (int i = 0; i < NumLocalParts_; ++i) {
243  Parts_[i].resize(sizes[i]);
244  }
245 
246  // 3.- cycle over all rows and populate the vectors
247  for (int i = 0; i < NumLocalParts_; ++i) {
248  sizes[i] = 0;
249  }
250 
251  for (size_t i = 0; i < Graph_->getLocalNumRows(); ++i) {
252  const local_ordinal_type part = Partition_[i];
253  if (part != invalid) {
254  const size_t count = sizes[part];
255  Parts_[part][count] = i;
256  sizes[part]++;
257  }
258  }
259 
260  // If there is no overlap, we're done, so return
261  if (OverlappingLevel_ == 0) {
262  return;
263  }
264 
265  // wider overlap requires further computations
266  for (int level = 1; level <= OverlappingLevel_; ++level) {
267  std::vector<std::vector<size_t> > tmp;
268  tmp.resize(NumLocalParts_);
269 
270  // cycle over all rows in the local graph (that is the overlapping
271  // graph). For each row, all columns will belong to the subgraph
272  // of row `i'.
273 
274  int MaxNumEntries_tmp = Graph_->getLocalMaxNumRowEntries();
275  nonconst_local_inds_host_view_type Indices("Indices", MaxNumEntries_tmp);
276  nonconst_local_inds_host_view_type newIndices("newIndices", MaxNumEntries_tmp);
277 
278  if (!maintainSparsity_) {
279  local_ordinal_type numLocalRows = Graph_->getLocalNumRows();
280  for (int part = 0; part < NumLocalParts_; ++part) {
281  for (size_t i = 0; i < Teuchos::as<size_t>(Parts_[part].size()); ++i) {
282  const local_ordinal_type LRID = Parts_[part][i];
283 
284  size_t numIndices;
285  Graph_->getLocalRowCopy(LRID, Indices, numIndices);
286 
287  for (size_t j = 0; j < numIndices; ++j) {
288  // use *local* indices only
289  const local_ordinal_type col = Indices[j];
290  if (col >= numLocalRows) {
291  continue;
292  }
293 
294  // has this column already been inserted?
295  std::vector<size_t>::iterator where =
296  std::find(tmp[part].begin(), tmp[part].end(), Teuchos::as<size_t>(col));
297 
298  if (where == tmp[part].end()) {
299  tmp[part].push_back(col);
300  }
301  }
302 
303  // 10-Jan-2017 JHU : A possible optimization is to avoid the std::find's in the loop above,
304  // but instead sort and make unique afterwards. One would have to be careful to only sort/
305  // make unique the insertions associated with the current row LRID, as for each row, LRID
306  // may occur after all other col indices for row LRID (see comment about zero pivot below).
307 
308  // has this column already been inserted?
309  std::vector<size_t>::iterator where =
310  std::find(tmp[part].begin(), tmp[part].end(), Teuchos::as<size_t>(LRID));
311 
312  // This happens here b/c Vanka on Stokes with Stabilized elements will have
313  // a zero pivot entry if this gets pushed back first. So... Last.
314  if (where == tmp[part].end()) {
315  tmp[part].push_back(LRID);
316  }
317  }
318  } // for (int part = 0; ...
319 
320  } else {
321  // maintainSparsity_ == true
322 
323  for (int part = 0; part < NumLocalParts_; ++part) {
324  for (size_t i = 0; i < Teuchos::as<size_t>(Parts_[part].size()); ++i) {
325  const local_ordinal_type LRID = Parts_[part][i];
326 
327  size_t numIndices;
328  Graph_->getLocalRowCopy(LRID, Indices, numIndices);
329  // JJH: the entries in Indices are already sorted. However, the Tpetra documentation states
330  // that we can't count on this always being true, hence we sort. Also note that there are
331  // unused entries at the end of Indices (it's sized to hold any row). This means we can't
332  // just use Indices.end() in sorting and in std::includes
333  Tpetra::sort(Indices, numIndices);
334 
335  for (size_t j = 0; j < numIndices; ++j) {
336  // use *local* indices only
337  const local_ordinal_type col = Indices[j];
338  if (Teuchos::as<size_t>(col) >= Graph_->getLocalNumRows()) {
339  continue;
340  }
341 
342  // has this column already been inserted?
343  std::vector<size_t>::iterator where =
344  std::find(tmp[part].begin(), tmp[part].end(), Teuchos::as<size_t>(col));
345 
346  if (where == tmp[part].end()) {
347  // Check if row associated with "col" increases connectivity already defined by row LRID's stencil.
348  // If it does and maintainSparsity_ is true, do not add "col" to the current partition (block).
349  size_t numNewIndices;
350  Graph_->getLocalRowCopy(col, newIndices, numNewIndices);
351  Tpetra::sort(newIndices, numNewIndices);
352  auto Indices_rcp = Kokkos::Compat::persistingView<nonconst_local_inds_host_view_type>(Indices, 0, numIndices);
353  auto newIndices_rcp = Kokkos::Compat::persistingView<nonconst_local_inds_host_view_type>(newIndices, 0, numNewIndices);
354  bool isSubset = std::includes(Indices_rcp.begin(), Indices_rcp.begin() + numIndices,
355  newIndices_rcp.begin(), newIndices_rcp.begin() + numNewIndices);
356  if (isSubset) {
357  tmp[part].push_back(col);
358  }
359  }
360  }
361 
362  // has this column already been inserted?
363  std::vector<size_t>::iterator where =
364  std::find(tmp[part].begin(), tmp[part].end(), Teuchos::as<size_t>(LRID));
365 
366  // This happens here b/c Vanka on Stokes with Stabilized elements will have
367  // a zero pivot entry if this gets pushed back first. So... Last.
368  if (where == tmp[part].end()) {
369  tmp[part].push_back(LRID);
370  }
371  }
372  } // for (int part = 0;
373 
374  } // if (maintainSparsity_) ... else
375 
376  // now I convert the STL vectors into Teuchos Array RCP's
377  //
378  // FIXME (mfh 12 July 2013) You could have started with ArrayRCP
379  // in the first place (which implements push_back and iterators)
380  // and avoided the copy.
381  for (int i = 0; i < NumLocalParts_; ++i) {
382  Parts_[i].resize(tmp[i].size());
383  for (size_t j = 0; j < tmp[i].size(); ++j) {
384  Parts_[i][j] = tmp[i][j];
385  }
386  }
387  }
388 }
389 
390 //==============================================================================
391 template <class GraphType>
393  return IsComputed_;
394 }
395 
396 //==============================================================================
397 template <class GraphType>
398 std::ostream&
400  Teuchos::FancyOStream fos(Teuchos::rcpFromRef(os));
401  fos.setOutputToRootOnly(0);
402  describe(fos);
403  return os;
404 }
405 
406 //==============================================================================
407 template <class GraphType>
409  std::ostringstream oss;
411  if (isComputed()) {
412  oss << "{status = computed";
413  } else {
414  oss << "{status = is not computed";
415  }
416  oss << "}";
417  return oss.str();
418 }
419 
420 //==============================================================================
421 template <class GraphType>
423  using std::endl;
424  if (verbLevel == Teuchos::VERB_NONE) {
425  return;
426  }
427 
428  os << "================================================================================" << endl;
429  os << "Ifpack2::OverlappingPartitioner" << endl;
430  os << "Number of local rows = " << Graph_->getLocalNumRows() << endl;
431  os << "Number of global rows = " << Graph_->getGlobalNumRows() << endl;
432  os << "Number of local parts = " << NumLocalParts_ << endl;
433  os << "Overlapping level = " << OverlappingLevel_ << endl;
434  os << "Is computed = " << IsComputed_ << endl;
435  os << "================================================================================" << endl;
436 }
437 
438 } // namespace Ifpack2
439 
440 #define IFPACK2_OVERLAPPINGPARTITIONER_INSTANT(LO, GO, N) \
441  template class Ifpack2::OverlappingPartitioner<Tpetra::CrsGraph<LO, GO, N> >; \
442  template class Ifpack2::OverlappingPartitioner<Tpetra::RowGraph<LO, GO, N> >;
443 
444 #endif // IFPACK2_OVERLAPPINGPARTITIONER_DEF_HPP
void rowsInPart(const local_ordinal_type Part, Teuchos::ArrayRCP< local_ordinal_type > &List) const
Fill List with the local indices of the rows in the (overlapping) partition Part. ...
Definition: Ifpack2_OverlappingPartitioner_def.hpp:96
virtual Teuchos::ArrayView< const local_ordinal_type > nonOverlappingPartition() const
A view of the local indices of the nonoverlapping partitions of each local row.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:108
T & get(const std::string &name, T def_value)
OverlappingPartitioner(const Teuchos::RCP< const row_graph_type > &graph)
Constructor.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:24
#define TEUCHOS_TEST_FOR_EXCEPTION(throw_exception_test, Exception, msg)
ParameterList & set(std::string const &name, T &&value, std::string const &docString="", RCP< const ParameterEntryValidator > const &validator=null)
int overlappingLevel() const
The number of levels of overlap.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:41
int numLocalParts() const
Number of computed local partitions.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:36
virtual void computeOverlappingPartitions()
Computes the partitions. Returns 0 if successful.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:207
void describe(Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const
Print the object with some verbosity level to an FancyOStream object.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:422
virtual ~OverlappingPartitioner()
Destructor.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:33
virtual bool isComputed() const
Returns true if partitions have been computed successfully.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:392
virtual std::string description() const
std::string description() const
Return a simple one-line description of this object.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:408
basic_FancyOStream & setOutputToRootOnly(const int rootRank)
virtual void compute()
Computes the partitions. Returns 0 if successful.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:156
virtual std::ostream & print(std::ostream &os) const
Prints basic information on iostream. This function is used by operator&lt;&lt;.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:399
local_ordinal_type operator()(const local_ordinal_type MyRow) const
Local index of the nonoverlapping partition of the given row.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:48
virtual void setParameters(Teuchos::ParameterList &List)
Set all the parameters for the partitioner.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:115
size_t numRowsInPart(const local_ordinal_type Part) const
the number of rows contained in the given partition.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:83