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 = -1;
00193   if( ColorIDs_ )
00194     arrayIndex = ColorIDs_->Get(Color);
00195   if (arrayIndex>-1) return(ColorCount_[arrayIndex]);
00196   else return(0);
00197 }
00198 //=========================================================================
00199 int * Epetra_MapColoring::ColorLIDList(int Color) const  {
00200   if (!ListsAreValid_) GenerateLists(); 
00201   int arrayIndex = -1;
00202   if( ColorIDs_ )
00203     arrayIndex = ColorIDs_->Get(Color);
00204   if (arrayIndex>-1) return(ColorLists_[arrayIndex]);
00205   else return(0);
00206 }
00207 //=========================================================================
00208 Epetra_Map * Epetra_MapColoring::GenerateMap(int Color) const {
00209 
00210   if (!ListsAreValid_) GenerateLists(); 
00211   int arrayIndex = -1;
00212   if( ColorIDs_ )
00213     arrayIndex = ColorIDs_->Get(Color);
00214   int NumElements = 0;
00215   int * ColorElementLIDs = 0;
00216   int * ColorElementGIDs =0;
00217   if (arrayIndex>-1) NumElements = ColorCount_[arrayIndex];
00218   if (NumElements>0) {
00219     ColorElementLIDs = ColorLIDList(Color);
00220     ColorElementGIDs = new int[NumElements];
00221     for (int i=0; i<NumElements; i++) ColorElementGIDs[i] = Map().GID(ColorElementLIDs[i]);
00222   }
00223   Epetra_Map * map = new Epetra_Map(-1, NumElements, ColorElementGIDs, 
00224             Map().IndexBase(), Map().Comm());
00225   if (ColorElementGIDs!=0) delete [] ColorElementGIDs;
00226   return(map);
00227 }
00228 //=========================================================================
00229 Epetra_BlockMap * Epetra_MapColoring::GenerateBlockMap(int Color) const {
00230 
00231   if (!ListsAreValid_) GenerateLists(); 
00232   int arrayIndex = -1;
00233   if( ColorIDs_ )
00234     arrayIndex = ColorIDs_->Get(Color);
00235   int NumElements = 0;
00236   int * ColorElementLIDs = 0;
00237   int * ColorElementSizes = 0;
00238   int * ColorElementGIDs = 0;
00239   if (arrayIndex>-1) NumElements = ColorCount_[arrayIndex];
00240   if (NumElements>0) {
00241     ColorElementLIDs = ColorLIDList(Color);
00242     ColorElementSizes = new int[NumElements];
00243     ColorElementGIDs = new int[NumElements];
00244     for (int i=0; i<NumElements; i++) ColorElementGIDs[i] = Map().GID(ColorElementLIDs[i]);
00245   }
00246   int * MapElementSizes = Map().ElementSizeList();
00247 
00248   {for (int i=0; i<NumElements; i++) 
00249     ColorElementSizes[i] = MapElementSizes[ColorElementLIDs[i]];}
00250 
00251   Epetra_BlockMap * map = new Epetra_BlockMap(-1, NumElements, ColorElementGIDs, 
00252                 ColorElementSizes,
00253                 Map().IndexBase(), Map().Comm());
00254 
00255   if (ColorElementGIDs!=0) delete [] ColorElementGIDs;
00256   if (ColorElementSizes!=0) delete [] ColorElementSizes;
00257 
00258   return(map);
00259 }
00260 //=========================================================================
00261 void Epetra_MapColoring::Print(ostream& os) const {
00262   int MyPID = Map().Comm().MyPID();
00263   int NumProc = Map().Comm().NumProc();
00264   
00265   if (MyPID==0) os 
00266     << endl 
00267     << " *****************************************" << endl
00268     << " Coloring information arranged map element" << endl 
00269     << " *****************************************" << endl
00270     << endl;
00271   for (int iproc=0; iproc < NumProc; iproc++) {
00272     if (MyPID==iproc) {
00273       int NumMyElements1 =Map(). NumMyElements();
00274       int * MyGlobalElements1 = Map().MyGlobalElements();
00275 
00276       if (MyPID==0) {
00277   os.width(8);
00278   os <<  "     MyPID"; os << "    ";
00279   os.width(12);
00280   os <<  "GID  ";
00281   os.width(20);
00282   os <<  "Color  ";
00283   os << endl;
00284       }
00285       for (int i=0; i < NumMyElements1; i++) {
00286   os.width(10);
00287   os <<  MyPID; os << "    ";
00288   os.width(10);
00289   os << MyGlobalElements1[i] << "    ";
00290   os.width(20);
00291   os <<  ElementColors_[i];
00292   os << endl;
00293       }
00294       os << flush; 
00295     }
00296 
00297     // Do a few global ops to give I/O a chance to complete
00298     Map().Comm().Barrier();
00299     Map().Comm().Barrier();
00300     Map().Comm().Barrier();
00301   }
00302 
00303   if (MyPID==0) os 
00304     << endl 
00305     << " **************************************" << endl
00306     << " Coloring information arranged by color" << endl 
00307     << " **************************************" << endl
00308     << endl;
00309   {for (int iproc=0; iproc < NumProc; iproc++) {
00310     if (MyPID==iproc) {
00311       if (NumColors()==0) os << " No colored elements on processor " << MyPID << endl;
00312       else {
00313         os << "Number of colors in map = " << NumColors() << endl
00314            << "Default color           = " << DefaultColor() << endl << endl;
00315         if (MyPID==0) {
00316           os.width(8);
00317           os <<  "     MyPID"; os << "    ";
00318           os.width(12);
00319           os <<  "LID  ";
00320           os.width(20);
00321           os <<  "Color  ";
00322           os << endl;
00323         }
00324         int * ColorValues = ListOfColors();
00325         for (int ii=0; ii<NumColors(); ii++) {
00326           int CV = ColorValues[ii];
00327     int ColorCount = NumElementsWithColor(CV);
00328     int * LIDList = ColorLIDList(CV);
00329     
00330     
00331     for (int i=0; i < ColorCount; i++) {
00332       os.width(10);
00333       os <<  MyPID; os << "    ";
00334       os.width(10);
00335       os << LIDList[i] << "    ";
00336       os.width(20);
00337       os << CV;
00338       os << endl;
00339     }
00340     os << flush; 
00341   }
00342       }
00343     }
00344     // Do a few global ops to give I/O a chance to complete
00345     Map().Comm().Barrier();
00346     Map().Comm().Barrier();
00347     Map().Comm().Barrier();
00348   }}
00349   return;
00350 }
00351 //=========================================================================
00352 int Epetra_MapColoring::MaxNumColors() const {
00353 
00354   if (!ListsAreValid_) GenerateLists(); 
00355   int tmp1 = NumColors_, tmp2;
00356   Map().Comm().MaxAll(&tmp1, &tmp2, 1);
00357   return(tmp2);
00358 }
00359 //=========================================================================
00360 int Epetra_MapColoring::CheckSizes(const Epetra_SrcDistObject& Source) {
00361   (void)Source;//prevents unused variable compiler warning
00362   return(0);
00363 }
00364 
00365 //=========================================================================
00366 int Epetra_MapColoring::CopyAndPermute(const Epetra_SrcDistObject& Source,
00367                                        int NumSameIDs, 
00368                int NumPermuteIDs,
00369                                        int * PermuteToLIDs, 
00370                int *PermuteFromLIDs,
00371                                        const Epetra_OffsetIndex * Indexor)
00372 {
00373   (void)Indexor;
00374   const Epetra_MapColoring & A = dynamic_cast<const Epetra_MapColoring &>(Source);
00375 
00376   int * From = A.ElementColors();
00377   int *To = ElementColors_;
00378 
00379   // Do copy first
00380   if (NumSameIDs>0)
00381     if (To!=From) {
00382       for (int j=0; j<NumSameIDs; j++)
00383   To[j] = From[j];
00384     }
00385   // Do local permutation next
00386   if (NumPermuteIDs>0)
00387     for (int j=0; j<NumPermuteIDs; j++) 
00388       To[PermuteToLIDs[j]] = From[PermuteFromLIDs[j]];
00389   
00390   return(0);
00391 }
00392 
00393 //=========================================================================
00394 int Epetra_MapColoring::PackAndPrepare(const Epetra_SrcDistObject & Source,
00395                                        int NumExportIDs,
00396                                        int * ExportLIDs,
00397                int & LenExports,
00398                                        char * & Exports,
00399                int & SizeOfPacket,
00400                int * Sizes,
00401                bool & VarSizes,
00402                                        Epetra_Distributor & Distor)
00403 {
00404   (void)Sizes;
00405   (void)VarSizes;
00406   (void)Distor;
00407   const Epetra_MapColoring & A = dynamic_cast<const Epetra_MapColoring &>(Source);
00408 
00409   int  * From = A.ElementColors();
00410   int * IntExports = 0;
00411 
00412   SizeOfPacket = (int)sizeof(int); 
00413 
00414   if (NumExportIDs*SizeOfPacket>LenExports) {
00415     if (LenExports>0) delete [] Exports;
00416     LenExports = NumExportIDs*SizeOfPacket;
00417     IntExports = new int[LenExports];
00418     Exports = (char *) IntExports;
00419   }
00420 
00421   int * ptr;
00422 
00423   if (NumExportIDs>0) {
00424     ptr = (int *) Exports;    
00425     for (int j=0; j<NumExportIDs; j++) ptr[j] = From[ExportLIDs[j]];
00426   }
00427   
00428   return(0);
00429 }
00430 
00431 //=========================================================================
00432 int Epetra_MapColoring::UnpackAndCombine(const Epetra_SrcDistObject & Source,
00433            int NumImportIDs,
00434                                          int * ImportLIDs, 
00435                                          int LenImports,
00436            char * Imports,
00437                                          int & SizeOfPacket, 
00438            Epetra_Distributor & Distor, 
00439            Epetra_CombineMode CombineMode,
00440                                          const Epetra_OffsetIndex * Indexor )
00441 {
00442   (void)Source;
00443   (void)LenImports;
00444   (void)Imports;
00445   (void)SizeOfPacket;
00446   (void)Distor;
00447   (void)Indexor;
00448   int j;
00449   
00450   if(    CombineMode != Add
00451       && CombineMode != Zero
00452       && CombineMode != Insert
00453       && CombineMode != AbsMax )
00454     EPETRA_CHK_ERR(-1); //Unsupported CombinedMode, will default to Zero
00455 
00456   if (NumImportIDs<=0) return(0);
00457 
00458   int * To = ElementColors_;
00459 
00460   int * ptr;
00461   // Unpack it...
00462 
00463   ptr = (int *) Imports;
00464     
00465   if (CombineMode==Add)
00466     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] += ptr[j]; // Add to existing value
00467   else if(CombineMode==Insert)
00468     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] = ptr[j];
00469   else if(CombineMode==AbsMax) {
00470     for (j=0; j<NumImportIDs; j++) To[ImportLIDs[j]] = 0;
00471     for (j=0; j<NumImportIDs; j++)  To[ImportLIDs[j]] = EPETRA_MAX( To[ImportLIDs[j]],std::abs(ptr[j]));
00472   }
00473   
00474   return(0);
00475 }
00476 

Generated on Wed May 12 21:41:05 2010 for Epetra Package Browser (Single Doxygen Collection) by  doxygen 1.4.7