PaStiX Handbook  6.2.1
Elimination tree structure

Data Structures

struct  etree_node_s
 Node of the elimination tree. More...
 
struct  etree_s
 Elimination tree. More...
 

Typedefs

typedef struct etree_node_s eTreeNode_t
 Node of the elimination tree.
 
typedef struct etree_s EliminTree
 Elimination tree.
 

Functions

static pastix_int_t compress_getNodeNbr (const EliminTree *etree, const Cand *candtab, pastix_int_t rootnum)
 Compute the number of nodes in the compressed tree. The compression is based on identical candidates for computations. More...
 
static void compress_setSonsNbr (const EliminTree *etree, const Cand *candtab, pastix_int_t rootnum, EliminTree *ctree, Cand *ccand, pastix_int_t fathnum, pastix_int_t *cnodeidx, pastix_int_t *tmp)
 Compress a subtree. The compression is based on identical candidates for computations. More...
 
void candGenDot (const EliminTree *etree, const Cand *candtab, FILE *stream)
 Print the elimination tree in a dot file. More...
 
static void candGenDotLevelSub (const EliminTree *etree, const Cand *candtab, FILE *stream, pastix_int_t nblevel, pastix_int_t rootnum)
 Print one level of the elimination subtree in a dot file. More...
 
void candGenDotLevel (const EliminTree *etree, const Cand *candtab, FILE *stream, pastix_int_t nblevel)
 Print the first levels of the elimination tree in a dot file. More...
 
void candGenCompressedDot (const EliminTree *etree, const Cand *candtab, FILE *stream)
 Print the compressed elimination tree in a dot file, where all nodes with the same candidates are merged together. More...
 
EliminTreeeTreeInit (pastix_int_t nodenbr)
 Initialize the elimination tree structure. More...
 
void eTreeExit (EliminTree *etree)
 Free the elimination tree structure. More...
 
void eTreeGenDot (const EliminTree *etree, FILE *stream)
 Print the elimination tree in a dot file. More...
 
void eTreePrint (const EliminTree *etree, FILE *stream, pastix_int_t rootnum)
 Print the elimination tree in a human readable format. More...
 
void eTreeSetSons (EliminTree *etree)
 Set the fsonnum fields base on the initialized sonsnbr. More...
 
pastix_int_t eTreeLeavesNbr (const EliminTree *etree)
 Compute the number of leaves. More...
 
pastix_int_t eTreeLevel (const EliminTree *etree)
 Compute the height of the elimination tree. More...
 
pastix_int_t eTreeNodeLevel (const EliminTree *etree, pastix_int_t nodenum)
 Compute the number of level existing below a given node. More...
 
EliminTreeeTreeBuild (const symbol_matrix_t *symbmtx)
 Build the elimination tree. More...
 
pastix_int_t eTreeComputeLevels (EliminTree *etree, pastix_int_t rootnum, pastix_int_t rootlvl)
 Compute the number of level existing below a given node. More...
 
pastix_int_t eTreeGetLevelMinIdx (const EliminTree *etree, pastix_int_t root, pastix_int_t lvl, pastix_int_t idxmin)
 Return the smallest index of the nodes belonging to the level lvl in the elimination tree. More...
 
static eTreeNode_teTreeFather (const EliminTree *etree, pastix_int_t node)
 Return the father of a given node. More...
 
static pastix_int_t eTreeSonI (const EliminTree *etree, pastix_int_t node, pastix_int_t i)
 Return the i^{th} son of a given node. More...
 
static pastix_int_t eTreeRoot (const EliminTree *etree)
 Return the root of the elimination tree. More...
 
static void etree_SetSonsIndex (EliminTree *etree)
 Set the fsonnum fields base on the initialized sonsnbr. More...
 

Detailed Description


Data Type Documentation

◆ etree_node_s

struct etree_node_s

Node of the elimination tree.

Definition at line 25 of file elimintree.h.

Data Fields
double ndecost

Cost of the tree node only (compute + send)

double ndepath

Critical path of the tree node only

double subcost

Cost of the subtree (including node)

double subpath

Critical path of the subtree (including node)

int ndlevel

Node depth in the elimination tree

int sonsnbr

Number of sons

pastix_int_t fathnum

index of the father node

pastix_int_t fsonnum

index of first son

◆ etree_s

struct etree_s

Elimination tree.

Definition at line 39 of file elimintree.h.

Data Fields
pastix_int_t baseval

Base value for numberings

pastix_int_t nodenbr

Number of nodes

eTreeNode_t * nodetab

Array of node [+1,based]

pastix_int_t * sonstab

Sons index of nodes

Function Documentation

◆ compress_getNodeNbr()

static pastix_int_t compress_getNodeNbr ( const EliminTree etree,
const Cand candtab,
pastix_int_t  rootnum 
)
inlinestatic

Compute the number of nodes in the compressed tree. The compression is based on identical candidates for computations.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]candtabThe candidate array associated to the elimination tree for additional information.
[in]rootnumThe root index of the subtree to compress.
Returns
The number of nodes of the subtree.

Definition at line 53 of file cand_gendot.c.

References eTreeSonI(), cand_s::fcandnum, cand_s::lcandnum, etree_s::nodetab, and etree_node_s::sonsnbr.

Referenced by candGenCompressedDot().

◆ compress_setSonsNbr()

static void compress_setSonsNbr ( const EliminTree etree,
const Cand candtab,
pastix_int_t  rootnum,
EliminTree ctree,
Cand ccand,
pastix_int_t  fathnum,
pastix_int_t *  cnodeidx,
pastix_int_t *  tmp 
)
inlinestatic

Compress a subtree. The compression is based on identical candidates for computations.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]candtabThe candidate array associated to the elimination tree for additional information. (optionnal)
[in]rootnumThe root index of the subtree to compress.
[in,out]ctreeThe pointer to the compressed elimination tree.
[in,out]ccandThe pointer to the compressed candidate array associated to ctree.
[in]fathnumThe index of the father in the compressed elimination tree.
[in,out]cnodeidxThe index of the next available spot in the compressed elimation tree array to store the nodes.
[in,out]tmpA temporary array of the size of the number of nodes in etree for the initial root. It is used to store the elements visited in the tree.

Definition at line 123 of file cand_gendot.c.

References etree_node_s::fathnum, cand_s::fcandnum, etree_node_s::fsonnum, cand_s::lcandnum, etree_node_s::ndecost, etree_s::nodetab, etree_node_s::sonsnbr, etree_s::sonstab, etree_node_s::subcost, and etree_node_s::subpath.

Referenced by candGenCompressedDot().

◆ candGenDot()

void candGenDot ( const EliminTree etree,
const Cand candtab,
FILE *  stream 
)

Print the elimination tree in a dot file.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]candtabThe candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]streamThe file to which write the elimination tree in the dot format.

Definition at line 253 of file cand_gendot.c.

References cand_s::lcandnum, etree_node_s::ndecost, etree_node_s::ndepath, etree_s::nodenbr, etree_s::nodetab, etree_node_s::subcost, and etree_node_s::subpath.

Referenced by candGenCompressedDot().

◆ candGenDotLevelSub()

static void candGenDotLevelSub ( const EliminTree etree,
const Cand candtab,
FILE *  stream,
pastix_int_t  nblevel,
pastix_int_t  rootnum 
)
inlinestatic

Print one level of the elimination subtree in a dot file.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]candtabThe candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]streamThe file to which write the elimination tree in the dot format.
[in]nblevelThe number of level remaining to be printed.
[in]rootnumThe root of the subtree to print.

Definition at line 331 of file cand_gendot.c.

References eTreeSonI(), cand_s::lcandnum, etree_node_s::ndecost, etree_s::nodetab, etree_node_s::sonsnbr, etree_node_s::subcost, and etree_node_s::subpath.

Referenced by candGenDotLevel().

◆ candGenDotLevel()

void candGenDotLevel ( const EliminTree etree,
const Cand candtab,
FILE *  stream,
pastix_int_t  nblevel 
)

Print the first levels of the elimination tree in a dot file.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]candtabThe candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]streamThe file to which write the elimination tree in the dot format.
[in]nblevelThe number of levels of the elimination tree to print.

Definition at line 405 of file cand_gendot.c.

References candGenDotLevelSub(), and eTreeRoot().

◆ candGenCompressedDot()

void candGenCompressedDot ( const EliminTree etree,
const Cand candtab,
FILE *  stream 
)

Print the compressed elimination tree in a dot file, where all nodes with the same candidates are merged together.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]candtabThe candidate array associated to the elimination tree for additional information.
[in,out]streamThe file to which write the elimination tree in the dot format.

Definition at line 441 of file cand_gendot.c.

References candExit(), candGenDot(), candInit(), compress_getNodeNbr(), compress_setSonsNbr(), eTreeExit(), eTreeInit(), eTreeRoot(), and etree_s::nodenbr.

◆ eTreeInit()

EliminTree * eTreeInit ( pastix_int_t  nodenbr)

Initialize the elimination tree structure.

Parameters
[in,out]etreeThe pointer to the allocated structure to initialize.

Definition at line 39 of file elimintree.c.

References etree_s::baseval, etree_node_s::fathnum, etree_node_s::fsonnum, etree_node_s::ndecost, etree_node_s::ndepath, etree_node_s::ndlevel, etree_s::nodenbr, etree_s::nodetab, etree_node_s::sonsnbr, etree_s::sonstab, etree_node_s::subcost, and etree_node_s::subpath.

Referenced by candGenCompressedDot(), eTreeBuild(), and pastixOrderBuildEtree().

◆ eTreeExit()

void eTreeExit ( EliminTree etree)

Free the elimination tree structure.

Parameters
[in,out]etreeThe pointer to the elimination tree to free.

Definition at line 85 of file elimintree.c.

References etree_s::nodetab, and etree_s::sonstab.

Referenced by candGenCompressedDot(), pastixOrderApplyLevelOrder(), and splitSymbol().

◆ eTreeGenDot()

void eTreeGenDot ( const EliminTree etree,
FILE *  stream 
)

Print the elimination tree in a dot file.

Parameters
[in]etreeThe pointer to the elimination tree.
[in,out]streamThe file to which write the elimination tree in the dot format.

Definition at line 319 of file elimintree.c.

References etree_node_s::ndepath, etree_s::nodenbr, etree_s::nodetab, etree_node_s::subcost, and etree_node_s::subpath.

◆ eTreePrint()

void eTreePrint ( const EliminTree etree,
FILE *  stream,
pastix_int_t  rootnum 
)

Print the elimination tree in a human readable format.

Each node is writen as: Rootnum idx number_of_sons: (son_1) (son_2) ... (son_n)

Parameters
[in]etreeThe pointer to the elimination tree.
[in,out]streamThe file to which write the elimination tree in the dot format.
[in]rootnumThe root of the subtree to write into the file.

Definition at line 374 of file elimintree.c.

References eTreeSonI(), etree_s::nodetab, and etree_node_s::sonsnbr.

◆ eTreeSetSons()

void eTreeSetSons ( EliminTree etree)

Set the fsonnum fields base on the initialized sonsnbr.

Parameters
[in,out]etreeThe pointer to the elimination tree for which the fsonnum fields must be initialized.

Definition at line 138 of file elimintree.c.

References etree_SetSonsIndex(), eTreeFather(), etree_node_s::fsonnum, etree_s::nodenbr, and etree_s::sonstab.

Referenced by eTreeBuild(), and pastixOrderBuildEtree().

◆ eTreeLeavesNbr()

pastix_int_t eTreeLeavesNbr ( const EliminTree etree)

Compute the number of leaves.

Parameters
[in]etreeThe pointer to the elimination tree.
Returns
The number of leaves in the elimination tree.

Definition at line 175 of file elimintree.c.

References etree_s::nodenbr, etree_s::nodetab, and etree_node_s::sonsnbr.

◆ eTreeLevel()

pastix_int_t eTreeLevel ( const EliminTree etree)

Compute the height of the elimination tree.

Parameters
[in]etreeThe pointer to the elimination tree.
Returns
The height of the elimination tree.

Definition at line 205 of file elimintree.c.

References eTreeNodeLevel(), and etree_s::nodenbr.

◆ eTreeNodeLevel()

pastix_int_t eTreeNodeLevel ( const EliminTree etree,
pastix_int_t  nodenum 
)

Compute the number of level existing below a given node.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]nodenumThe index of the node to study.
Returns
The number of level below the node including it.

Definition at line 285 of file elimintree.c.

References eTreeRoot(), etree_node_s::fathnum, and etree_s::nodetab.

Referenced by eTreeLevel().

◆ eTreeBuild()

EliminTree * eTreeBuild ( const symbol_matrix_t symbmtx)

Build the elimination tree.

The elimination tree is computed based on a given symbolic structure, and not from the tree given by the ordering library. Each father of a node is defined as the facing column block of the first off diagonal block.

Parameters
[in]symbmtxThe pointer to the symbol matrix from which the elimination tree is computed.
Returns
The elimination tree linked to the symbol matrix.

Definition at line 474 of file elimintree.c.

References symbol_cblk_s::bloknum, symbol_matrix_s::bloktab, symbol_matrix_s::cblknbr, symbol_matrix_s::cblktab, eTreeInit(), eTreeRoot(), eTreeSetSons(), etree_node_s::fathnum, symbol_blok_s::fcblknm, etree_s::nodetab, and etree_node_s::sonsnbr.

Referenced by splitSymbol().

◆ eTreeComputeLevels()

pastix_int_t eTreeComputeLevels ( EliminTree etree,
pastix_int_t  rootnum,
pastix_int_t  rootlvl 
)

Compute the number of level existing below a given node.

Parameters
[in,out]etreeThe pointer to the elimination tree. On exit, all traversed nodes will be updated with the depth related to the given root.
[in]rootnumThe root of the tree to study.
[in]rootlvlThe level of the root node.
Returns
The maximal depth of the tree.

Definition at line 246 of file elimintree.c.

References eTreeSonI(), etree_node_s::ndlevel, etree_s::nodetab, and etree_node_s::sonsnbr.

Referenced by orderSupernodes().

◆ eTreeGetLevelMinIdx()

pastix_int_t eTreeGetLevelMinIdx ( const EliminTree etree,
pastix_int_t  root,
pastix_int_t  lvl,
pastix_int_t  idxmin 
)

Return the smallest index of the nodes belonging to the level lvl in the elimination tree.

Look recursively in the elimination tree to return the smallest index of all the nodes belonging to a same level defined by lvl.

Parameters
[in]etreeThe pointer to the elimination tree.
[in]rootThe root of the subtree to study.
[in]lvlThe number of levels below root to look for.
[in]idxminThe minimum index already discovered.
Returns
The minimum index found in the descendants of the root node, lvl levels below.

Definition at line 425 of file elimintree.c.

References eTreeSonI(), etree_s::nodetab, and etree_node_s::sonsnbr.

Referenced by orderSupernodes().

◆ eTreeFather()

static eTreeNode_t* eTreeFather ( const EliminTree etree,
pastix_int_t  node 
)
inlinestatic

Return the father of a given node.

Parameters
[in]etreePointer to the elimination tree structure.
[in]nodeThe node of interest.
Returns
The father of the node.

Definition at line 78 of file elimintree.h.

References etree_node_s::fathnum, and etree_s::nodetab.

Referenced by eTreeSetSons().

◆ eTreeSonI()

static pastix_int_t eTreeSonI ( const EliminTree etree,
pastix_int_t  node,
pastix_int_t  i 
)
inlinestatic

Return the i^{th} son of a given node.

Parameters
[in]etreePointer to the elimination tree structure.
[in]nodeThe node of interest.
[in]iThe index of the son wanted.
Returns
The index of the i^{th} son of the node.

Definition at line 105 of file elimintree.h.

References etree_node_s::fsonnum, etree_s::nodetab, and etree_s::sonstab.

Referenced by candGenDotLevelSub(), candSubTreeBuild(), compress_getNodeNbr(), eTreeComputeLevels(), eTreeGetLevelMinIdx(), eTreePrint(), pastixOrderApplyLevelOrder(), propMappSubtree(), and propMappSubtreeOn1P().

◆ eTreeRoot()

static pastix_int_t eTreeRoot ( const EliminTree etree)
inlinestatic

Return the root of the elimination tree.

Parameters
[in]etreePointer to the elimination tree structure.
Returns
The index of the root in the elimination tree.

Definition at line 126 of file elimintree.h.

Referenced by candBuild(), candGenCompressedDot(), candGenDotLevel(), candUpdate(), eTreeBuild(), eTreeNodeLevel(), orderSupernodes(), and propMappTree().

◆ etree_SetSonsIndex()

static void etree_SetSonsIndex ( EliminTree etree)
inlinestatic

Set the fsonnum fields base on the initialized sonsnbr.

Parameters
[in,out]etreeThe pointer to the elimination tree for which the fsonnum fields must be initialized.

Definition at line 110 of file elimintree.c.

References etree_node_s::fsonnum, etree_s::nodenbr, etree_s::nodetab, and etree_node_s::sonsnbr.

Referenced by eTreeSetSons().