Public Types | Protected Member Functions | Friends | List of all members
Eigen::internal::SparseLUImpl< Scalar, StorageIndex > Class Template Reference

#include <SparseLUImpl.h>

Public Types

typedef Ref< Matrix< StorageIndex, Dynamic, 1 > > BlockIndexVector
 
typedef Ref< Matrix< Scalar, Dynamic, 1 > > BlockScalarVector
 
typedef LU_GlobalLU_t< IndexVector, ScalarVectorGlobalLU_t
 
typedef Matrix< StorageIndex, Dynamic, 1 > IndexVector
 
typedef Map< ScalarMatrix, 0, OuterStride<> > MappedMatrixBlock
 
typedef SparseMatrix< Scalar, ColMajor, StorageIndex > MatrixType
 
typedef ScalarVector::RealScalar RealScalar
 
typedef Matrix< Scalar, Dynamic, Dynamic, ColMajorScalarMatrix
 
typedef Matrix< Scalar, Dynamic, 1 > ScalarVector
 

Protected Member Functions

Index column_bmod (const Index jcol, const Index nseg, BlockScalarVector dense, ScalarVector &tempv, BlockIndexVector segrep, BlockIndexVector repfnz, Index fpanelc, GlobalLU_t &glu)
 Performs numeric block updates (sup-col) in topological order. More...
 
Index column_dfs (const Index m, const Index jcol, IndexVector &perm_r, Index maxsuper, Index &nseg, BlockIndexVector lsub_col, IndexVector &segrep, BlockIndexVector repfnz, IndexVector &xprune, IndexVector &marker, IndexVector &parent, IndexVector &xplore, GlobalLU_t &glu)
 Performs a symbolic factorization on column jcol and decide the supernode boundary. More...
 
Index copy_to_ucol (const Index jcol, const Index nseg, IndexVector &segrep, BlockIndexVector repfnz, IndexVector &perm_r, BlockScalarVector dense, GlobalLU_t &glu)
 Performs numeric block updates (sup-col) in topological order. More...
 
void countnz (const Index n, Index &nnzL, Index &nnzU, GlobalLU_t &glu)
 Count Nonzero elements in the factors. More...
 
template<typename Traits >
void dfs_kernel (const StorageIndex jj, IndexVector &perm_r, Index &nseg, IndexVector &panel_lsub, IndexVector &segrep, Ref< IndexVector > repfnz_col, IndexVector &xprune, Ref< IndexVector > marker, IndexVector &parent, IndexVector &xplore, GlobalLU_t &glu, Index &nextl_col, Index krow, Traits &traits)
 
template<typename VectorType >
Index expand (VectorType &vec, Index &length, Index nbElts, Index keep_prev, Index &num_expansions)
 
void fixupL (const Index n, const IndexVector &perm_r, GlobalLU_t &glu)
 Fix up the data storage lsub for L-subscripts. More...
 
void heap_relax_snode (const Index n, IndexVector &et, const Index relax_columns, IndexVector &descendants, IndexVector &relax_end)
 Identify the initial relaxed supernodes. More...
 
Index memInit (Index m, Index n, Index annz, Index lwork, Index fillratio, Index panel_size, GlobalLU_t &glu)
 Allocate various working space for the numerical factorization phase. More...
 
template<typename VectorType >
Index memXpand (VectorType &vec, Index &maxlen, Index nbElts, MemType memtype, Index &num_expansions)
 Expand the existing storage. More...
 
void panel_bmod (const Index m, const Index w, const Index jcol, const Index nseg, ScalarVector &dense, ScalarVector &tempv, IndexVector &segrep, IndexVector &repfnz, GlobalLU_t &glu)
 Performs numeric block updates (sup-panel) in topological order. More...
 
void panel_dfs (const Index m, const Index w, const Index jcol, MatrixType &A, IndexVector &perm_r, Index &nseg, ScalarVector &dense, IndexVector &panel_lsub, IndexVector &segrep, IndexVector &repfnz, IndexVector &xprune, IndexVector &marker, IndexVector &parent, IndexVector &xplore, GlobalLU_t &glu)
 Performs a symbolic factorization on a panel of columns [jcol, jcol+w) More...
 
Index pivotL (const Index jcol, const RealScalar &diagpivotthresh, IndexVector &perm_r, IndexVector &iperm_c, Index &pivrow, GlobalLU_t &glu)
 Performs the numerical pivotin on the current column of L, and the CDIV operation. More...
 
void pruneL (const Index jcol, const IndexVector &perm_r, const Index pivrow, const Index nseg, const IndexVector &segrep, BlockIndexVector repfnz, IndexVector &xprune, GlobalLU_t &glu)
 Prunes the L-structure. More...
 
void relax_snode (const Index n, IndexVector &et, const Index relax_columns, IndexVector &descendants, IndexVector &relax_end)
 Identify the initial relaxed supernodes. More...
 
Index snode_bmod (const Index jcol, const Index fsupc, ScalarVector &dense, GlobalLU_t &glu)
 
Index snode_dfs (const Index jcol, const Index kcol, const MatrixType &mat, IndexVector &xprune, IndexVector &marker, GlobalLU_t &glu)
 

Friends

template<typename , typename >
struct column_dfs_traits
 

Detailed Description

template<typename Scalar, typename StorageIndex>
class Eigen::internal::SparseLUImpl< Scalar, StorageIndex >

Base class for sparseLU

Definition at line 20 of file SparseLUImpl.h.

Member Typedef Documentation

template<typename Scalar, typename StorageIndex>
typedef Ref<Matrix<StorageIndex,Dynamic,1> > Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::BlockIndexVector

Definition at line 29 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef Ref<Matrix<Scalar,Dynamic,1> > Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::BlockScalarVector

Definition at line 28 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef LU_GlobalLU_t<IndexVector, ScalarVector> Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::GlobalLU_t

Definition at line 30 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef Matrix<StorageIndex,Dynamic,1> Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::IndexVector

Definition at line 24 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef Map<ScalarMatrix, 0, OuterStride<> > Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::MappedMatrixBlock

Definition at line 26 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef SparseMatrix<Scalar,ColMajor,StorageIndex> Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::MatrixType

Definition at line 31 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef ScalarVector::RealScalar Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::RealScalar

Definition at line 27 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef Matrix<Scalar,Dynamic,Dynamic,ColMajor> Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::ScalarMatrix

Definition at line 25 of file SparseLUImpl.h.

template<typename Scalar, typename StorageIndex>
typedef Matrix<Scalar,Dynamic,1> Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::ScalarVector

Definition at line 23 of file SparseLUImpl.h.

Member Function Documentation

template<typename Scalar , typename StorageIndex >
Index SparseLUImpl< Scalar, StorageIndex >::column_bmod ( const Index  jcol,
const Index  nseg,
BlockScalarVector  dense,
ScalarVector tempv,
BlockIndexVector  segrep,
BlockIndexVector  repfnz,
Index  fpanelc,
GlobalLU_t glu 
)
protected

Performs numeric block updates (sup-col) in topological order.

Parameters
jcolcurrent column to update
nsegNumber of segments in the U part
denseStore the full representation of the column
tempvworking array
segrepsegment representative ...
repfnz??? First nonzero column in each row ??? ...
fpanelcFirst column in the current panel
gluGlobal LU data.
Returns
0 - successful return > 0 - number of bytes allocated when run out of space

Definition at line 53 of file SparseLU_column_bmod.h.

template<typename Scalar , typename StorageIndex >
Index SparseLUImpl< Scalar, StorageIndex >::column_dfs ( const Index  m,
const Index  jcol,
IndexVector perm_r,
Index  maxsuper,
Index nseg,
BlockIndexVector  lsub_col,
IndexVector segrep,
BlockIndexVector  repfnz,
IndexVector xprune,
IndexVector marker,
IndexVector parent,
IndexVector xplore,
GlobalLU_t glu 
)
protected

Performs a symbolic factorization on column jcol and decide the supernode boundary.

A supernode representative is the last column of a supernode. The nonzeros in U[*,j] are segments that end at supernodes representatives. The routine returns a list of the supernodal representatives in topological order of the dfs that generates them. The location of the first nonzero in each supernodal segment (supernodal entry location) is also returned.

Parameters
mnumber of rows in the matrix
jcolCurrent column
perm_rRow permutation
maxsuperMaximum number of column allowed in a supernode
[in,out]nsegNumber of segments in current U[*,j] - new segments appended
lsub_coldefines the rhs vector to start the dfs
[in,out]segrepSegment representatives - new segments appended
repfnzFirst nonzero location in each row
xprune
markermarker[i] == jj, if i was visited during dfs of current column jj;
parent
xploreworking array
gluglobal LU data
Returns
0 success > 0 number of bytes allocated when run out of space

Definition at line 93 of file SparseLU_column_dfs.h.

template<typename Scalar , typename StorageIndex >
Index SparseLUImpl< Scalar, StorageIndex >::copy_to_ucol ( const Index  jcol,
const Index  nseg,
IndexVector segrep,
BlockIndexVector  repfnz,
IndexVector perm_r,
BlockScalarVector  dense,
GlobalLU_t glu 
)
protected

Performs numeric block updates (sup-col) in topological order.

Parameters
jcolcurrent column to update
nsegNumber of segments in the U part
segrepsegment representative ...
repfnzFirst nonzero column in each row ...
perm_rRow permutation
denseStore the full representation of the column
gluGlobal LU data.
Returns
0 - successful return > 0 - number of bytes allocated when run out of space

Definition at line 50 of file SparseLU_copy_to_ucol.h.

template<typename Scalar , typename StorageIndex >
void SparseLUImpl< Scalar, StorageIndex >::countnz ( const Index  n,
Index nnzL,
Index nnzU,
GlobalLU_t glu 
)
protected

Count Nonzero elements in the factors.

Definition at line 21 of file SparseLU_Utils.h.

template<typename Scalar , typename StorageIndex>
template<typename Traits >
void SparseLUImpl< Scalar, StorageIndex >::dfs_kernel ( const StorageIndex  jj,
IndexVector perm_r,
Index nseg,
IndexVector panel_lsub,
IndexVector segrep,
Ref< IndexVector repfnz_col,
IndexVector xprune,
Ref< IndexVector marker,
IndexVector parent,
IndexVector xplore,
GlobalLU_t glu,
Index nextl_col,
Index  krow,
Traits &  traits 
)
protected

Definition at line 62 of file SparseLU_panel_dfs.h.

template<typename Scalar , typename StorageIndex >
template<typename VectorType >
Index SparseLUImpl< Scalar, StorageIndex >::expand ( VectorType vec,
Index length,
Index  nbElts,
Index  keep_prev,
Index num_expansions 
)
protected

Expand the existing storage to accomodate more fill-ins

Parameters
vecValid pointer to the vector to allocate or expand
[in,out]lengthAt input, contain the current length of the vector that is to be increased. At output, length of the newly allocated vector
[in]nbEltsCurrent number of elements in the factors
keep_prev1: use length and do not expand the vector; 0: compute new_len and expand
[in,out]num_expansionsNumber of times the memory has been expanded

Definition at line 63 of file SparseLU_Memory.h.

template<typename Scalar , typename StorageIndex >
void SparseLUImpl< Scalar, StorageIndex >::fixupL ( const Index  n,
const IndexVector perm_r,
GlobalLU_t glu 
)
protected

Fix up the data storage lsub for L-subscripts.

It removes the subscripts sets for structural pruning, and applies permutation to the remaining subscripts

Definition at line 52 of file SparseLU_Utils.h.

template<typename Scalar , typename StorageIndex >
void SparseLUImpl< Scalar, StorageIndex >::heap_relax_snode ( const Index  n,
IndexVector et,
const Index  relax_columns,
IndexVector descendants,
IndexVector relax_end 
)
protected

Identify the initial relaxed supernodes.

This routine applied to a symmetric elimination tree. It assumes that the matrix has been reordered according to the postorder of the etree

Parameters
nThe number of columns
etelimination tree
relax_columnsMaximum number of columns allowed in a relaxed snode
descendantsNumber of descendants of each node in the etree
relax_endlast column in a supernode

Definition at line 46 of file SparseLU_heap_relax_snode.h.

template<typename Scalar , typename StorageIndex >
Index SparseLUImpl< Scalar, StorageIndex >::memInit ( Index  m,
Index  n,
Index  annz,
Index  lwork,
Index  fillratio,
Index  panel_size,
GlobalLU_t glu 
)
protected

Allocate various working space for the numerical factorization phase.

Parameters
mnumber of rows of the input matrix
nnumber of columns
annznumber of initial nonzeros in the matrix
lworkif lwork=-1, this routine returns an estimated size of the required memory
glupersistent data to facilitate multiple factors : will be deleted later ??
fillratioestimated ratio of fill in the factors
panel_sizeSize of a panel
Returns
an estimated size of the required memory if lwork = -1; otherwise, return the size of actually allocated memory when allocation failed, and 0 on success
Note
Unlike SuperLU, this routine does not support successive factorization with the same pattern and the same row permutation

Definition at line 151 of file SparseLU_Memory.h.

template<typename Scalar , typename StorageIndex >
template<typename VectorType >
Index SparseLUImpl< Scalar, StorageIndex >::memXpand ( VectorType vec,
Index maxlen,
Index  nbElts,
MemType  memtype,
Index num_expansions 
)
protected

Expand the existing storage.

Parameters
vecvector to expand
[in,out]maxlenOn input, previous size of vec (Number of elements to copy ). on output, new size
nbEltscurrent number of elements in the vector.
memtypeType of the element to expand
num_expansionsNumber of expansions
Returns
0 on success, > 0 size of the memory allocated so far

Definition at line 209 of file SparseLU_Memory.h.

template<typename Scalar , typename StorageIndex >
void SparseLUImpl< Scalar, StorageIndex >::panel_bmod ( const Index  m,
const Index  w,
const Index  jcol,
const Index  nseg,
ScalarVector dense,
ScalarVector tempv,
IndexVector segrep,
IndexVector repfnz,
GlobalLU_t glu 
)
protected

Performs numeric block updates (sup-panel) in topological order.

Before entering this routine, the original nonzeros in the panel were already copied i nto the spa[m,w]

Parameters
mnumber of rows in the matrix
wPanel size
jcolStarting column of the panel
nsegNumber of segments in the U part
denseStore the full representation of the panel
tempvworking array
segrepsegment representative... first row in the segment
repfnzFirst nonzero rows
gluGlobal LU data.

Definition at line 56 of file SparseLU_panel_bmod.h.

template<typename Scalar , typename StorageIndex >
void SparseLUImpl< Scalar, StorageIndex >::panel_dfs ( const Index  m,
const Index  w,
const Index  jcol,
MatrixType A,
IndexVector perm_r,
Index nseg,
ScalarVector dense,
IndexVector panel_lsub,
IndexVector segrep,
IndexVector repfnz,
IndexVector xprune,
IndexVector marker,
IndexVector parent,
IndexVector xplore,
GlobalLU_t glu 
)
protected

Performs a symbolic factorization on a panel of columns [jcol, jcol+w)

A supernode representative is the last column of a supernode. The nonzeros in U[*,j] are segments that end at supernodes representatives

The routine returns a list of the supernodal representatives in topological order of the dfs that generates them. This list is a superset of the topological order of each individual column within the panel. The location of the first nonzero in each supernodal segment (supernodal entry location) is also returned. Each column has a separate list for this purpose.

Two markers arrays are used for dfs : marker[i] == jj, if i was visited during dfs of current column jj; marker1[i] >= jcol, if i was visited by earlier columns in this panel;

Parameters
[in]mnumber of rows in the matrix
[in]wPanel size
[in]jcolStarting column of the panel
[in]AInput matrix in column-major storage
[in]perm_rRow permutation
[out]nsegNumber of U segments
[out]denseAccumulate the column vectors of the panel
[out]panel_lsubSubscripts of the row in the panel
[out]segrepSegment representative i.e first nonzero row of each segment
[out]repfnzFirst nonzero location in each row
[out]xpruneThe pruned elimination tree
[out]markerwork vector
parentThe elimination tree
xplorework vector
gluThe global data structure

Definition at line 219 of file SparseLU_panel_dfs.h.

template<typename Scalar , typename StorageIndex >
Index SparseLUImpl< Scalar, StorageIndex >::pivotL ( const Index  jcol,
const RealScalar diagpivotthresh,
IndexVector perm_r,
IndexVector iperm_c,
Index pivrow,
GlobalLU_t glu 
)
protected

Performs the numerical pivotin on the current column of L, and the CDIV operation.

Pivot policy : (1) Compute thresh = u * max_(i>=j) abs(A_ij); (2) IF user specifies pivot row k and abs(A_kj) >= thresh THEN pivot row = k; ELSE IF abs(A_jj) >= thresh THEN pivot row = j; ELSE pivot row = m;

Note: If you absolutely want to use a given pivot order, then set u=0.0.

Parameters
jcolThe current column of L
diagpivotthreshdiagonal pivoting threshold
[in,out]perm_rRow permutation (threshold pivoting)
[in]iperm_ccolumn permutation - used to finf diagonal of Pc*A*Pc'
[out]pivrowThe pivot row
gluGlobal LU data
Returns
0 if success, i > 0 if U(i,i) is exactly zero

Definition at line 60 of file SparseLU_pivotL.h.

template<typename Scalar , typename StorageIndex >
void SparseLUImpl< Scalar, StorageIndex >::pruneL ( const Index  jcol,
const IndexVector perm_r,
const Index  pivrow,
const Index  nseg,
const IndexVector segrep,
BlockIndexVector  repfnz,
IndexVector xprune,
GlobalLU_t glu 
)
protected

Prunes the L-structure.

It prunes the L-structure of supernodes whose L-structure contains the current pivot row "pivrow"

Parameters
jcolThe current column of L
[in]perm_rRow permutation
[out]pivrowThe pivot row
nsegNumber of segments
segrep
repfnz
[out]xprune
gluGlobal LU data

Definition at line 53 of file SparseLU_pruneL.h.

template<typename Scalar , typename StorageIndex >
void SparseLUImpl< Scalar, StorageIndex >::relax_snode ( const Index  n,
IndexVector et,
const Index  relax_columns,
IndexVector descendants,
IndexVector relax_end 
)
protected

Identify the initial relaxed supernodes.

This routine is applied to a column elimination tree. It assumes that the matrix has been reordered according to the postorder of the etree

Parameters
nthe number of columns
etelimination tree
relax_columnsMaximum number of columns allowed in a relaxed snode
descendantsNumber of descendants of each node in the etree
relax_endlast column in a supernode

Definition at line 47 of file SparseLU_relax_snode.h.

template<typename Scalar, typename StorageIndex>
Index Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::snode_bmod ( const Index  jcol,
const Index  fsupc,
ScalarVector dense,
GlobalLU_t glu 
)
protected
template<typename Scalar, typename StorageIndex>
Index Eigen::internal::SparseLUImpl< Scalar, StorageIndex >::snode_dfs ( const Index  jcol,
const Index  kcol,
const MatrixType mat,
IndexVector xprune,
IndexVector marker,
GlobalLU_t glu 
)
protected

Friends And Related Function Documentation

template<typename Scalar, typename StorageIndex>
template<typename , typename >
friend struct column_dfs_traits
friend

Definition at line 60 of file SparseLUImpl.h.


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


gtsam
Author(s):
autogenerated on Sat May 8 2021 02:56:55