IFPACK Development
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 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Michael A. Heroux (maherou@sandia.gov)
00038 //
00039 // ***********************************************************************
00041 */
00042
00043 #include "Ifpack_ConfigDefs.h"
00044 #include "Ifpack_Partitioner.h"
00045 #include "Ifpack_OverlappingPartitioner.h"
00046 #include "Ifpack_GreedyPartitioner.h"
00047 #include "Ifpack_Graph.h"
00048
00049 #include "Epetra_Comm.h"
00050 #include "Epetra_BlockMap.h"
00051 #include "Epetra_Map.h"
00052 #include "Epetra_CrsGraph.h"
00053 #include "Teuchos_ParameterList.hpp"
00054
00055 //==============================================================================
00056 int Ifpack_GreedyPartitioner::ComputePartitions()
00057 {
00058   vector<int> ElementsPerPart(NumLocalParts());
00059   vector<int> Count(NumLocalParts());
00060   for (int i = 0 ; i < NumLocalParts() ; ++i)
00061     Count[i] = 0;
00062
00063   // define how many nodes have to be put on each part
00064   int div = NumMyRows() / NumLocalParts();
00065   int mod = NumMyRows() % NumLocalParts();
00066
00067   for (int i = 0 ; i < NumLocalParts() ; ++i) {
00068     Count[i] = 0;
00069     ElementsPerPart[i] = div;
00070     if (i < mod) ElementsPerPart[i]++;
00071   }
00072
00073   for( int i=0 ; i<NumMyRows() ; ++i ) {
00074     Partition_[i] = -1;
00075   }
00076
00077   int NumEntries;
00078   vector<int> Indices(MaxNumEntries());
00079
00080   // load root node for partition 0
00081   int CurrentPartition = 0;
00082   int TotalCount = 0;
00083
00084   // filter singletons and empty rows, put all of them in partition 0
00085   for (int i = 0 ; i < NumMyRows() ; ++i) {
00086     NumEntries = 0;
00087     int ierr = Graph_->ExtractMyRowCopy(i, MaxNumEntries(),
00088                                         NumEntries, &Indices[0]);
00089     IFPACK_CHK_ERR(ierr);
00090     if (NumEntries <= 1) {
00091       Partition_[i] = 0;
00092       TotalCount++;
00093     }
00094   }
00095
00096   if (TotalCount)
00097     CurrentPartition = 1;
00098
00099   vector<int> ThisLevel(1);
00100   ThisLevel[0] = RootNode_;
00101
00102   // be sure that RootNode is not a singleton or empty row
00103   if (Partition_[RootNode_] != -1) {
00104     // look for another RN
00105     for (int i = 0 ; i < NumMyRows() ; ++i)
00106       if (Partition_[i] == -1) {
00107         ThisLevel[0] = i;
00108         break;
00109       }
00110   }
00111   else {
00112     Partition_[RootNode_] = CurrentPartition;
00113   }
00114
00115   // now aggregate the non-empty and non-singleton rows
00116   while (ThisLevel.size()) {
00117
00118     vector<int> NextLevel;
00119
00120     for (unsigned int i = 0 ; i < ThisLevel.size() ; ++i) {
00121
00122       int CurrentNode = ThisLevel[i];
00123       int ierr = Graph_->ExtractMyRowCopy(CurrentNode, MaxNumEntries(),
00124                                           NumEntries, &Indices[0]);
00125       IFPACK_CHK_ERR(ierr);
00126
00127       if (NumEntries <= 1)
00128         continue;
00129
00130       for (int j = 0 ; j < NumEntries ; ++j) {
00131
00132         int NextNode = Indices[j];
00133         if (NextNode >= NumMyRows()) continue;
00134
00135         if (Partition_[NextNode] == -1) {
00136           // this is a free node
00137           NumLocalParts_ = CurrentPartition + 1;
00138           Partition_[NextNode] = CurrentPartition;
00139           ++Count[CurrentPartition];
00140           ++TotalCount;
00141           NextLevel.push_back(NextNode);
00142         }
00143       }
00144     } // for (i)
00145
00146     // check whether change partition or not
00147     if (Count[CurrentPartition] >= ElementsPerPart[CurrentPartition])
00148       ++CurrentPartition;
00149
00150     // swap next and this
00151     ThisLevel.resize(0);
00152     for (unsigned int i = 0 ; i < NextLevel.size() ; ++i)
00153       ThisLevel.push_back(NextLevel[i]);
00154
00155     if (ThisLevel.size() == 0 && (TotalCount != NumMyRows())) {
00156       // need to look for new RootNode, do this in a simple way
00157       for (int i = 0 ; i < NumMyRows() ; i++) {
00158         if (Partition_[i] == -1)
00159           ThisLevel.push_back(i);
00160         break;
00161       }
00162     }
00163
00164   } // while (ok)
00165
00166   return(0);
00167 }
00168