Eigen::MetisOrdering< StorageIndex > Class Template Reference

#include <src/eigen/Eigen/src/MetisSupport/MetisSupport.h>

Collaboration diagram for Eigen::MetisOrdering< StorageIndex >:

Public Types
typedef PermutationMatrix< Dynamic, Dynamic, StorageIndex >	PermutationType
typedef Matrix< StorageIndex, Dynamic, 1 >	IndexVector

Public Member Functions
template<typename MatrixType >
void	get_symmetrized_graph (const MatrixType &A)
template<typename MatrixType >
void	operator() (const MatrixType &A, PermutationType &matperm)

Protected Attributes
IndexVector	m_indexPtr
IndexVector	m_innerIndices

Detailed Description

template<typename StorageIndex>
class Eigen::MetisOrdering< StorageIndex >

Get the fill-reducing ordering from the METIS package

If A is the original matrix and Ap is the permuted matrix, the fill-reducing permutation is defined as follows : Row (column) i of A is the matperm(i) row (column) of Ap. WARNING: As computed by METIS, this corresponds to the vector iperm (instead of perm)

Member Typedef Documentation

IndexVector

template<typename StorageIndex >

typedef Matrix<StorageIndex,Dynamic,1> Eigen::MetisOrdering< StorageIndex >::IndexVector

PermutationType

template<typename StorageIndex >

typedef PermutationMatrix<Dynamic,Dynamic,StorageIndex> Eigen::MetisOrdering< StorageIndex >::PermutationType

Member Function Documentation

get_symmetrized_graph()

template<typename StorageIndex >

template<typename MatrixType >

void Eigen::MetisOrdering< StorageIndex >::get_symmetrized_graph ( const MatrixType &  A )

inline

  {
    Index m = A.cols(); 
    eigen_assert((A.rows() == A.cols()) && "ONLY FOR SQUARED MATRICES");
    // Get the transpose of the input matrix 
    MatrixType At = A.transpose(); 
    // Get the number of nonzeros elements in each row/col of At+A
    Index TotNz = 0; 
    IndexVector visited(m); 
    visited.setConstant(-1); 
    for (StorageIndex j = 0; j < m; j++)
    {
      // Compute the union structure of of A(j,:) and At(j,:)
      visited(j) = j; // Do not include the diagonal element
      // Get the nonzeros in row/column j of A
      for (typename MatrixType::InnerIterator it(A, j); it; ++it)
      {
        Index idx = it.index(); // Get the row index (for column major) or column index (for row major)
        if (visited(idx) != j ) 
        {
          visited(idx) = j; 
          ++TotNz; 
        }
      }
      //Get the nonzeros in row/column j of At
      for (typename MatrixType::InnerIterator it(At, j); it; ++it)
      {
        Index idx = it.index(); 
        if(visited(idx) != j)
        {
          visited(idx) = j; 
          ++TotNz; 
        }
      }
    }
    // Reserve place for A + At
    m_indexPtr.resize(m+1);
    m_innerIndices.resize(TotNz); 
 
    // Now compute the real adjacency list of each column/row 
    visited.setConstant(-1); 
    StorageIndex CurNz = 0; 
    for (StorageIndex j = 0; j < m; j++)
    {
      m_indexPtr(j) = CurNz; 
      
      visited(j) = j; // Do not include the diagonal element
      // Add the pattern of row/column j of A to A+At
      for (typename MatrixType::InnerIterator it(A,j); it; ++it)
      {
        StorageIndex idx = it.index(); // Get the row index (for column major) or column index (for row major)
        if (visited(idx) != j ) 
        {
          visited(idx) = j; 
          m_innerIndices(CurNz) = idx; 
          CurNz++; 
        }
      }
      //Add the pattern of row/column j of At to A+At
      for (typename MatrixType::InnerIterator it(At, j); it; ++it)
      {
        StorageIndex idx = it.index(); 
        if(visited(idx) != j)
        {
          visited(idx) = j; 
          m_innerIndices(CurNz) = idx; 
          ++CurNz; 
        }
      }
    }
    m_indexPtr(m) = CurNz;    
  }

References eigen_assert, Eigen::MetisOrdering< StorageIndex >::m_indexPtr, Eigen::MetisOrdering< StorageIndex >::m_innerIndices, Eigen::PlainObjectBase< Derived >::resize(), and Eigen::PlainObjectBase< Derived >::setConstant().

Referenced by Eigen::MetisOrdering< StorageIndex >::operator()().

Here is the call graph for this function:

Here is the caller graph for this function:

operator()()

template<typename StorageIndex >

template<typename MatrixType >

void Eigen::MetisOrdering< StorageIndex >::operator() ( const MatrixType &  A, PermutationType &  matperm  )

inline

  {
     StorageIndex m = internal::convert_index<StorageIndex>(A.cols()); // must be StorageIndex, because it is passed by address to METIS
     IndexVector perm(m),iperm(m); 
    // First, symmetrize the matrix graph. 
     get_symmetrized_graph(A); 
     int output_error;
     
     // Call the fill-reducing routine from METIS 
     output_error = METIS_NodeND(&m, m_indexPtr.data(), m_innerIndices.data(), NULL, NULL, perm.data(), iperm.data());
     
    if(output_error != METIS_OK) 
    {
      //FIXME The ordering interface should define a class of possible errors 
     std::cerr << "ERROR WHILE CALLING THE METIS PACKAGE \n"; 
     return; 
    }
    
    // Get the fill-reducing permutation 
    //NOTE:  If Ap is the permuted matrix then perm and iperm vectors are defined as follows 
    // Row (column) i of Ap is the perm(i) row(column) of A, and row (column) i of A is the iperm(i) row(column) of Ap
    
     matperm.resize(m);
     for (int j = 0; j < m; j++)
       matperm.indices()(iperm(j)) = j;
   
  }

References Eigen::PlainObjectBase< Derived >::data(), Eigen::MetisOrdering< StorageIndex >::get_symmetrized_graph(), Eigen::PermutationMatrix< SizeAtCompileTime, MaxSizeAtCompileTime, _StorageIndex >::indices(), Eigen::MetisOrdering< StorageIndex >::m_indexPtr, Eigen::MetisOrdering< StorageIndex >::m_innerIndices, and Eigen::PermutationBase< Derived >::resize().

Here is the call graph for this function:

Member Data Documentation

m_indexPtr

template<typename StorageIndex >

IndexVector Eigen::MetisOrdering< StorageIndex >::m_indexPtr

protected

Referenced by Eigen::MetisOrdering< StorageIndex >::get_symmetrized_graph(), and Eigen::MetisOrdering< StorageIndex >::operator()().

m_innerIndices

template<typename StorageIndex >

IndexVector Eigen::MetisOrdering< StorageIndex >::m_innerIndices

protected

Referenced by Eigen::MetisOrdering< StorageIndex >::get_symmetrized_graph(), and Eigen::MetisOrdering< StorageIndex >::operator()().

---

The documentation for this class was generated from the following file:

• src/eigen/Eigen/src/MetisSupport/MetisSupport.h