Epetra_MapColoring.cpp

Go to the documentation of this file.
00001 
00002 //@HEADER
00003 // ************************************************************************
00004 // 
00005 //               Epetra: Linear Algebra Services Package 
00006 //                 Copyright (2001) Sandia Corporation
00007 // 
00008 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00009 // license for use of this work by or on behalf of the U.S. Government.
00010 // 
00011 // This library is free software; you can redistribute it and/or modify
00012 // it under the terms of the GNU Lesser General Public License as
00013 // published by the Free Software Foundation; either version 2.1 of the
00014 // License, or (at your option) any later version.
00015 //  
00016 // This library is distributed in the hope that it will be useful, but
00017 // WITHOUT ANY WARRANTY; without even the implied warranty of
00018 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019 // Lesser General Public License for more details.
00020 //  
00021 // You should have received a copy of the GNU Lesser General Public
00022 // License along with this library; if not, write to the Free Software
00023 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00024 // USA
00025 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00026 // 
00027 // ************************************************************************
00028 //@HEADER
00029 
00030 #include "Epetra_HashTable.h"
00031 #include "Epetra_Comm.h"
00032 #include "Epetra_Map.h"
00033 #include "Epetra_MapColoring.h"
00034 #include "Epetra_Util.h"
00035 //=============================================================================
00036 Epetra_MapColoring::Epetra_MapColoring(const Epetra_BlockMap& Map, int * ElementColors, 
00037                const int DefaultColor)
00038   : Epetra_DistObject(Map, "Epetra::MapColoring"),
00039     DefaultColor_(DefaultColor),
00040     ColorIDs_(0),
00041     FirstColor_(0),
00042     NumColors_(0),
00043     ListOfColors_(0),
00044     ColorCount_(0),
00045     ElementColors_(0),
00046     ColorLists_(0),
00047     Allocated_(false),
00048     ListsAreGenerated_(false),
00049     ListsAreValid_(false)
00050 {
00051   Allocate(ElementColors, 1);
00052 }
00053 //=============================================================================
00054 Epetra_MapColoring::Epetra_MapColoring(const Epetra_BlockMap& Map,
00055                const int DefaultColor)
00056   : Epetra_DistObject(Map, "Epetra::MapColoring"),
00057     DefaultColor_(DefaultColor),
00058     ColorIDs_(0),
00059     FirstColor_(0),
00060     NumColors_(0),
00061     ListOfColors_(0),
00062     ColorCount_(0),
00063     ElementColors_(0),
00064     ColorLists_(0),
00065     Allocated_(false),
00066     ListsAreGenerated_(false),
00067     ListsAreValid_(false)
00068 {
00069   Allocate(&DefaultColor_, 0);
00070 }
00071 //=============================================================================
00072 Epetra_MapColoring::Epetra_MapColoring(const Epetra_MapColoring& Source)
00073   : Epetra_DistObject(Source),
00074     DefaultColor_(Source.DefaultColor_),
00075     ColorIDs_(0),
00076     FirstColor_(0),
00077     NumColors_(0),
00078     ListOfColors_(0),
00079     ColorCount_(0),
00080     ElementColors_(0),
00081     ColorLists_(0),
00082     Allocated_(false),
00083     ListsAreGenerated_(false),
00084     ListsAreValid_(false)
00085 {
00086   Allocate(Source.ElementColors_, 1);
00087 }
00088 //=========================================================================
00089 Epetra_MapColoring::~Epetra_MapColoring(){
00090 
00091 
00092   if (Allocated_ && Map().NumMyElements()>0) delete [] ElementColors_;
00093   if (ListsAreGenerated_) DeleteLists();
00094 }
00095 
00096 //=========================================================================
00097 int Epetra_MapColoring::DeleteLists() const {
00098 
00099 
00100   if (ListsAreGenerated_) {
00101     for (int i=0; i<NumColors_; i++) if (ColorLists_[i]!=0) delete [] ColorLists_[i];
00102     delete [] ColorLists_;
00103     delete [] ColorCount_;
00104     delete [] ListOfColors_;
00105     delete ColorIDs_;
00106     ListItem * CurItem = FirstColor_;
00107     while (CurItem!=0) {
00108       ListItem * NextItem = CurItem->NextItem;
00109       delete CurItem;
00110       CurItem = NextItem;
00111     }
00112   }
00113   ListsAreValid_ = false;
00114   return(0);
00115 }
00116 
00117 //=========================================================================
00118 int Epetra_MapColoring::Allocate(int * ElementColors, int Increment)
00119 {
00120   
00121   if (Allocated_) return(0);
00122   
00123   int NumMyElements = Map().NumMyElements();
00124   if (NumMyElements>0) ElementColors_ = new int[NumMyElements];
00125   for (int i=0; i< NumMyElements; i++) ElementColors_[i] = ElementColors[i*Increment];
00126   Allocated_ = true;
00127   return(0);
00128 }
00129 
00130 //=========================================================================
00131 int Epetra_MapColoring::GenerateLists() const {
00132   int NumMyElements = Map().NumMyElements();
00133   if (NumMyElements==0) return(0); // Nothing to do
00134 
00135   if (ListsAreValid_) return(0); // Already been here
00136 
00137   if (ListsAreGenerated_) DeleteLists();  // Delete any existing lists
00138 
00139 
00140   // Scan the ElementColors to determine how many colors we have
00141   NumColors_ = 1;
00142   FirstColor_ = new ListItem(ElementColors_[0]); // Initialize First color in list
00143   for (int i=1; i<NumMyElements; i++) if (!InItemList(ElementColors_[i])) NumColors_++;
00144 
00145   // Create hash table that maps color IDs to the integers 0,...NumColors_
00146   ColorIDs_ = new Epetra_HashTable(NumColors_);
00147   ListOfColors_ = new int[NumColors_];
00148   ListItem * CurItem = FirstColor_;
00149   {for (int i=0; i<NumColors_; i++) {
00150     ColorIDs_->Add(CurItem->ItemValue, i); // Create hash table entry
00151     ListOfColors_[i] = CurItem->ItemValue; // Put color value in a list of colors
00152     CurItem = CurItem->NextItem;
00153   }}
00154   Epetra_Util util;
00155   util.Sort(true, NumColors_, ListOfColors_, 0, 0, 0, 0); // Sort List of colors in ascending order
00156   // Count the number of IDs of each color
00157   ColorCount_ = new int[NumColors_];
00158   {for (int i=0; i<NumColors_; i++) ColorCount_[i] = 0;}
00159   {for (int i=0; i<NumMyElements; i++) ColorCount_[ColorIDs_->Get(ElementColors_[i])]++;}
00160 
00161   // Finally build list of IDs grouped by color
00162   ColorLists_ = new int *[NumColors_];
00163   {for (int i=0; i<NumColors_; i++) ColorLists_[i] = new int[ColorCount_[i]];}
00164   {for (int i=0; i<NumColors_; i++) ColorCount_[i] = 0;} // Reset so we can use for counting
00165   {for (int i=0; i<NumMyElements; i++) {
00166     int j = ColorIDs_->Get(ElementColors_[i]);
00167     ColorLists_[j][ColorCount_[j]++] = i;
00168   }}
00169   ListsAreValid_ = true;
00170   ListsAreGenerated_ = true;
00171 
00172   return(0);
00173 }
00174 //=========================================================================
00175 bool Epetra_MapColoring::InItemList(int ColorValue) const {
00176   bool ColorFound = false;
00177   ListItem * CurColor = 0;
00178   ListItem * NextColor = FirstColor_;
00179   while (!ColorFound && NextColor!=0) {
00180     CurColor = NextColor;
00181     NextColor = CurColor->NextItem;
00182     if (ColorValue==CurColor->ItemValue) ColorFound = true;
00183   }
00184 
00185   if (!ColorFound) CurColor->NextItem = new ListItem(ColorValue);
00186 
00187   return(ColorFound);
00188 }
00189 //=========================================================================
00190 int Epetra_MapColoring::NumElementsWithColor(int Color) const  {
00191   if (!ListsAreValid_) GenerateLists(); 
00192   int arrayIndex = ColorIDs_->Get(Color);
00193   if (arrayIndex>-1) return(ColorCount_[arrayIndex]);
00194   else return(0);
00195 }
00196 //=========================================================================
00197 int * Epetra_MapColoring::ColorLIDList(int Color) const  {
00198   if (!ListsAreValid_) GenerateLists(); 
00199   int arrayIndex = ColorIDs_->Get(Color);
00200   if (arrayIndex>-1) return(ColorLists_[arrayIndex]);
00201   else return(0);
00202 }
00203 //=========================================================================
00204 Epetra_Map * Epetra_MapColoring::GenerateMap(int Color) const {
00205 
00206   if (!ListsAreValid_) GenerateLists(); 
00207   int arrayIndex = ColorIDs_->Get(Color);
00208   int NumElements = 0;
00209   int * ColorElementLIDs = 0;
00210   int * ColorElementGIDs =0;
00211   if (arrayIndex>-1) NumElements = ColorCount_[arrayIndex];
00212   if (NumElements>0) {
00213     ColorElementLIDs = ColorLIDList(Color);
00214     ColorElementGIDs = new int[NumElements];
00215     for (int i=0; i<NumElements; i++) ColorElementGIDs[i] = Map().GID(ColorElementLIDs[i]);
00216   }
00217   Epetra_Map * map = new Epetra_Map(-1, NumElements, ColorElementGIDs, 
00218             Map().IndexBase(), Map().Comm());
00219   if (ColorElementGIDs!=0) delete [] ColorElementGIDs;
00220   return(map);
00221 }
00222 //=========================================================================
00223 Epetra_BlockMap * Epetra_MapColoring::GenerateBlockMap(int Color) const {
00224 
00225   if (!ListsAreValid_) GenerateLists(); 
00226   int arrayIndex = ColorIDs_->Get(Color);
00227   int NumElements = 0;
00228   int * ColorElementLIDs = 0;
00229   int * ColorElementSizes = 0;
00230   int * ColorElementGIDs = 0;
00231   if (arrayIndex>-1) NumElements = ColorCount_[arrayIndex];
00232   if (NumElements>0) {
00233     ColorElementLIDs = ColorLIDList(Color);
00234     ColorElementSizes = new int[NumElements];
00235     ColorElementGIDs = new int[NumElements];
00236     for (int i=0; i<NumElements; i++) ColorElementGIDs[i] = Map().GID(ColorElementLIDs[i]);
00237   }
00238   int * MapElementSizes = Map().ElementSizeList();
00239 
00240   {for (int i=0; i<NumElements; i++) 
00241     ColorElementSizes[i] = MapElementSizes[ColorElementLIDs[i]];}
00242 
00243   Epetra_BlockMap * map = new Epetra_BlockMap(-1, NumElements, ColorElementGIDs, 
00244                 ColorElementSizes,
00245                 Map().IndexBase(), Map().Comm());
00246 
00247   if (ColorElementGIDs!=0) delete [] ColorElementGIDs;
00248   if (ColorElementSizes!=0) delete [] ColorElementSizes;
00249 
00250   return(map);
00251 }
00252 //=========================================================================
00253 void Epetra_MapColoring::Print(ostream& os) const {
00254   int MyPID = Map().Comm().MyPID();
00255   int NumProc = Map().Comm().NumProc();
00256   
00257   if (MyPID==0) os 
00258     << endl 
00259     << " *****************************************" << endl
00260     << " Coloring information arranged map element" << endl 
00261     << " *****************************************" << endl
00262     << endl;
00263   for (int iproc=0; iproc < NumProc; iproc++) {
00264     if (MyPID==iproc) {
00265       int NumMyElements1 =Map(). NumMyElements();
00266       int * MyGlobalElements1 = Map().MyGlobalElements();
00267 
00268       if (MyPID==0) {
00269   os.width(8);
00270   os <<  "     MyPID"; os << "    ";
00271   os.width(12);
00272   os <<  "GID  ";
00273   os.width(20);
00274   os <<  "Color  ";
00275   os << endl;
00276       }
00277       for (int i=0; i < NumMyElements1; i++) {
00278   os.width(10);
00279   os <<  MyPID; os << "    ";
00280   os.width(10);
00281   os << MyGlobalElements1[i] << "    ";
00282   os.width(20);
00283   os <<  ElementColors_[i];
00284   os << endl;
00285       }
00286       os << flush; 
00287     }
00288 
00289     // Do a few global ops to give I/O a chance to complete
00290     Map().Comm().Barrier();
00291     Map().Comm().Barrier();
00292     Map().Comm().Barrier();
00293   }
00294 
00295   if (MyPID==0) os 
00296     << endl 
00297     << " **************************************" << endl
00298     << " Coloring information arranged by color" << endl 
00299     << " **************************************" << endl
00300     << endl;
00301   {for (int iproc=0; iproc < NumProc; iproc++) {
00302     if (MyPID==iproc) {
00303       if (NumColors()==0) os << " No colored elements on processor " << MyPID << endl;
00304       else {
00305         os << "Number of colors in map = " << NumColors() << endl
00306            << "Default color           = " << DefaultColor() << endl << endl;
00307         if (MyPID==0) {
00308           os.width(8);
00309           os <<  "     MyPID"; os << "    ";
00310           os.width(12);
00311           os <<  "LID  ";
00312           os.width(20);
00313           os <<  "Color  ";
00314           os << endl;
00315         }
00316         int * ColorValues = ListOfColors();
00317         for (int ii=0; ii<NumColors(); ii++) {
00318           int CV = ColorValues[ii];
00319     int ColorCount = NumElementsWithColor(CV);
00320     int * LIDList = ColorLIDList(CV);
00321     
00322     
00323     for (int i=0; i < ColorCount; i++) {
00324       os.width(10);
00325       os <<  MyPID; os << "    ";
00326       os.width(10);
00327       os << LIDList[i] << "    ";
00328       os.width(20);
00329       os << CV;
00330       os << endl;
00331     }
00332     os << flush; 
00333   }
00334       }
00335     }
00336     // Do a few global ops to give I/O a chance to complete
00337     Map().Comm().Barrier();
00338     Map().Comm().Barrier();
00339     Map().Comm().Barrier();
00340   }}
00341   return;
00342 }
00343 //=========================================================================
00344 int Epetra_MapColoring::MaxNumColors() const {
00345 
00346   if (!ListsAreValid_) GenerateLists(); 
00347   int tmp1 = NumColors_, tmp2;
00348   Map().Comm().MaxAll(&tmp1, &tmp2, 1);
00349   return(tmp2);
00350 }
00351 //=========================================================================
00352 int Epetra_MapColoring::CheckSizes(const Epetra_SrcDistObject& Source) {
00353   (void)Source;//prevents unused variable compiler warning
00354   return(0);
00355 }
00356 
00357 //=========================================================================
00358 int Epetra_MapColoring::CopyAndPermute(const Epetra_SrcDistObject& Source,
00359                                        int NumSameIDs, 
00360                int NumPermuteIDs,
00361                                        int * PermuteToLIDs, 
00362                int *PermuteFromLIDs,
00363                                        const Epetra_OffsetIndex * Indexor)
00364 {
00365   (void)Indexor;
00366   const Epetra_MapColoring & A = dynamic_cast<const Epetra_MapColoring &>(Source);
00367 
00368   int * From = A.ElementColors();
00369   int *To = ElementColors_;
00370 
00371   // Do copy first
00372   if (NumSameIDs>0)
00373     if (To!=From) {
00374       for (int j=0; j<NumSameIDs; j++)
00375   To[j] = From[j];
00376     }
00377   // Do local permutation next
00378   if (NumPermuteIDs>0)
00379     for (int j=0; j<NumPermuteIDs; j++) 
00380       To[PermuteToLIDs[j]] = From[PermuteFromLIDs[j]];
00381   
00382   return(0);
00383 }
00384 
00385 //=========================================================================
00386 int Epetra_MapColoring::PackAndPrepare(const Epetra_SrcDistObject & Source,
00387                                        int NumExportIDs,
00388                                        int * ExportLIDs,
00389                int & LenExports,
00390                                        char * & Exports,
00391                int & SizeOfPacket,
00392                int * Sizes,
00393                bool & VarSizes,
00394                                        Epetra_Distributor & Distor)
00395 {
00396   (void)Sizes;
00397   (void)VarSizes;
00398   (void)Distor;
00399   const Epetra_MapColoring & A = dynamic_cast<const Epetra_MapColoring &>(Source);
00400 
00401   int  * From = A.ElementColors();
00402   int * IntExports = 0;
00403 
00404   SizeOfPacket = (int)sizeof(int); 
00405 
00406   if (NumExportIDs*SizeOfPacket>LenExports) {
00407     if (LenExports>0) delete [] Exports;
00408     LenExports = NumExportIDs*SizeOfPacket;
00409     IntExports = new int[LenExports];
00410     Exports = (char *) IntExports;
00411   }
00412 
00413   int * ptr;
00414 
00415   if (NumExportIDs>0) {
00416     ptr = (int *) Exports;    
00417     for (int j=0; j<NumExportIDs; j++) ptr[j] = From[ExportLIDs[j]];
00418   }
00419   
00420   return(0);
00421 }
00422 
00423 //=========================================================================
00424 int Epetra_MapColoring::UnpackAndCombine(const Epetra_SrcDistObject & Source,
00425            int NumImportIDs,
00426                                          int * ImportLIDs, 
00427                                          int LenImports,
00428            char * Imports,
00429                                          int & SizeOfPacket, 
00430            Epetra_Distributor & Distor, 
00431            Epetra_CombineMode CombineMode,
00432                                          const Epetra_OffsetIndex * Indexor )
00433 {
00434   (void)Source;
00435   (void)LenImports;
00436   (void)Imports;
00437   (void)SizeOfPacket;
00438   (void)Distor;
00439   (void)Indexor;
00440   int j;
00441   
00442   if(    CombineMode != Add
00443       && CombineMode != Zero
00444       && CombineMode != Insert
00445       && CombineMode != AbsMax )
00446     EPETRA_CHK_ERR(-1); //Unsupported CombinedMode, will default to Zero
00447 
00448   if (NumImportIDs<=0) return(0);
00449 
00450   int * To = ElementColors_;
00451 
00452   int * ptr;
00453   // Unpack it...
00454 
00455   ptr = (int *) Imports;
00456     
00457   if (CombineMode==Add)
00458     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] += ptr[j]; // Add to existing value
00459   else if(CombineMode==Insert)
00460     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] = ptr[j];
00461   else if(CombineMode==AbsMax) {
00462     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] = 0;
00463     for (j=0; j<NumImportIDs; j++)  To[ImportLIDs[j]] = EPETRA_MAX( To[ImportLIDs[j]],std::abs(ptr[j]));
00464   }
00465   
00466   return(0);
00467 }
00468 

Generated on Thu Sep 18 12:37:57 2008 for Epetra Package Browser (Single Doxygen Collection) by doxygen 1.3.9.1