PaStiX Handbook: 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...

EliminTree *	eTreeInit (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...

EliminTree *	eTreeBuild (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_t *	eTreeFather (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]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information.
[in]	rootnum	The 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, pastix_int_t, 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]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information. (optionnal)
[in]	rootnum	The root index of the subtree to compress.
[in,out]	ctree	The pointer to the compressed elimination tree.
[in,out]	ccand	The pointer to the compressed candidate array associated to ctree.
[in]	fathnum	The index of the father in the compressed elimination tree.
[in,out]	cnodeidx	The index of the next available spot in the compressed elimation tree array to store the nodes.
[in,out]	tmp	A 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, pastix_int_t, 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]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]	stream	The 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, pastix_int_t, etree_node_s::subcost, and etree_node_s::subpath.

Referenced by candGenCompressedDot(), and pastix_subtask_blend().

◆ 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]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]	stream	The file to which write the elimination tree in the dot format.
[in]	nblevel	The number of level remaining to be printed.
[in]	rootnum	The 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, pastix_int_t, 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]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information. (optionnal)
[in,out]	stream	The file to which write the elimination tree in the dot format.
[in]	nblevel	The number of levels of the elimination tree to print.

Definition at line 405 of file cand_gendot.c.

References candGenDotLevelSub(), and eTreeRoot().

Referenced by pastix_subtask_blend().

◆ 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]	etree	The pointer to the elimination tree.
[in]	candtab	The candidate array associated to the elimination tree for additional information.
[in,out]	stream	The 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(), etree_s::nodenbr, and pastix_int_t.

Referenced by pastix_subtask_blend().

◆ eTreeInit()

EliminTree * eTreeInit ( pastix_int_t nodenbr )

Initialize the elimination tree structure.

Parameters

[in] nodenbr TODO

Return values

TODO

Definition at line 43 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, pastix_int_t, etree_node_s::sonsnbr, etree_s::sonstab, etree_node_s::subcost, and etree_node_s::subpath.

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

◆ eTreeExit()

void eTreeExit ( EliminTree * etree )

Free the elimination tree structure.

Parameters

[in,out] etree The pointer to the elimination tree to free.

Definition at line 89 of file elimintree.c.

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

Referenced by candGenCompressedDot(), orderApplyLevelOrder(), pastix_subtask_blend(), pastix_subtask_order(), and splitSymbol().

◆ eTreeGenDot()

void eTreeGenDot	(	const EliminTree *	etree,
		FILE *	stream
	)

Print the elimination tree in a dot file.

Parameters

[in]	etree	The pointer to the elimination tree.
[in,out]	stream	The file to which write the elimination tree in the dot format.

Definition at line 323 of file elimintree.c.

References etree_node_s::ndepath, etree_s::nodenbr, etree_s::nodetab, pastix_int_t, 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]	etree	The pointer to the elimination tree.
[in,out]	stream	The file to which write the elimination tree in the dot format.
[in]	rootnum	The root of the subtree to write into the file.

Definition at line 378 of file elimintree.c.

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

◆ eTreeSetSons()

void eTreeSetSons ( EliminTree * etree )

Set the fsonnum fields base on the initialized sonsnbr.

Parameters

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

Definition at line 142 of file elimintree.c.

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

Referenced by eTreeBuild(), and orderBuildEtree().

◆ eTreeLeavesNbr()

pastix_int_t eTreeLeavesNbr ( const EliminTree * etree )

Compute the number of leaves.

Parameters

[in] etree The pointer to the elimination tree.

Returns: The number of leaves in the elimination tree.

Definition at line 179 of file elimintree.c.

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

◆ eTreeLevel()

pastix_int_t eTreeLevel ( const EliminTree * etree )

Compute the height of the elimination tree.

Parameters

[in] etree The pointer to the elimination tree.

Returns: The height of the elimination tree.

Definition at line 209 of file elimintree.c.

References eTreeNodeLevel(), etree_s::nodenbr, and pastix_int_t.

◆ eTreeNodeLevel()

pastix_int_t eTreeNodeLevel	(	const EliminTree *	etree,
		pastix_int_t	nodenum
	)

Compute the number of level existing below a given node.

Parameters

[in]	etree	The pointer to the elimination tree.
[in]	nodenum	The index of the node to study.

Returns: The number of level below the node including it.

Definition at line 289 of file elimintree.c.

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

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] symbmtx The pointer to the symbol matrix from which the elimination tree is computed.

Returns: The elimination tree linked to the symbol matrix.

Definition at line 478 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, pastix_int_t, and etree_node_s::sonsnbr.

Referenced by pastix_subtask_blend(), and 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]	etree	The pointer to the elimination tree. On exit, all traversed nodes will be updated with the depth related to the given root.
[in]	rootnum	The root of the tree to study.
[in]	rootlvl	The level of the root node.

Returns: The maximal depth of the tree.

Definition at line 250 of file elimintree.c.

References eTreeSonI(), etree_node_s::ndlevel, etree_s::nodetab, pastix_int_t, 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]	etree	The pointer to the elimination tree.
[in]	root	The root of the subtree to study.
[in]	lvl	The number of levels below root to look for.
[in]	idxmin	The minimum index already discovered.

Returns: The minimum index found in the descendants of the root node, lvl levels below.

Definition at line 429 of file elimintree.c.

References eTreeSonI(), etree_s::nodetab, pastix_int_t, 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]	etree	Pointer to the elimination tree structure.
[in]	node	The 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]	etree	Pointer to the elimination tree structure.
[in]	node	The node of interest.
[in]	i	The 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(), candSubTreeDistribDeepestLevel(), candSubTreeDistribDeepestWidth(), candSubTreeDistribFirstLevel(), candSubTreeDistribFirstWidth(), compress_getNodeNbr(), eTreeComputeLevels(), eTreeGetLevelMinIdx(), eTreePrint(), orderApplyLevelOrder(), propMappSubtree(), and propMappSubtreeOn1P().

◆ eTreeRoot()

static pastix_int_t eTreeRoot ( const EliminTree * etree )

inlinestatic

Return the root of the elimination tree.

Parameters

[in] etree Pointer 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(), pastix_subtask_blend(), and propMappTree().

◆ etree_SetSonsIndex()

static void etree_SetSonsIndex ( EliminTree * etree )

inlinestatic

Set the fsonnum fields base on the initialized sonsnbr.

Parameters

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

Definition at line 114 of file elimintree.c.

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

Referenced by eTreeSetSons().

Data Structures

Typedefs

Functions

Detailed Description

Data Type Documentation

◆ etree_node_s

◆ etree_s

Function Documentation

◆ compress_getNodeNbr()

◆ compress_setSonsNbr()

◆ candGenDot()

◆ candGenDotLevelSub()

◆ candGenDotLevel()

◆ candGenCompressedDot()

◆ eTreeInit()

◆ eTreeExit()

◆ eTreeGenDot()

◆ eTreePrint()

◆ eTreeSetSons()

◆ eTreeLeavesNbr()

◆ eTreeLevel()

◆ eTreeNodeLevel()

◆ eTreeBuild()

◆ eTreeComputeLevels()

◆ eTreeGetLevelMinIdx()

◆ eTreeFather()

◆ eTreeSonI()

◆ eTreeRoot()

◆ etree_SetSonsIndex()