Representation of a block tree. More...

Data Structures
struct	_block
	Representation of block trees. More...

struct	_blockentry
	Auxiliary structure for hierarchical iterators for a block cluster tree. More...

Typedefs
typedef struct _block	block
	Representation of a block tree.

typedef block *	pblock
	Pointer to block object.

typedef const block *	pcblock
	Pointer to constant block object.

typedef bool(*	admissible) (pcluster rc, pcluster cc, void *data)
	Callback function for an admissibility condition.

typedef struct _blockentry	blockentry
	Representation of a blockentry object.

typedef blockentry *	pblockentry
	Pointer to a blockentry object.

typedef const blockentry *	pcblockentry
	Pointer to a constant blockentry object.

Functions
bool	admissible_2_cluster (pcluster rc, pcluster cc, void *data)
	Check the euclidian (maximum) admissibility condition. More...

bool	admissible_max_cluster (pcluster rc, pcluster cc, void *data)
	Check the admissibility condition in the maximum norm. More...

bool	admissible_sphere_cluster (pcluster rc, pcluster cc, void *data)
	Check the admissibility condition for spherical domains. More...

bool	admissible_2_min_cluster (pcluster rc, pcluster cc, void *data)
	Check the euclidian minimum admissibility condition. More...

pblock	new_block (pcluster rc, pcluster cc, bool a, uint rsons, uint csons)
	Create a new block object. More...

void	del_block (pblock b)
	Delete a block tree. More...

void	update_block (pblock b)
	Complete initialization of a block object. More...

pblock	build_nonstrict_block (pcluster rc, pcluster cc, void *data, admissible admis)
	Build a non strict block tree. More...

pblock	build_nonstrict_lower_block (pcluster rc, pcluster cc, void *data, admissible admis)
	Build a non strict lower triangular block tree. More...

pblock	build_strict_block (pcluster rc, pcluster cc, void *data, admissible admis)
	Build a strict block tree. More...

pblock	build_strict_lower_block (pcluster rc, pcluster cc, void *data, admissible admis)
	Build a strict lower triangular block tree. More...

void	draw_cairo_block (cairo_t *cr, pcblock b, int levels)
	Draw a block tree. More...

void	view_block (pcblock b)
	Visualize a block tree in OpenGL. More...

void	iterate_block (pcblock b, uint bname, uint rname, uint cname, void(pre)(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data), void(post)(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data), void *data)
	Hierarchical iterator for a block tree. More...

void	iterate_rowlist_block (pcblock b, uint bname, uint rname, uint cname, uint pardepth, void(pre)(pcblockentry pb, uint pardepth, void data), void(post)(pcblockentry pb, uint pardepth, void data), void *data)
	Iterate through all subblocks of a block tree, rowwise. More...

void	iterate_collist_block (pcblock b, uint bname, uint rname, uint cname, uint pardepth, void(pre)(pcblockentry pb, uint pardepth, void data), void(post)(pcblockentry pb, uint pardepth, void data), void *data)
	Iterate through all subblocks of a block tree, columnwise. More...

void	iterate_byrow_block (pcblock b, uint bname, uint rname, uint cname, uint pardepth, void(pre)(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data), void(post)(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data), void *data)
	Iterate through all subblocks of a block tree. More...

void	iterate_bycol_block (pcblock b, uint bname, uint rname, uint cname, uint pardepth, void(pre)(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data), void(post)(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data), void *data)
	Iterate through all subblocks of a block tree. More...

pblock *	enumerate_block (pblock t)
	Enumerate a block tree. More...

uint *	enumerate_level_block (pblock t)
	Enumerate the levels of a block tree. More...

uint	getdepth_block (pcblock b)
	Compute the depth of a block tree object. More...

uint	compute_csp_block (pcblock b)
	Compute the sparsity of a block object. More...

Detailed Description

Representation of a block tree.

The block class is used to represent block trees.

Function Documentation

bool admissible_2_cluster	(	pcluster	rc,
		pcluster	cc,
		void *	data
	)

Check the euclidian (maximum) admissibility condition.

Checks the euclidian (maximum) admissibility of two cluster trees $ s $ and $ t $ . The block $ (s,t) $ is admissible, if $\max {\text{diam}_2 (B_s) \text{diam}_2 (B_s)} \leq \eta \text{dist}_2 (B_s, B_t)$ . $ B_s $ and $ B_t $ are the bounding boxes for $ s $ and $ t $ , $\text{diam}_2$ is the euclidian diameter, $\text{dist}_2$ the euclidian distance.

Parameters

rc	Row cluster .
cc	Col cluster .
data	Has to be a pointer to real eta.

Returns: TRUE, if the block is admissible, otherwise FALSE.

bool admissible_2_min_cluster	(	pcluster	rc,
		pcluster	cc,
		void *	data
	)

Check the euclidian minimum admissibility condition.

Checks the euclidianminimum admissibility of two cluster trees $ s $ and $ t $ . The block $ (s,t) $ is admissible, if $\min {\text{diam}_2 (B_s) \text{diam}_2 (B_s)} \leq \eta \text{dist}_2 (B_s, B_t)$ . $ B_s $ and $ B_t $ are the bounding boxes for $ s $ and $ t $ , $\text{diam}_2$ is the euclidian diameter, $\text{dist}_2$ the euclidian distance.

Parameters

rc	Row cluster .
cc	Col cluster .
data	Has to be a pointer to real eta.

Returns: TRUE, if the block is admissible, otherwise FALSE.

bool admissible_max_cluster	(	pcluster	rc,
		pcluster	cc,
		void *	data
	)

Check the admissibility condition in the maximum norm.

Checks the admissibility of two cluster trees $ s $ and $ t $ in the maximum norm. The block $ (s,t) $ is admissible, if $\max {\text{diam}_{\infty} (B_s) \text{diam}_{\infty} (B_s)} \leq \eta \text{dist}_{\infty} (B_s, B_t)$ . $ B_s $ and $ B_t $ are the bounding boxes for $ s $ and $ t $ , $\text{diam}_{\infty}$ is the euclidian diameter, $\text{dist}_{\infty}$ the euclidian distance.

Parameters

rc	Row cluster .
cc	Col cluster .
data	Has to be a pointer to real eta.

Returns: TRUE, if the block is admissible, otherwise FALSE.

bool admissible_sphere_cluster	(	pcluster	rc,
		pcluster	cc,
		void *	data
	)

Check the admissibility condition for spherical domains.

Checks the admissibility condition for spherical domains. The block $ (s,t) $ is admissible, if $\max {\text{diam}_{2} (B_s) \text{diam}_{2} (B_s)} \leq \eta \left\|c_s - c_t \right\|_2 - r_t - r_s$ .

$ B_s $ and $ B_t $ are the bounding boxes for $ s $ and $ t $ , $\text{diam}_{\infty}$ is the euclidian diameter, $\text{dist}_{\infty}$ the euclidian distance.

Parameters

rc	Row cluster .
cc	Col cluster .
data	Has to be a pointer to real eta.

Returns: TRUE, if the block is admissible, otherwise FALSE.

pblock build_nonstrict_block	(	pcluster	rc,
		pcluster	cc,
		void *	data,
		admissible	admis
	)

Build a non strict block tree.

Builds a non strict block tree from the row cluster tree $ rc $ and the column cluster tree $ cc $ . A block tree is non-strict if all leaves $ (t,s) $ are admissible or $ t $ or $ s $ have no sons.

Parameters

rc	Row cluster.
cc	Col cluster.
data	Necessary data for the admissibility condition.
admis	Admissibility condition.

Returns: Returns a non strict block tree.

pblock build_nonstrict_lower_block	(	pcluster	rc,
		pcluster	cc,
		void *	data,
		admissible	admis
	)

Build a non strict lower triangular block tree.

Builds a non strict lower triangular block tree from the row cluster tree $ rc $ and the column cluster tree $ cc $ . A block tree is non-strict if all leaves $ (t,s) $ are admissible or $ t $ or $ s $ have no sons.

Parameters

rc	Row cluster.
cc	Col cluster.
data	Necessary data for the admissibility condition.
admis	Admissibility condition.

Returns: Returns a non strict lower triangular block tree.

pblock build_strict_block	(	pcluster	rc,
		pcluster	cc,
		void *	data,
		admissible	admis
	)

Build a strict block tree.

Builds a strict block tree from the row cluster tree $ rc $ and the column cluster tree $ cc $ . A block tree is called strict, if all leaves $ (t,s) $ are admissible or $ t $ and $ s $ are leave cluster.

Parameters

rc	Row cluster.
cc	Col Cluster.
data	Necessary data for the admissibility condition.
admis	Admissibility condition.

Returns: Returns a strict block tree.

pblock build_strict_lower_block	(	pcluster	rc,
		pcluster	cc,
		void *	data,
		admissible	admis
	)

Build a strict lower triangular block tree.

Builds a strict lower triangular block tree from the row cluster tree $ rc $ and the column cluster tree $ cc $ . A block tree is called strict, if all leaves $ (t,s) $ are admissible or $ t $ and $ s $ are leave cluster.

Parameters

rc	Row cluster.
cc	Col Cluster.
data	Necessary data for the admissibility condition.
admis	Admissibility condition.

Returns: Returns a strict lower triangular block tree.

uint compute_csp_block ( pcblock b )

Compute the sparsity of a block object.

Computes the $C_{sp}$ -sparsity of the block tree $ b $ . The block tree is called $C_{sp}$ -sparse, if the number of its block rows and block columns is at most $C_{sp}$ .

Parameters

b	Block tree.

Returns: Returns the $C_{sp}$ -spars of the blcok cluster tree.

void del_block ( pblock b )

Delete a block tree.

Releases the storage corresponding to the object, including the storage of all its descendants.

Parameters

b	Object to be deleted.

void draw_cairo_block	(	cairo_t *	cr,
		pcblock	b,
		int	levels
	)

Draw a block tree.

Draw a block tree to a cairo surface.

Parameters

cr	Cairo surface to be drawn to.
b	The block tree that has to be drawn.
levels	Number of levels of the block tree, that should be drawn. If `levels` == 0 holds, all levels will be drawn.

pblock* enumerate_block ( pblock t )

Enumerate a block tree.

Enumerates the block tree $ t $ in an array of size $ t->desc $ by passing through all descendants and ordering them in a pointer to a block tree object. The enumeration starts with $ 0 $ assigned to the root and then proceeds with depth-first search.

Parameters

t	block tree to be enumerated.

Returns: Returns a pointer, length , to a block tree enumerating all descendants.

uint* enumerate_level_block ( pblock t )

Enumerate the levels of a block tree.

Enumerates the block tree $ t $ in an array of size $ t->desc $ by passing through all descendants, ordering them and filling an array with information of the level of each descendant in the block cluster tree. The array includes at position $ i $ the level of the descendant $ i $ of the block tree.

Parameters

t	block tree to be enumerated.

Returns: Returns a pointer to unsigned int, length , with the level of each descendant.

uint getdepth_block ( pcblock b )

Compute the depth of a block tree object.

Compute the maximal depth of a block tree.

Parameters

b	block object

Returns: Returns the maximal depth of b.

void iterate_block	(	pcblock	b,
		uint	bname,
		uint	rname,
		uint	cname,
		void()(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data)	pre,
		void()(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data)	post,
		void *	data
	)

Hierarchical iterator for a block tree.

Iterate over the blocktree and all its descendants. The pre function is called for each element before its descendants are processed, the post function is called afterwards

tname will take values between tname and tname+t->sons-1, where tname is interpreted as the index of the root, while the indices of the first son start at tname+1, the indices of the second start at tname+1+1t->son[0]->desc, and so on.

Parameters

b	Block tree.
bname	Number of the block tree .
rname	Number of the row cluster tree in `b`.
cname	Number of the column cluster tree in `b`. .
pre	Function to be called before the descendants of `b` are processed.
post	Function to be called after the descendants of `b` are processed.
data	Auxiliary data for Callback Functions.

void iterate_bycol_block	(	pcblock	b,
		uint	bname,
		uint	rname,
		uint	cname,
		uint	pardepth,
		void()(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data)	pre,
		void()(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data)	post,
		void *	data
	)

Iterate through all subblocks of a block tree.

If the iterator works with multiple threads, it guarantees that threads running in parallel call the pre and post functions with different column clusters.

Parameters

b	Block tree.
bname	Number of the block tree.
rname	Number of the row cluster tree in `b`.
cname	Number of the column cluster tree in `b`.
pardepth	Parallelization depth.
pre	Function to be called before the descendants of `b` are processed.
post	Function to be called before the descendants of `b` are processed.
data	Auxiliary data for Callback Functions.

void iterate_byrow_block	(	pcblock	b,
		uint	bname,
		uint	rname,
		uint	cname,
		uint	pardepth,
		void()(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data)	pre,
		void()(pcblock b, uint bname, uint rname, uint cname, uint pardepth, void data)	post,
		void *	data
	)

Iterate through all subblocks of a block tree.

If the iterator works with multiple threads, it guarantees that threads running in parallel call the pre and post functions with different row clusters.

Parameters

b	Block tree.
bname	Number of the block tree.
rname	Number of the row cluster tree in `b` .
cname	Number of the column cluster tree in `b`.
pardepth	Parallelization depth.
pre	Function to be called before the descendants of `b` are processed.
post	funczion to be called after the descendants of `b` are processed.
data	Auxiliary data for Callback Functions.

void iterate_collist_block	(	pcblock	b,
		uint	bname,
		uint	rname,
		uint	cname,
		uint	pardepth,
		void()(pcblockentry pb, uint pardepth, void data)	pre,
		void()(pcblockentry pb, uint pardepth, void data)	post,
		void *	data
	)

Iterate through all subblocks of a block tree, columnwise.

Iterate through all subblocks of a block tree and collect all column blocks in an blockentry object.

Parameters

b	Block tree.
bname	Number of the block tree.
rname	Number of the row cluster tree in `b`.
cname	Number of the column cluster tree in `b`.
pre	Function to be called before the sons of `b` are processed.
pardepth	Parallelization depth.
post	Function to be called after the sons of `b` are processed.
data	Auxiliary data for Callback Functions.

void iterate_rowlist_block	(	pcblock	b,
		uint	bname,
		uint	rname,
		uint	cname,
		uint	pardepth,
		void()(pcblockentry pb, uint pardepth, void data)	pre,
		void()(pcblockentry pb, uint pardepth, void data)	post,
		void *	data
	)

Iterate through all subblocks of a block tree, rowwise.

Iterate through all subblocks of a block tree and collect all row blocks in an h2matrixlist object.

Parameters

b	Block tree.
bname	Number of the block tree.
rname	Number of the row cluster tree in `b`.
cname	Number of the column cluster tree in `b`.
pardepth	Parallelization depth.
pre	Function to be called before the sons of `b` are processed.
post	Function to be called after the sons of `b` are processed.
data	Auxiliary data for Callback Functions.

pblock new_block	(	pcluster	rc,
		pcluster	cc,
		bool	a,
		uint	rsons,
		uint	csons
	)

Create a new block object.

Allocates storage for the object and sets the pointers to the sons to NULL.

Remarks: Should always be matched by a call to del_cluster.

Parameters

rc	Row cluster.
cc	Column cluster.
a	Admissibility flag.
rsons	Number of sons of the row cluster.
csons	Number of sons of the column cluster.

Returns: Returns a new block tree.

void update_block ( pblock b )

Complete initialization of a block object.

Completes initialization of a block tree object after all sons have been initialized. This function computes the number of descendants of the block tree $ b $ .

Remarks: Should be called after all sons of the block tree have been initialized.

Parameters

b	Object to be updated.

void view_block ( pcblock b )

Visualize a block tree in OpenGL.

Parameters

b	The block tree that has to be drawn.

Data Structures

Typedefs

Functions

Detailed Description

Function Documentation