Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits > Class Template Reference

The RandomSetter is a wrapper object allowing to set/update a sparse matrix with random access. More...

Classes
struct	ScalarWrapper

Public Member Functions
Index	nonZeros () const
Scalar &	operator() (Index row, Index col)
	RandomSetter (SparseMatrixType &target)
	~RandomSetter ()

Protected Attributes
HashMapType *	m_hashmaps
unsigned char	m_keyBitsOffset
Index	m_outerPackets
SparseMatrixType *	mp_target

Private Types
enum	{   SwapStorage ,   TargetRowMajor ,   SetterRowMajor }
typedef MapTraits< ScalarWrapper >::Type	HashMapType
typedef MapTraits< ScalarWrapper >::KeyType	KeyType
typedef SparseMatrixType::Scalar	Scalar
typedef SparseMatrixType::StorageIndex	StorageIndex

Static Private Attributes
static constexpr int	OuterPacketMask

Detailed Description

template<typename SparseMatrixType, template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>
class Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >

The RandomSetter is a wrapper object allowing to set/update a sparse matrix with random access.

Template Parameters

SparseMatrixType	the type of the sparse matrix we are updating
MapTraits	a traits class representing the map implementation used for the temporary sparse storage. Its default value depends on the system.
OuterPacketBits	defines the number of rows (or columns) manage by a single map object as a power of two exponent.

This class temporarily represents a sparse matrix object using a generic map implementation allowing for efficient random access. The conversion from the compressed representation to a hash_map object is performed in the RandomSetter constructor, while the sparse matrix is updated back at destruction time. This strategy suggest the use of nested blocks as in this example:

SparseMatrix<double> m(rows,cols);
{
  RandomSetter<SparseMatrix<double> > w(m);
  // don't use m but w instead with read/write random access to the coefficients:
  for(;;)
    w(rand(),rand()) = rand;
}
// when w is deleted, the data are copied back to m
// and m is ready to use.

Since hash_map objects are not fully sorted, representing a full matrix as a single hash_map would involve a big and costly sort to update the compressed matrix back. To overcome this issue, a RandomSetter use multiple hash_map, each representing 2^OuterPacketBits columns or rows according to the storage order. To reach optimal performance, this value should be adjusted according to the average number of nonzeros per rows/columns.

The possible values for the template parameter MapTraits are:

• StdMapTraits: corresponds to std::map. (does not perform very well)
• StdUnorderedMapTraits: corresponds to std::unordered_map
• GoogleDenseHashMapTraits: corresponds to google::dense_hash_map (best efficiency, reasonable memory consumption)
• GoogleSparseHashMapTraits: corresponds to google::sparse_hash_map (best memory consumption, relatively good performance)

The default map implementation depends on the availability, and the preferred order is: GoogleSparseHashMapTraits, StdUnorderedMapTraits, and finally StdMapTraits.

For performance and memory consumption reasons it is highly recommended to use one of Google's hash_map implementations. To enable the support for them, you must define EIGEN_GOOGLEHASH_SUPPORT. This will include both <google/dense_hash_map> and <google/sparse_hash_map> for you.

See also

https://github.com/sparsehash/sparsehash

Definition at line 162 of file RandomSetter.h.

Member Typedef Documentation

HashMapType

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

typedef MapTraits<ScalarWrapper>::Type Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::HashMapType

private

Definition at line 173 of file RandomSetter.h.

KeyType

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

typedef MapTraits<ScalarWrapper>::KeyType Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::KeyType

private

Definition at line 172 of file RandomSetter.h.

Scalar

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

typedef SparseMatrixType::Scalar Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::Scalar

private

Definition at line 164 of file RandomSetter.h.

StorageIndex

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

typedef SparseMatrixType::StorageIndex Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::StorageIndex

private

Definition at line 165 of file RandomSetter.h.

Member Enumeration Documentation

anonymous enum

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

anonymous enum

private

Enumerator
SwapStorage
TargetRowMajor
SetterRowMajor

Definition at line 175 of file RandomSetter.h.

         {
      SwapStorage = 1 - MapTraits<ScalarWrapper>::IsSorted,
      TargetRowMajor = (SparseMatrixType::Flags & RowMajorBit) ? 1 : 0,
      SetterRowMajor = SwapStorage ? 1-TargetRowMajor : TargetRowMajor
    };

Constructor & Destructor Documentation

RandomSetter()

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::RandomSetter ( SparseMatrixType &  target )

inline

Constructs a random setter object from the sparse matrix target

Note that the initial value of target are imported. If you want to re-set a sparse matrix from scratch, then you must set it to zero first using the setZero() function.

Definition at line 189 of file RandomSetter.h.

      : mp_target(&target)
    {
      const Index outerSize = SwapStorage ? target.innerSize() : target.outerSize();
      const Index innerSize = SwapStorage ? target.outerSize() : target.innerSize();
      m_outerPackets = outerSize >> OuterPacketBits;
      if (outerSize&OuterPacketMask)
        m_outerPackets += 1;
      m_hashmaps = new HashMapType[m_outerPackets];
      // compute number of bits needed to store inner indices
      Index aux = innerSize - 1;
      m_keyBitsOffset = 0;
      while (aux)
      {
        ++m_keyBitsOffset;
        aux = aux >> 1;
      }
      KeyType ik = (1<<(OuterPacketBits+m_keyBitsOffset));
      for (Index k=0; k<m_outerPackets; ++k)
        MapTraits<ScalarWrapper>::setInvalidKey(m_hashmaps[k],ik);
 
      // insert current coeffs
      for (Index j=0; j<mp_target->outerSize(); ++j)
        for (typename SparseMatrixType::InnerIterator it(*mp_target,j); it; ++it)
          (*this)(TargetRowMajor?j:it.index(), TargetRowMajor?it.index():j) = it.value();
    }

~RandomSetter()

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::~RandomSetter ( )

inline

Destructor updating back the sparse matrix target

Definition at line 217 of file RandomSetter.h.

    {
      KeyType keyBitsMask = (1<<m_keyBitsOffset)-1;
      if (!SwapStorage) // also means the map is sorted
      {
        mp_target->setZero();
        mp_target->makeCompressed();
        mp_target->reserve(nonZeros());
        Index prevOuter = -1;
        for (Index k=0; k<m_outerPackets; ++k)
        {
          const Index outerOffset = (1<<OuterPacketBits) * k;
          typename HashMapType::iterator end = m_hashmaps[k].end();
          for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
          {
            const Index outer = (it->first >> m_keyBitsOffset) + outerOffset;
            const Index inner = it->first & keyBitsMask;
            if (prevOuter!=outer)
            {
              for (Index j=prevOuter+1;j<=outer;++j)
                mp_target->startVec(j);
              prevOuter = outer;
            }
            mp_target->insertBackByOuterInner(outer, inner) = it->second.value;
          }
        }
        mp_target->finalize();
      }
      else
      {
        VectorXi positions(mp_target->outerSize());
        positions.setZero();
        // pass 1
        for (Index k=0; k<m_outerPackets; ++k)
        {
          typename HashMapType::iterator end = m_hashmaps[k].end();
          for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
          {
            const Index outer = it->first & keyBitsMask;
            ++positions[outer];
          }
        }
        // prefix sum
        StorageIndex count = 0;
        for (Index j=0; j<mp_target->outerSize(); ++j)
        {
          StorageIndex tmp = positions[j];
          mp_target->outerIndexPtr()[j] = count;
          positions[j] = count;
          count += tmp;
        }
        mp_target->makeCompressed();
        mp_target->outerIndexPtr()[mp_target->outerSize()] = count;
        mp_target->resizeNonZeros(count);
        // pass 2
        for (Index k=0; k<m_outerPackets; ++k)
        {
          const Index outerOffset = (1<<OuterPacketBits) * k;
          typename HashMapType::iterator end = m_hashmaps[k].end();
          for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
          {
            const Index inner = (it->first >> m_keyBitsOffset) + outerOffset;
            const Index outer = it->first & keyBitsMask;
            // sorted insertion
            // Note that we have to deal with at most 2^OuterPacketBits unsorted coefficients,
            // moreover those 2^OuterPacketBits coeffs are likely to be sparse, an so only a
            // small fraction of them have to be sorted, whence the following simple procedure:
            Index posStart = mp_target->outerIndexPtr()[outer];
            Index i = (positions[outer]++) - 1;
            while ( (i >= posStart) && (mp_target->innerIndexPtr()[i] > inner) )
            {
              mp_target->valuePtr()[i+1] = mp_target->valuePtr()[i];
              mp_target->innerIndexPtr()[i+1] = mp_target->innerIndexPtr()[i];
              --i;
            }
            mp_target->innerIndexPtr()[i+1] = internal::convert_index<StorageIndex>(inner);
            mp_target->valuePtr()[i+1] = it->second.value;
          }
        }
      }
      delete[] m_hashmaps;
    }

Member Function Documentation

nonZeros()

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

Index Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::nonZeros ( ) const

inline

Returns

the number of non zero coefficients

Note

According to the underlying map/hash_map implementation, this function might be quite expensive.

Definition at line 316 of file RandomSetter.h.

    {
      Index nz = 0;
      for (Index k=0; k<m_outerPackets; ++k)
        nz += static_cast<Index>(m_hashmaps[k].size());
      return nz;
    }

operator()()

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

Scalar& Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::operator() ( Index  row, Index  col  )

inline

Returns

a reference to the coefficient at given coordinates row, col

Definition at line 301 of file RandomSetter.h.

    {
      const Index outer = SetterRowMajor ? row : col;
      const Index inner = SetterRowMajor ? col : row;
      const Index outerMajor = outer >> OuterPacketBits; // index of the packet/map
      const Index outerMinor = outer & OuterPacketMask;  // index of the inner vector in the packet
      const KeyType key = internal::convert_index<KeyType>((outerMinor<<m_keyBitsOffset) | inner);
      return m_hashmaps[outerMajor][key].value;
    }

Member Data Documentation

m_hashmaps

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

HashMapType* Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::m_hashmaps

protected

Definition at line 327 of file RandomSetter.h.

m_keyBitsOffset

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

unsigned char Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::m_keyBitsOffset

protected

Definition at line 330 of file RandomSetter.h.

m_outerPackets

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

Index Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::m_outerPackets

protected

Definition at line 329 of file RandomSetter.h.

mp_target

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

SparseMatrixType* Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::mp_target

protected

Definition at line 328 of file RandomSetter.h.

OuterPacketMask

template<typename SparseMatrixType , template< typename T > class MapTraits = StdUnorderedMapTraits, int OuterPacketBits = 6>

constexpr int Eigen::RandomSetter< SparseMatrixType, MapTraits, OuterPacketBits >::OuterPacketMask

staticconstexprprivate

Definition at line 174 of file RandomSetter.h.

---

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

• RandomSetter.h