Eigen::internal::simpl_chol_helper< Scalar, StorageIndex > Struct Template Reference

#include <SimplicialCholesky_impl.h>

Classes
struct	DisjointSet
struct	Stack

Public Types
using	CholMatrixType = SparseMatrix< Scalar, ColMajor, StorageIndex >
using	InnerIterator = typename CholMatrixType::InnerIterator
using	VectorI = Matrix< StorageIndex, Dynamic, 1 >

Static Public Member Functions
static void	calc_hadj_outer (const StorageIndex size, const CholMatrixType &ap, StorageIndex *outerIndex)
static void	calc_hadj_inner (const StorageIndex size, const CholMatrixType &ap, const StorageIndex *outerIndex, StorageIndex *innerIndex, StorageIndex *tmp)
static void	calc_etree (const StorageIndex size, const CholMatrixType &ap, StorageIndex *parent, StorageIndex *tmp)
static void	calc_lineage (const StorageIndex size, const StorageIndex *parent, StorageIndex *firstChild, StorageIndex *firstSibling)
static void	calc_post (const StorageIndex size, const StorageIndex *parent, StorageIndex *firstChild, const StorageIndex *firstSibling, StorageIndex *post, StorageIndex *dfs)
static void	calc_colcount (const StorageIndex size, const StorageIndex *hadjOuter, const StorageIndex *hadjInner, const StorageIndex *parent, StorageIndex *prevLeaf, StorageIndex *tmp, const StorageIndex *post, StorageIndex *nonZerosPerCol, bool doLDLT)
static void	init_matrix (const StorageIndex size, const StorageIndex *nonZerosPerCol, CholMatrixType &L)
static void	run (const StorageIndex size, const CholMatrixType &ap, CholMatrixType &L, VectorI &parent, VectorI &workSpace, bool doLDLT)

Static Public Attributes
static constexpr StorageIndex	kEmpty = -1

Member Typedef Documentation

CholMatrixType

template<typename Scalar , typename StorageIndex >

using Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::CholMatrixType = SparseMatrix<Scalar, ColMajor, StorageIndex>

InnerIterator

template<typename Scalar , typename StorageIndex >

using Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::InnerIterator = typename CholMatrixType::InnerIterator

VectorI

template<typename Scalar , typename StorageIndex >

using Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::VectorI = Matrix<StorageIndex, Dynamic, 1>

Member Function Documentation

calc_colcount()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_colcount ( const StorageIndex  size, const StorageIndex *  hadjOuter, const StorageIndex *  hadjInner, const StorageIndex *  parent, StorageIndex *  prevLeaf, StorageIndex *  tmp, const StorageIndex *  post, StorageIndex *  nonZerosPerCol, bool  doLDLT  )

inlinestatic

                                                                                                 {
    // initialize nonZerosPerCol with 1 for leaves, 0 for non-leaves
    std::fill_n(nonZerosPerCol, size, 1);
    for (StorageIndex j = 0; j < size; j++) {
      StorageIndex p = parent[j];
      // p is not a leaf
      if (p != kEmpty) nonZerosPerCol[p] = 0;
    }
 
    DisjointSet parentSet(tmp, size);
    // prevLeaf is already initialized
    eigen_assert(std::all_of(prevLeaf, prevLeaf + size, [](StorageIndex a) { return a == kEmpty; }));
 
    for (StorageIndex j_ = 0; j_ < size; j_++) {
      StorageIndex j = post[j_];
      nonZerosPerCol[j] += hadjOuter[j + 1] - hadjOuter[j];
      for (StorageIndex k = hadjOuter[j]; k < hadjOuter[j + 1]; k++) {
        StorageIndex i = hadjInner[k];
        eigen_assert(i > j);
        StorageIndex prev = prevLeaf[i];
        if (prev != kEmpty) {
          StorageIndex q = parentSet.find(prev);
          parentSet.compress(prev, q);
          nonZerosPerCol[q]--;
        }
        prevLeaf[i] = j;
      }
      StorageIndex p = parent[j];
      if (p != kEmpty) parentSet.compress(j, p);
    }
 
    for (StorageIndex j = 0; j < size; j++) {
      StorageIndex p = parent[j];
      if (p != kEmpty) nonZerosPerCol[p] += nonZerosPerCol[j] - 1;
      if (doLDLT) nonZerosPerCol[j]--;
    }
  }

References j, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::kEmpty, p, and size.

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run().

calc_etree()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_etree ( const StorageIndex  size, const CholMatrixType &  ap, StorageIndex *  parent, StorageIndex *  tmp  )

inlinestatic

                                                                                                                     {
    std::fill_n(parent, size, kEmpty);
 
    DisjointSet ancestor(tmp, size);
 
    for (StorageIndex j = 1; j < size; j++) {
      for (InnerIterator it(ap, j); it; ++it) {
        StorageIndex i = it.index();
        if (i < j) {
          StorageIndex r = ancestor.find(i);
          if (r != j) parent[r] = j;
          ancestor.compress(i, j);
        }
      }
    }
  }

References ap, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::DisjointSet::compress(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::DisjointSet::find(), i, j, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::kEmpty, UniformPSDSelfTest::r, size, and tmp.

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run().

calc_hadj_inner()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_hadj_inner ( const StorageIndex  size, const CholMatrixType &  ap, const StorageIndex *  outerIndex, StorageIndex *  innerIndex, StorageIndex *  tmp  )

inlinestatic

                                                                           {
    std::fill_n(tmp, size, 0);
 
    for (StorageIndex j = 1; j < size; j++) {
      for (InnerIterator it(ap, j); it; ++it) {
        StorageIndex i = it.index();
        if (i < j) {
          StorageIndex b = outerIndex[i] + tmp[i];
          innerIndex[b] = j;
          tmp[i]++;
        }
      }
    }
  }

References ap, b, i, j, size, and tmp.

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run().

calc_hadj_outer()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_hadj_outer ( const StorageIndex  size, const CholMatrixType &  ap, StorageIndex *  outerIndex  )

inlinestatic

                                                                                                           {
    for (StorageIndex j = 1; j < size; j++) {
      for (InnerIterator it(ap, j); it; ++it) {
        StorageIndex i = it.index();
        if (i < j) outerIndex[i + 1]++;
      }
    }
    std::partial_sum(outerIndex, outerIndex + size + 1, outerIndex);
  }

References ap, i, j, and size.

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run().

calc_lineage()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_lineage ( const StorageIndex  size, const StorageIndex *  parent, StorageIndex *  firstChild, StorageIndex *  firstSibling  )

inlinestatic

                                                       {
    std::fill_n(firstChild, size, kEmpty);
    std::fill_n(firstSibling, size, kEmpty);
 
    for (StorageIndex j = 0; j < size; j++) {
      StorageIndex p = parent[j];
      if (p == kEmpty) continue;
      StorageIndex c = firstChild[p];
      if (c == kEmpty)
        firstChild[p] = j;
      else {
        while (firstSibling[c] != kEmpty) c = firstSibling[c];
        firstSibling[c] = j;
      }
    }
  }

References calibrate::c, j, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::kEmpty, p, and size.

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run().

calc_post()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_post ( const StorageIndex  size, const StorageIndex *  parent, StorageIndex *  firstChild, const StorageIndex *  firstSibling, StorageIndex *  post, StorageIndex *  dfs  )

inlinestatic

                                                                                                 {
    Stack post_stack(post, 0, size);
    for (StorageIndex j = 0; j < size; j++) {
      if (parent[j] != kEmpty) continue;
      // Begin at a root
      Stack dfs_stack(dfs, 0, size);
      dfs_stack.push(j);
      while (!dfs_stack.empty()) {
        StorageIndex i = dfs_stack.back();
        StorageIndex c = firstChild[i];
        if (c == kEmpty) {
          post_stack.push(i);
          dfs_stack.pop();
        } else {
          dfs_stack.push(c);
          // Remove the path from `i` to `c` for future traversals.
          firstChild[i] = firstSibling[c];
        }
      }
    }
    eigen_assert(post_stack.size() == size);
    eigen_assert(std::all_of(firstChild, firstChild + size, [](StorageIndex a) { return a == kEmpty; }));
  }

References a, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::Stack::back(), calibrate::c, MortaringHelpers::dfs(), eigen_assert, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::Stack::empty(), i, j, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::kEmpty, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::Stack::pop(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::Stack::push(), size, and Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::Stack::size().

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run().

init_matrix()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::init_matrix ( const StorageIndex  size, const StorageIndex *  nonZerosPerCol, CholMatrixType &  L  )

inlinestatic

                                                                                                          {
    eigen_assert(L.outerIndexPtr()[0] == 0);
    std::partial_sum(nonZerosPerCol, nonZerosPerCol + size, L.outerIndexPtr() + 1);
    L.resizeNonZeros(L.outerIndexPtr()[size]);
  }

References eigen_assert, L, and size.

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run().

run()

template<typename Scalar , typename StorageIndex >

static void Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::run ( const StorageIndex  size, const CholMatrixType &  ap, CholMatrixType &  L, VectorI &  parent, VectorI &  workSpace, bool  doLDLT  )

inlinestatic

                                                   {
    parent.resize(size);
    workSpace.resize(4 * size);
    L.resize(size, size);
 
    StorageIndex* tmp1 = workSpace.data();
    StorageIndex* tmp2 = workSpace.data() + size;
    StorageIndex* tmp3 = workSpace.data() + 2 * size;
    StorageIndex* tmp4 = workSpace.data() + 3 * size;
 
    // Borrow L's outer index array for the higher adjacency pattern.
    StorageIndex* hadj_outer = L.outerIndexPtr();
    calc_hadj_outer(size, ap, hadj_outer);
    // Request additional temporary storage for the inner indices of the higher adjacency pattern.
    ei_declare_aligned_stack_constructed_variable(StorageIndex, hadj_inner, hadj_outer[size], nullptr);
    calc_hadj_inner(size, ap, hadj_outer, hadj_inner, tmp1);
 
    calc_etree(size, ap, parent.data(), tmp1);
    calc_lineage(size, parent.data(), tmp1, tmp2);
    calc_post(size, parent.data(), tmp1, tmp2, tmp3, tmp4);
    calc_colcount(size, hadj_outer, hadj_inner, parent.data(), tmp1, tmp2, tmp3, tmp4, doLDLT);
    init_matrix(size, tmp4, L);
  }

References ap, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_colcount(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_etree(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_hadj_inner(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_hadj_outer(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_lineage(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_post(), Eigen::PlainObjectBase< Derived >::data(), ei_declare_aligned_stack_constructed_variable, Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::init_matrix(), L, Eigen::PlainObjectBase< Derived >::resize(), and size.

Member Data Documentation

kEmpty

template<typename Scalar , typename StorageIndex >

constexpr StorageIndex Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::kEmpty = -1

staticconstexpr

Referenced by Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_colcount(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_etree(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_lineage(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::calc_post(), Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::DisjointSet::compress(), and Eigen::internal::simpl_chol_helper< Scalar, StorageIndex >::DisjointSet::find().

---

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

• SimplicialCholesky_impl.h