Ifpack_GreedyPartitioner.cpp

00001 /*@HEADER
00002 // ***********************************************************************
00003 //
00004 //       Ifpack: Object-Oriented Algebraic Preconditioner Package
00005 //                 Copyright (2002) Sandia Corporation
00006 //
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 //
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
00025 //
00026 // ***********************************************************************
00027 //@HEADER
00028 */
00029 
00030 #include "Ifpack_ConfigDefs.h"
00031 #include "Ifpack_Partitioner.h"
00032 #include "Ifpack_OverlappingPartitioner.h"
00033 #include "Ifpack_GreedyPartitioner.h"
00034 #include "Ifpack_Graph.h"
00035 
00036 #include "Epetra_Comm.h"
00037 #include "Epetra_BlockMap.h"
00038 #include "Epetra_Map.h"
00039 #include "Epetra_CrsGraph.h"
00040 #include "Teuchos_ParameterList.hpp"
00041 
00042 //==============================================================================
00043 int Ifpack_GreedyPartitioner::ComputePartitions()
00044 {
00045   vector<int> ElementsPerPart(NumLocalParts());
00046   vector<int> Count(NumLocalParts());
00047   for (int i = 0 ; i < NumLocalParts() ; ++i)
00048     Count[i] = 0;
00049 
00050   // define how many nodes have to be put on each part
00051   int div = NumMyRows() / NumLocalParts();
00052   int mod = NumMyRows() % NumLocalParts();
00053 
00054   for (int i = 0 ; i < NumLocalParts() ; ++i) {
00055     Count[i] = 0;
00056     ElementsPerPart[i] = div;
00057     if (i < mod) ElementsPerPart[i]++;
00058   }
00059 
00060   for( int i=0 ; i<NumMyRows() ; ++i ) {
00061     Partition_[i] = -1;
00062   }
00063 
00064   int NumEntries;
00065   vector<int> Indices(MaxNumEntries());
00066   
00067   // load root node for partition 0
00068   int CurrentPartition = 0;
00069   int TotalCount = 0;
00070 
00071   // filter singletons and empty rows, put all of them in partition 0
00072   for (int i = 0 ; i < NumMyRows() ; ++i) {
00073     NumEntries = 0;
00074     int ierr = Graph_->ExtractMyRowCopy(i, MaxNumEntries(),
00075                                         NumEntries, &Indices[0]);
00076     IFPACK_CHK_ERR(ierr);
00077     if (NumEntries <= 1) {
00078       Partition_[i] = 0;
00079       TotalCount++;
00080     }
00081   }
00082 
00083   if (TotalCount)
00084     CurrentPartition = 1;
00085 
00086   vector<int> ThisLevel(1);
00087   ThisLevel[0] = RootNode_;
00088 
00089   // be sure that RootNode is not a singleton or empty row
00090   if (Partition_[RootNode_] != -1) {
00091     // look for another RN
00092     for (int i = 0 ; i < NumMyRows() ; ++i)
00093       if (Partition_[i] == -1) {
00094         ThisLevel[0] = i;
00095         break;
00096       }
00097   }
00098   else {
00099     Partition_[RootNode_] = CurrentPartition;
00100   }
00101 
00102   // now aggregate the non-empty and non-singleton rows
00103   while (ThisLevel.size()) {
00104 
00105     vector<int> NextLevel;
00106 
00107     for (unsigned int i = 0 ; i < ThisLevel.size() ; ++i) {
00108 
00109       int CurrentNode = ThisLevel[i];
00110       int ierr = Graph_->ExtractMyRowCopy(CurrentNode, MaxNumEntries(),
00111                                           NumEntries, &Indices[0]);
00112       IFPACK_CHK_ERR(ierr);
00113 
00114       if (NumEntries <= 1)
00115         continue;
00116 
00117       for (int j = 0 ; j < NumEntries ; ++j) {
00118 
00119         int NextNode = Indices[j];
00120         if (NextNode >= NumMyRows()) continue;
00121 
00122         if (Partition_[NextNode] == -1) {
00123           // this is a free node
00124           NumLocalParts_ = CurrentPartition + 1;
00125           Partition_[NextNode] = CurrentPartition;
00126           ++Count[CurrentPartition];
00127           ++TotalCount;
00128           NextLevel.push_back(NextNode);
00129         }
00130       }
00131     } // for (i)
00132 
00133     // check whether change partition or not
00134     if (Count[CurrentPartition] >= ElementsPerPart[CurrentPartition])
00135       ++CurrentPartition;
00136 
00137     // swap next and this
00138     ThisLevel.resize(0);
00139     for (unsigned int i = 0 ; i < NextLevel.size() ; ++i)
00140       ThisLevel.push_back(NextLevel[i]);
00141 
00142     if (ThisLevel.size() == 0 && (TotalCount != NumMyRows())) {
00143       // need to look for new RootNode, do this in a simple way
00144       for (int i = 0 ; i < NumMyRows() ; i++) {
00145         if (Partition_[i] == -1)
00146           ThisLevel.push_back(i);
00147         break;
00148       }
00149     }
00150 
00151   } // while (ok)
00152 
00153   return(0);
00154 }
00155 

Generated on Wed May 12 21:30:18 2010 for IFPACK by  doxygen 1.4.7