Ifpack_METISPartitioner.cpp

/*@HEADER
// ***********************************************************************
//
//       Ifpack: Object-Oriented Algebraic Preconditioner Package
//                 Copyright (2002) Sandia Corporation
//
// Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
// license for use of this work by or on behalf of the U.S. Government.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
//
// 3. Neither the name of the Corporation nor the names of the
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
//
// ***********************************************************************
//@HEADER
*/

#include "Ifpack_ConfigDefs.h"
#include "Ifpack_Partitioner.h"
#include "Ifpack_OverlappingPartitioner.h"
#include "Ifpack_METISPartitioner.h"
#include "Ifpack_Graph.h"
#include "Ifpack_Graph_Epetra_CrsGraph.h"
#include "Epetra_Comm.h"
#include "Epetra_CrsGraph.h"
#include "Epetra_Map.h"
#include "Teuchos_ParameterList.hpp"
#include "Teuchos_RefCountPtr.hpp"

// may need to change this for wierd installations
typedef int idxtype;
#ifdef HAVE_IFPACK_METIS
extern "C" {
  void METIS_EstimateMemory(int *, idxtype *, idxtype *, int *, int *, int *);
  void METIS_PartGraphKway(int *, idxtype *, idxtype *, idxtype *, 
               idxtype *, int *, int *, int *, int *, int *,
               idxtype *);
  void METIS_PartGraphRecursive(int *, idxtype *, idxtype *, 
                idxtype *, idxtype *, int *, int *, int *, 
                int *, int *, idxtype *);

}
#endif

//==============================================================================
// NOTE:
// - matrix is supposed to be localized, and passes through the
// singleton filter. This means that I do not have to look
// for Dirichlet nodes (singletons). Also, all rows and columns are 
// local.
int Ifpack_METISPartitioner::ComputePartitions()
{

  int ierr;
#ifdef HAVE_IFPACK_METIS
  int nbytes = 0;
  int edgecut;
#endif

  Teuchos::RefCountPtr<Epetra_CrsGraph> SymGraph ;
  Teuchos::RefCountPtr<Epetra_Map> SymMap;
  Teuchos::RefCountPtr<Ifpack_Graph_Epetra_CrsGraph> SymIFPACKGraph;
  Teuchos::RefCountPtr<Ifpack_Graph> IFPACKGraph = Teuchos::rcp( (Ifpack_Graph*)Graph_, false );

  int Length = 2 * MaxNumEntries();
  int NumIndices;
  std::vector<int> Indices;
  Indices.resize(Length);

  /* construct the CSR graph information of the LOCAL matrix
     using the get_row function */

  std::vector<idxtype> wgtflag;
  wgtflag.resize(4);

  std::vector<int> options;
  options.resize(4);
  
  int numflag;

  if (UseSymmetricGraph_) {

#if !defined(EPETRA_NO_32BIT_GLOBAL_INDICES) || !defined(EPETRA_NO_64BIT_GLOBAL_INDICES)
    // need to build a symmetric graph. 
    // I do this in two stages:
    // 1.- construct an Epetra_CrsMatrix, symmetric
    // 2.- convert the Epetra_CrsMatrix into METIS format
    SymMap = Teuchos::rcp( new Epetra_Map(NumMyRows(),0,Graph_->Comm()) );
    SymGraph = Teuchos::rcp( new Epetra_CrsGraph(Copy,*SymMap,0) );
#endif

#ifndef EPETRA_NO_32BIT_GLOBAL_INDICES
      if(SymGraph->RowMap().GlobalIndicesInt()) {
        for (int i = 0; i < NumMyRows() ; ++i) {

          ierr = Graph_->ExtractMyRowCopy(i, Length, NumIndices, &Indices[0]);
          IFPACK_CHK_ERR(ierr);

          for (int j = 0 ; j < NumIndices ; ++j) {
            int jj = Indices[j];
            if (jj != i) {
              SymGraph->InsertGlobalIndices(i,1,&jj);
              SymGraph->InsertGlobalIndices(jj,1,&i);
            }
          }
        }
      }
      else
#endif
#ifndef EPETRA_NO_64BIT_GLOBAL_INDICES
      if(SymGraph->RowMap().GlobalIndicesLongLong()) {
        for (int i = 0; i < NumMyRows() ; ++i) {
          long long i_LL = i;

          ierr = Graph_->ExtractMyRowCopy(i, Length, NumIndices, &Indices[0]);
          IFPACK_CHK_ERR(ierr);

          for (int j = 0 ; j < NumIndices ; ++j) {
            long long jj = Indices[j];
            if (jj != i_LL) {
              SymGraph->InsertGlobalIndices(i_LL,1,&jj);
              SymGraph->InsertGlobalIndices(jj,1,&i_LL);
            }
          }
        }
      }
      else
#endif
        throw "Ifpack_METISPartitioner::ComputePartitions: GlobalIndices type unknown";

    IFPACK_CHK_ERR(SymGraph->FillComplete());
    SymIFPACKGraph = Teuchos::rcp( new Ifpack_Graph_Epetra_CrsGraph(SymGraph) );
    IFPACKGraph = SymIFPACKGraph;
  }

  // now work on IFPACKGraph, that can be the symmetric or
  // the non-symmetric one

  /* set parameters */
   
  wgtflag[0] = 0;    /* no weights */
  numflag    = 0;    /* C style */
  options[0] = 0;    /* default options */
   
  std::vector<idxtype> xadj;
  xadj.resize(NumMyRows() + 1);

  std::vector<idxtype> adjncy;
  adjncy.resize(NumMyNonzeros());
   
  int count = 0; 
  int count2 = 0; 
  xadj[0] = 0;
  
  for (int i = 0; i < NumMyRows() ; ++i) {

    xadj[count2+1] = xadj[count2]; /* nonzeros in row i-1 */

    ierr = IFPACKGraph->ExtractMyRowCopy(i, Length, NumIndices, &Indices[0]);
    IFPACK_CHK_ERR(ierr);

    for (int j = 0 ; j < NumIndices ; ++j) {
      int jj = Indices[j];
      if (jj != i) {
    adjncy[count++] = jj;
    xadj[count2+1]++;
      }
    }
    count2++;
  }

  std::vector<idxtype> NodesInSubgraph;
  NodesInSubgraph.resize(NumLocalParts_);

  // some cases can be handled separately
  
  int ok;

  if (NumLocalParts() == 1) {

    for (int i = 0 ; i < NumMyRows() ; ++i) 
      Partition_[i] = 0;
    
  } else if (NumLocalParts() == NumMyRows()) {

    for (int i = 0 ; i < NumMyRows() ; ++i) 
      Partition_[i] = i;
  
  } else {

    ok = 0;

    // sometimes METIS creates less partitions than specified.
    // ok will check this problem, and recall metis, asking
    // for NumLocalParts_/2 partitions
    while (ok == 0) {
      
      for (int i = 0 ; i < NumMyRows() ; ++i) 
    Partition_[i] = -1;
    
#ifdef HAVE_IFPACK_METIS
      int j = NumMyRows();
      if (NumLocalParts_ < 8) {

    int i = 1; /* optype in the METIS manual */
    numflag = 0;
    METIS_EstimateMemory(&j, &xadj[0], &adjncy[0], 
                 &numflag, &i, &nbytes );
    
    METIS_PartGraphRecursive(&j, &xadj[0], &adjncy[0],
                 NULL, NULL,
                 &wgtflag[0], &numflag, &NumLocalParts_, 
                 &options[0], &edgecut, &Partition_[0]);
      } else {

    numflag = 0;
    
    METIS_PartGraphKway (&j, &xadj[0], &adjncy[0], 
                 NULL, 
                 NULL, &wgtflag[0], &numflag, 
                 &NumLocalParts_, &options[0],
                 &edgecut, &Partition_[0]);
      }
#else
      numflag = numflag * 2; // avoid warning for unused variable
      if (Graph_->Comm().MyPID() == 0) {
    cerr << "METIS was not linked; now I put all" << endl;
    cerr << "the local nodes in the same partition." << endl;
      }
      for (int i = 0 ; i < NumMyRows() ; ++i) 
    Partition_[i] = 0;
      NumLocalParts_ = 1;
#endif
      
      ok = 1;
      
      for (int i = 0 ; i < NumLocalParts() ; ++i) 
    NodesInSubgraph[i] = 0;

      for (int i = 0 ; i < NumMyRows() ; ++i) {
    int j = Partition_[i];
    if ((j < 0) || (j>= NumLocalParts())) {
      ok = 0;
      break;
    } 
    else NodesInSubgraph[j]++;
      }
      
      for (int i = 0 ; i < NumLocalParts() ; ++i) {
    if( NodesInSubgraph[i] == 0 ) {
      ok = 0;
      break;
    }
      }
      
      if (ok == 0) {
    cerr << "Specified number of subgraphs ("
         << NumLocalParts_ << ") generates empty subgraphs." << endl;
    cerr << "Now I recall METIS with NumLocalParts_ = "
         << NumLocalParts_ / 2 << "..." << endl;
    NumLocalParts_ = NumLocalParts_/2;
      }
      
      if (NumLocalParts() == 0) {
    IFPACK_CHK_ERR(-10); // something went wrong
      }
      
      if (NumLocalParts() == 1) {
    for (int i = 0 ; i < NumMyRows() ; ++i) 
      Partition_[i] = 0;
    ok = 1;
      }
      
    } /* while( ok == 0 ) */
  
  } /* if( NumLocalParts_ == 1 ) */

  return(0);
}