Ifpack2 Templated Preconditioning Package  Version 1.0
Ifpack2_OverlappingPartitioner_def.hpp
1 /*@HEADER
2 // ***********************************************************************
3 //
4 // Ifpack2: Tempated Object-Oriented Algebraic Preconditioner Package
5 // Copyright (2009) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
38 //
39 // ***********************************************************************
40 //@HEADER
41 */
42 
43 #ifndef IFPACK2_OVERLAPPINGPARTITIONER_DEF_HPP
44 #define IFPACK2_OVERLAPPINGPARTITIONER_DEF_HPP
45 #include "Ifpack2_ConfigDefs.hpp"
46 #include "Ifpack2_OverlappingPartitioner_decl.hpp"
47 #include "Teuchos_Array.hpp"
48 #include "Teuchos_ArrayRCP.hpp"
49 #include <vector>
50 #include <string>
51 
52 namespace Ifpack2 {
53 
54 template<class GraphType>
56 OverlappingPartitioner (const Teuchos::RCP<const row_graph_type>& graph) :
57  NumLocalParts_ (1),
58  Graph_ (graph),
59  OverlappingLevel_ (0),
60  IsComputed_ (false),
61  verbose_ (false)
62 {}
63 
64 
65 template<class GraphType>
67 
68 
69 template<class GraphType>
70 int
72 {
73  return NumLocalParts_;
74 }
75 
76 
77 template<class GraphType>
79 {
80  return OverlappingLevel_;
81 }
82 
83 
84 template<class GraphType>
85 typename GraphType::local_ordinal_type
87 operator () (const local_ordinal_type MyRow) const
88 {
89  TEUCHOS_TEST_FOR_EXCEPTION(
90  MyRow < 0 || Teuchos::as<size_t> (MyRow) > Graph_->getNodeNumRows (),
91  std::runtime_error,
92  "Ifpack2::OverlappingPartitioner::operator(): "
93  "Invalid local row index " << MyRow << ".");
94 
95  return Partition_[MyRow];
96 }
97 
98 
99 //==============================================================================
100 template<class GraphType>
101 typename GraphType::local_ordinal_type
103 operator() (const local_ordinal_type i, const local_ordinal_type j) const
104 {
105  TEUCHOS_TEST_FOR_EXCEPTION(
106  i < 0 || i > Teuchos::as<local_ordinal_type> (NumLocalParts_),
107  std::runtime_error,
108  "Ifpack2::OverlappingPartitioner::operator(): "
109  "Invalid local row index i=" << i << ".");
110  TEUCHOS_TEST_FOR_EXCEPTION(
111  j < 0 || j > Teuchos::as<local_ordinal_type> (Parts_[i].size ()),
112  std::runtime_error,
113  "Ifpack2::OverlappingPartitioner::operator(): "
114  "Invalid node index j=" << j << ".");
115  return Parts_[i][j];
116 }
117 
118 //==============================================================================
119 template<class GraphType>
120 size_t
122 numRowsInPart (const local_ordinal_type Part) const
123 {
124  TEUCHOS_TEST_FOR_EXCEPTION(
125  Part < 0 || Part > Teuchos::as<local_ordinal_type> (NumLocalParts_),
126  std::runtime_error,
127  "Ifpack2::OverlappingPartitioner::numRowsInPart: "
128  "Invalid partition index Part=" << Part << ".");
129  return Parts_[Part].size ();
130 }
131 
132 //==============================================================================
133 template<class GraphType>
134 void
136 rowsInPart (const local_ordinal_type Part,
137  Teuchos::ArrayRCP<local_ordinal_type>& List) const
138 {
139  // Let numRowsInPart do the sanity checking...
140  const size_t numRows = numRowsInPart (Part);
141  for (size_t i = 0; i < numRows; ++i) {
142  List[i] = Parts_[Part][i];
143  }
144 }
145 
146 //==============================================================================
147 template<class GraphType>
148 Teuchos::ArrayView<const typename GraphType::local_ordinal_type>
150 {
151  return Partition_.view (0, Graph_->getNodeNumRows ());
152 }
153 
154 //==============================================================================
155 template<class GraphType>
156 void
158 setParameters (Teuchos::ParameterList& List)
159 {
160  NumLocalParts_ = List.get("partitioner: local parts", NumLocalParts_);
161  OverlappingLevel_ = List.get("partitioner: overlap", OverlappingLevel_);
162  verbose_ = List.get("partitioner: print level", verbose_);
163 
164  if (NumLocalParts_ < 0) {
165  NumLocalParts_ = Graph_->getNodeNumRows() / (-NumLocalParts_);
166  }
167  if (NumLocalParts_ == 0) {
168  NumLocalParts_ = 1;
169  }
170 
171  // Sanity checking
172  TEUCHOS_TEST_FOR_EXCEPTION(
173  NumLocalParts_ < 0 ||
174  Teuchos::as<size_t> (NumLocalParts_) > Graph_->getNodeNumRows(),
175  std::runtime_error,
176  "Ifpack2::OverlappingPartitioner::setParameters: "
177  "Invalid NumLocalParts_ = " << NumLocalParts_ << ".");
178  TEUCHOS_TEST_FOR_EXCEPTION(
179  OverlappingLevel_ < 0, std::runtime_error,
180  "Ifpack2::OverlappingPartitioner::setParameters: "
181  "Invalid OverlappingLevel_ = " << OverlappingLevel_ << ".");
182 
184 }
185 
186 //==============================================================================
187 template<class GraphType>
189 {
190  using std::cout;
191  using std::endl;
192 
193  TEUCHOS_TEST_FOR_EXCEPTION(
195  std::runtime_error,
196  "Ifpack2::OverlappingPartitioner::compute: "
197  "Invalid NumLocalParts_ or OverlappingLevel_.");
198 
199  // std::string's constructor has some overhead, so it's better to
200  // use const char[] for local constant strings.
201  const char printMsg[] = "OverlappingPartitioner: ";
202 
203  if (verbose_ && (Graph_->getComm()->getRank() == 0)) {
204  cout << printMsg << "Number of local parts = "
205  << NumLocalParts_ << endl;
206  cout << printMsg << "Approx. Number of global parts = "
207  << NumLocalParts_ * Graph_->getComm ()->getSize () << endl;
208  cout << printMsg << "Amount of overlap = "
209  << OverlappingLevel_ << endl;
210  }
211 
212  // 1.- allocate memory
213  Partition_.resize (Graph_->getNodeNumRows ());
214  Parts_.resize (NumLocalParts_);
215 
216  // 2.- sanity checks on input graph
217  TEUCHOS_TEST_FOR_EXCEPTION(
218  ! Graph_->isFillComplete (), std::runtime_error,
219  "Ifpack2::OverlappingPartitioner::compute: "
220  "The input graph must be fill complete.");
221 
222  TEUCHOS_TEST_FOR_EXCEPTION(
223  Graph_->getGlobalNumRows () != Graph_->getGlobalNumCols (),
224  std::runtime_error,
225  "Ifpack2::OverlappingPartitioner::compute: "
226  "The input graph must be (globally) square.");
227 
228  // 3.- perform non-overlapping partition
230 
231  // 4.- compute the partitions with overlapping
233 
234  // 5.- mark as computed
235  IsComputed_ = true;
236 }
237 
238 //==============================================================================
239 template<class GraphType>
241 {
242  const local_ordinal_type invalid =
243  Teuchos::OrdinalTraits<local_ordinal_type>::invalid();
244 
245  // Old FIXME from Ifpack: the first part of this function should be elsewhere
246 
247  // start defining the subgraphs for no overlap
248 
249  std::vector<size_t> sizes;
250  sizes.resize (NumLocalParts_);
251 
252  // 1.- compute how many rows are in each subgraph
253  for (int i = 0; i < NumLocalParts_; ++i) {
254  sizes[i] = 0;
255  }
256 
257  for (size_t i = 0; i < Graph_->getNodeNumRows (); ++i) {
258  TEUCHOS_TEST_FOR_EXCEPTION(
259  Partition_[i] >= NumLocalParts_, std::runtime_error,
260  "Ifpack2::OverlappingPartitioner::computeOverlappingPartitions: "
261  "Partition_[i] > NumLocalParts_.");
262  // invalid indicates that this unknown is not in a nonoverlapping
263  // partition
264  if (Partition_[i] != invalid) {
265  sizes[Partition_[i]]++;
266  }
267  }
268 
269  // 2.- allocate space for each subgraph
270  for (int i = 0; i < NumLocalParts_; ++i) {
271  Parts_[i].resize (sizes[i]);
272  }
273 
274  // 3.- cycle over all rows and populate the vectors
275  for (int i = 0; i < NumLocalParts_; ++i) {
276  sizes[i] = 0;
277  }
278 
279  for (size_t i = 0; i < Graph_->getNodeNumRows (); ++i) {
280  const local_ordinal_type part = Partition_[i];
281  if (part != invalid) {
282  const size_t count = sizes[part];
283  Parts_[part][count] = i;
284  sizes[part]++;
285  }
286  }
287 
288  // If there is no overlap, we're done, so return
289  if (OverlappingLevel_ == 0) {
290  return;
291  }
292 
293  // wider overlap requires further computations
294  for (int level = 1; level <= OverlappingLevel_; ++level) {
295  std::vector<std::vector<size_t> > tmp;
296  tmp.resize (NumLocalParts_);
297 
298  // cycle over all rows in the local graph (that is the overlapping
299  // graph). For each row, all columns will belong to the subgraph
300  // of row `i'.
301 
302  int MaxNumEntries_tmp = Graph_->getNodeMaxNumRowEntries();
303  Teuchos::Array<local_ordinal_type> Indices;
304  Indices.resize (MaxNumEntries_tmp);
305 
306  for (int part = 0; part < NumLocalParts_ ; ++part) {
307  for (size_t i = 0; i < Teuchos::as<size_t> (Parts_[part].size ()); ++i) {
308  const local_ordinal_type LRID = Parts_[part][i];
309 
310  size_t NumIndices;
311  Graph_->getLocalRowCopy (LRID, Indices (), NumIndices);
312 
313  for (size_t j = 0; j < NumIndices; ++j) {
314  // use *local* indices only
315  const local_ordinal_type col = Indices[j];
316  if (Teuchos::as<size_t> (col) >= Graph_->getNodeNumRows ()) {
317  continue;
318  }
319 
320  // has this column already been inserted?
321  std::vector<size_t>::iterator where =
322  std::find (tmp[part].begin (), tmp[part].end (), Teuchos::as<size_t> (col));
323 
324  if (where == tmp[part].end()) {
325  tmp[part].push_back (col);
326  }
327  }
328 
329  // has this column already been inserted?
330  std::vector<size_t>::iterator where =
331  std::find (tmp[part].begin (), tmp[part].end (), Teuchos::as<size_t> (LRID));
332 
333  // This happens here b/c Vanka on Stokes with Stabilized elements will have
334  // a zero pivot entry if this gets pushed back first. So... Last.
335  if (where == tmp[part].end ()) {
336  tmp[part].push_back (LRID);
337  }
338  }
339  }
340 
341  // now I convert the STL vectors into Teuchos Array RCP's
342  //
343  // FIXME (mfh 12 July 2013) You could have started with ArrayRCP
344  // in the first place (which implements push_back and iterators)
345  // and avoided the copy.
346  for (int i = 0; i < NumLocalParts_; ++i) {
347  Parts_[i].resize (tmp[i].size ());
348  for (size_t j = 0; j < tmp[i].size (); ++j) {
349  Parts_[i][j] = tmp[i][j];
350  }
351  }
352  }
353 }
354 
355 //==============================================================================
356 template<class GraphType>
358 {
359  return IsComputed_;
360 }
361 
362 //==============================================================================
363 template<class GraphType>
364 std::ostream&
366 {
367  Teuchos::FancyOStream fos (Teuchos::rcpFromRef (os));
368  fos.setOutputToRootOnly (0);
369  describe (fos);
370  return os;
371 }
372 
373 //==============================================================================
374 template<class GraphType>
376 {
377  std::ostringstream oss;
378  oss << Teuchos::Describable::description();
379  if (isComputed()) {
380  oss << "{status = computed";
381  }
382  else {
383  oss << "{status = is not computed";
384  }
385  oss <<"}";
386  return oss.str();
387 }
388 
389 //==============================================================================
390 template<class GraphType>
391 void OverlappingPartitioner<GraphType>::describe(Teuchos::FancyOStream &os, const Teuchos::EVerbosityLevel verbLevel) const
392 {
393  using std::endl;
394  if (verbLevel == Teuchos::VERB_NONE) {
395  return;
396  }
397 
398  os << "================================================================================" << endl;
399  os << "Ifpack2::OverlappingPartitioner" << endl;
400  os << "Number of local rows = " << Graph_->getNodeNumRows() << endl;
401  os << "Number of global rows = " << Graph_->getGlobalNumRows() << endl;
402  os << "Number of local parts = " << NumLocalParts_ << endl;
403  os << "Overlapping level = " << OverlappingLevel_ << endl;
404  os << "Is computed = " << IsComputed_ << endl;
405  os << "================================================================================" << endl;
406 }
407 
408 
409 }// namespace Ifpack2
410 
411 #define IFPACK2_OVERLAPPINGPARTITIONER_INSTANT(LO,GO,N) \
412  template class Ifpack2::OverlappingPartitioner<Tpetra::CrsGraph< LO, GO, N > >; \
413  template class Ifpack2::OverlappingPartitioner<Tpetra::RowGraph< LO, GO, N > >;
414 
415 #endif // IFPACK2_OVERLAPPINGPARTITIONER_DEF_HPP
Teuchos::Array< local_ordinal_type > Partition_
Definition: Ifpack2_OverlappingPartitioner_decl.hpp:171
Teuchos::Array< Teuchos::ArrayRCP< local_ordinal_type > > Parts_
Definition: Ifpack2_OverlappingPartitioner_decl.hpp:175
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:136
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:149
OverlappingPartitioner(const Teuchos::RCP< const row_graph_type > &graph)
Constructor.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:56
int OverlappingLevel_
Level of overlap.
Definition: Ifpack2_OverlappingPartitioner_decl.hpp:181
int overlappingLevel() const
The number of levels of overlap.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:78
int numLocalParts() const
Number of computed local partitions.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:71
Teuchos::RCP< const row_graph_type > Graph_
The graph to be partitioned.
Definition: Ifpack2_OverlappingPartitioner_decl.hpp:178
virtual void computeOverlappingPartitions()
Computes the partitions. Returns 0 if successful.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:240
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:391
virtual ~OverlappingPartitioner()
Destructor.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:66
virtual bool isComputed() const
Returns true if partitions have been computed successfully.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:357
int NumLocalParts_
Number of local subgraphs.
Definition: Ifpack2_OverlappingPartitioner_decl.hpp:167
std::string description() const
Return a simple one-line description of this object.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:375
virtual void computePartitions()=0
Computes the partitions. Returns 0 if successful.
virtual void compute()
Computes the partitions. Returns 0 if successful.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:188
virtual std::ostream & print(std::ostream &os) const
Prints basic information on iostream. This function is used by operator<<.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:365
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:87
bool verbose_
If true, information are reported to stdout.
Definition: Ifpack2_OverlappingPartitioner_decl.hpp:187
virtual void setParameters(Teuchos::ParameterList &List)
Set all the parameters for the partitioner.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:158
size_t numRowsInPart(const local_ordinal_type Part) const
the number of rows contained in the given partition.
Definition: Ifpack2_OverlappingPartitioner_def.hpp:122
Preconditioners and smoothers for Tpetra sparse matrices.
Definition: Ifpack2_AdditiveSchwarz_decl.hpp:72
virtual void setPartitionParameters(Teuchos::ParameterList &List)=0
Set all the parameters for the partitioner.
bool IsComputed_
If true, the graph has been successfully partitioned.
Definition: Ifpack2_OverlappingPartitioner_decl.hpp:184