Directional cluster bases for directional $\mathcal{H}^2$ -matrices. More...

Data Structures
struct	_dclusterbasis
	Representation of a directional cluster basis. More...

Typedefs
typedef struct _dclusterbasis	dclusterbasis
	Representation of a directional cluster basis.

typedef dclusterbasis *	pdclusterbasis
	Pointer to a dclusterbasis object.

typedef const dclusterbasis *	pcdclusterbasis
	Pointer to a constant dclusterbasis object.

Functions
pdclusterbasis	init_dclusterbasis (pdclusterbasis cb, pcdcluster t)
	Initialize a dclusterbasis object. More...

void	uninit_dclusterbasis (pdclusterbasis cb)
	Uninitializes a dclusterbasis object. More...

pdclusterbasis	new_dclusterbasis (pcdcluster t)
	Create a new dclusterbasis object. More...

void	del_dclusterbasis (pdclusterbasis cb)
	Delete a dclusterbasis object. More...

void	update_dclusterbasis (pdclusterbasis cb)
	Updates bookkeeping information, e.g., `cb->ktree,` for a dclusterbasis object after its sons have been altered. More...

void	setrank_dclusterbasis (pdclusterbasis cb, uint iota, uint k)
	Change the rank of a directional cluster basis and resize `cb->V[iota]`, while for all sons `i` the transfer matrices `cb->E[i][iota]` is resized. More...

void	initmatrices_dclusterbasis (pdclusterbasis cb)
	Initialize the matrices for a dclusterbasis object. More...

void	findranks_dclusterbasis (uint rank, pcdblock b, pdclusterbasis rb, pdclusterbasis cb)
	Determine the ranks of the directional cluster basis. More...

uint	getactives_dclusterbasis ()
	Get number of active dclusterbasis objects. More...

size_t	getsize_dclusterbasis (pcdclusterbasis cb)
	Get the size of a given dclusterbasis object. More...

size_t	getsize_nonrecursive_dclusterbasis (pcdclusterbasis cb)
	Get the size of a given dclusterbasis object, without considering its sons. More...

uint	getmaxrank_dclusterbasis (pcdclusterbasis cb)
	Get the maximum rank of a given dclusterbasis object. More...

uint	getactivedirections_dclusterbasis (pcdclusterbasis cb)
	Count the number of all used directions for a given dclusterbasis object. More...

void	print_tree_dclusterbasis (pcdclusterbasis cb)
	Print the tree structure of a given dclusterbasis object. More...

pdclusterbasis	buildfromdcluster_dclusterbasis (pcdcluster t)
	Construct a dclusterbasis from a directional cluster tree. More...

pavector	newcoeffs_dclusterbasis (pcdclusterbasis cb)
	Create coefficient vector for a directional cluster basis. More...

void	forward_dclusterbasis (pcdclusterbasis cb, pcavector x, pavector xt)
	Forward transformation. More...

void	backward_dclusterbasis (pcdclusterbasis cb, pavector yt, pavector y)
	Backward transformation. More...

void	slowforward_dclusterbasis (pcdclusterbasis cb, pcavector x, pavector xt)
	Slow version of the forward transformation. More...

void	slowbackward_dclusterbasis (pcdclusterbasis cb, pcavector yt, pavector y)
	Slow version of the backward transformation. More...

void	compress_dclusterbasis (pcdclusterbasis cb, pcavector xp, pavector xt)
	Compute $\hat x_t = V_t^* x$ . More...

void	expand_dclusterbasis (field alpha, pcdclusterbasis cb, pavector yt, pavector yp)
	Add $\alpha V_t \hat y_t$ to target vector . More...

void	blockcompress_dclusterbasis (pcdclusterbasis cb, pcamatrix Xp, pamatrix Xt)
	Compute $\widehat{X}_t = V_t^* X$ . More...

void	blockexpand_dclusterbasis (field alpha, pcdclusterbasis cb, pamatrix Xt, pamatrix Xp)
	Compute $X =X + \alpha V_t \widehat{X}_t$ . More...

pdclusterbasis *	enumerate_dclusterbasis (pcdcluster t, pdclusterbasis cb)
	Enumerate dclusterbasis according to the durectional cluster tree. More...

void	iterate_dclusterbasis (pdclusterbasis cb, uint tname, uint pardepth, void(pre)(pdclusterbasis cb, uint tname, uint pardepth, void data), void(post)(pdclusterbasis cb, uint tname, uint pardepth, void data), void *data)
	Hierarchical iterator for a dclusterbasis. More...

void	ortho_dclusterbasis (pdclusterbasis cb, pdclusteroperator co)
	Create an orthogonal directional cluster basis. More...

void	weight_dclusterbasis_dclusteroperator (pdclusterbasis cb, pdclusteroperator co)
	Compute weight matrices with QR-decomposition. More...

real	check_ortho_dclusterbasis (pcdclusterbasis cb)
	Check if a given directional cluster basis is orthogonal or not. More...

pdclusterbasis	clone_structure_dclusterbasis (pcdclusterbasis cb)
	Clone the structure of an already existing directional cluster basis. More...

pdclusterbasis	duplicate_dclusterbasis (pcdclusterbasis cb)
	Duplicate a directional cluster basis. More...

Detailed Description

Directional cluster bases for directional $\mathcal{H}^2$ -matrices.

Function Documentation

void backward_dclusterbasis	(	pcdclusterbasis	cb,
		pavector	yt,
		pavector	y
	)

Backward transformation.

Compute $y \gets y + V_{t \iota} \widehat y_{t \iota}$ for all elements of the cluster basis. This function also adds permuted coefficients contained in yt to the result vector. It can be used to add the result of fastaddeval_dh2matrix_avector or fastaddevaltrans_dh2matrix_avector to the target vector.

The contents of yt are interpreted as in the function forward_clusterbasis_avector : if cb is not a leaf, the first cb->koff[cb->directions] rows of yt are coefficients to be multiplied by $V_{t \iota}$ for all directions $\iota \in \mathcal{D}_{t}$ . Successively followed by cb->son[j]->k[iota1] coefficients with $iota1 = \mathrm{sd}_{t}(\iota)$ for all sons.

If cb is a leaf, the first cb->koff[cb->directions] rows of yt are also coefficients to be multiplied by $V_{t \iota}$ for all directions $\iota$ , followed by cb->t->size coefficients in cluster numbering to be added to appropriate entries of the target vector.

Remarks: This function accesses the target vector y via the indices in cb->t->idx, so even if cb corresponds only to a small cluster, y usually has to be a vector corresponding to the root of the cluster tree in the original numbering.

Parameters

cb	Directional cluster basis.
yt	Source vector of dimension `cb->ktree`, filled with a mix of transformed coefficients and permuted coefficients. This vector will be overwritten by the function.
y	Target vector.

void blockcompress_dclusterbasis	(	pcdclusterbasis	cb,
		pcamatrix	Xp,
		pamatrix	Xt
	)

Compute $\widehat{X}_t = V_t^* X$ .

Version of compress_dclusterbasis that works for matrices instead of vectors, applying the transformation to all columns simultaneously.

Parameters

cb	Cluster basis.
Xp	Source matrix using cluster numbering corresponding to `cb->t` in the rows.
Xt	Target vector with `cb->kbranch` rows. Its first `cb->k[cb->directions]` rows will be filled by the transformed coefficients.

void blockexpand_dclusterbasis	(	field	alpha,
		pcdclusterbasis	cb,
		pamatrix	Xt,
		pamatrix	Xp
	)

Compute $X =X + \alpha V_t \widehat{X}_t$ .

Version of expand_dclusterbasis that works for matrices instead of vectors, applying the transformation to all columns simultaneously.

Parameters

alpha	Scaling factor $\alpha$ .
cb	Cluster basis.
Xt	Source matrix using cluster numbering corresponding to `cb->t` in the rows.
Xp	Target vector with `cb->kbranch` rows. Its first `cb->koff[cb->directions]` rows will be filled by the transformed coefficients.

pdclusterbasis buildfromdcluster_dclusterbasis ( pcdcluster t )

Construct a dclusterbasis from a directional cluster tree.

Only the structure is for the dclusterbasis object is build, no ranks are determined or matrices initialized.

Parameters

t	Root directional cluster.

Returns: New root dclusterbasis object following the structure of the directional cluster tree.

real check_ortho_dclusterbasis ( pcdclusterbasis cb )

Check if a given directional cluster basis is orthogonal or not.

Evaluate for a directional leaf cluster $\|V_t,\iota^* V_t,\iota - I\|_F$ and for a directional non-leaf cluster $\|\widehat{V}_t,\iota^* \widehat{V}_t,\iota - I\|_F$ and returns the maximum value. If the maximum is significantly larger than the machine eps, the directional cluster shouldn't be considered as orthogonal.

Parameters

cb	Directional cluster basis which should be checked.

Returns: Returns a measure for the orthogonality of the dclusterbasis cb.

pdclusterbasis clone_structure_dclusterbasis ( pcdclusterbasis cb )

Clone the structure of an already existing directional cluster basis.

Simply clone the structure without filling any matrices.

Parameters

cb	dclusterbasis to be cloned.

Returns: Clone of the directional cluster basis cb.

void compress_dclusterbasis	(	pcdclusterbasis	cb,
		pcavector	xp,
		pavector	xt
	)

Compute $\hat x_t = V_t^* x$ .

This function computes $\hat x_t = V_t^* x$ using the transfer matrices $E_{t \iota}$ and the leaf matrices $V_{t \iota}$ , for all directions $\iota$ . Similar to forward_dclusterbasis without permutation.

Parameters

cb	Directional cluster basis.
xp	Source vector using cluster numbering corresponding to `cb->t`.
xt	Target vector of dimension `cb->kbranch`. Its first `cb->koff[cb->directions]` rows will be filled by the transformed coefficients.

void del_dclusterbasis ( pdclusterbasis cb )

Delete a dclusterbasis object.

Releases the storage corresponding to the directional cluster basis.

Parameters

cb	Object to be deleted.

pdclusterbasis duplicate_dclusterbasis ( pcdclusterbasis cb )

Duplicate a directional cluster basis.

Simply copy the structure and fill all matrices.

Parameters

cb	dclusterbasis to be duplicated.

Returns: Directional cluster basis with the copy of cb.

pdclusterbasis* enumerate_dclusterbasis	(	pcdcluster	t,
		pdclusterbasis	cb
	)

Enumerate dclusterbasis according to the durectional cluster tree.

The dclusterbasis elements are enumerated in an array of size t->desc. The enumeration starts with 0 assigned to the root and then proceeds with cb->son[0] corresponding to the entries 1 to t->son[0]->desc in the array and ending with cb->son[sons-1] corresponding to the last t->son[sons-1]->desc entries.

Parameters

t	Directional Cluster tree.
cb	Directional cluster basis matching the cluster tree given by `t`.

Returns: Array of size t->desc containing pointers to the clusterbasis objects corresponding to cb and its descendants.

void expand_dclusterbasis	(	field	alpha,
		pcdclusterbasis	cb,
		pavector	yt,
		pavector	yp
	)

Add $\alpha V_t \hat y_t$ to target vector $y$ .

This function computes $y \gets y + V_t \hat y_t$ using the transfer matrices $E_{t \iota}$ and the leaf matrices $V_{t \iota}$ , for all directions $\iota$ . Similar to backward_dclusterbasis without permutation.

Parameters

alpha	Scaling factor $\alpha$ .
cb	Directional cluster basis.
yt	Target vector of dimension `cb->kbranch`. Its first `cb->koff[cb->directions]` rows contain transformed coefficients.
yp	Source vector using cluster numbering corresponding to `cb->t`.

void findranks_dclusterbasis	(	uint	rank,
		pcdblock	b,
		pdclusterbasis	rb,
		pdclusterbasis	cb
	)

Determine the ranks of the directional cluster basis.

Attention: This function does not initialize the transfer and leaf matrices. Functions like initmatrices_dclusterbasis take care of this part of the initialization.

Parameters

rank	Values for the rank.
b	Corresponding dblock object.
rb	Directional row cluster basis.
cb	Directional column cluster basis.

void forward_dclusterbasis	(	pcdclusterbasis	cb,
		pcavector	x,
		pavector	xt
	)

Forward transformation.

Compute $\hat x_{t \iota} = V_{t \iota}^* x$ for all elements of the cluster basis. This function also stores the permuted coefficients corresponding to the leaves of the cluster basis in the result, preparing all the necessary information for the multiplication phase realized in fastaddeval_dh2matrix_avector and fastaddevaltrans_dh2matrix_avector.

If cb is not a leaf, the first cb->koff[cb->directions] rows of xt are successively filled with $\hat x_{t \iota} = V_{t \iota}^* x$ . The following cb->son[0]->ktree entries are filled with the coefficients for the first son, proceeding until the last cb->son[sons-1]->ktree entries are filled with the coefficients for the last son.

If cb is a leaf, the first cb->koff[cb->directions] rows of xt are also successively filled with $\hat x_{t \iota} = V_{t \iota}^* x$ . The following cb->t->size rows are filled with the coefficients of the original vector x using the cluster numbering of cb->t.

Remarks: This function accesses the source vector x via the indices in cb->t->idx, so even if cb corresponds only to a small cluster, x usually has to be a vector corresponding to the root of the cluster tree in the original numbering..

Parameters

cb	Directional cluster basis.
x	Source vector.
xt	Target vector of dimension `cb->ktree`, will be filled with a mix of transformed coefficients and permuted coefficients.

uint getactivedirections_dclusterbasis ( pcdclusterbasis cb )

Count the number of all used directions for a given dclusterbasis object.

Parameters

cb	dclusterbasis root.

Returns: Number of all used directions.

uint getactives_dclusterbasis ( )

Get number of active dclusterbasis objects.

Returns: Number of active dclusterbasis objects.

uint getmaxrank_dclusterbasis ( pcdclusterbasis cb )

Get the maximum rank of a given dclusterbasis object.

Yields the maximum rank for all directions and descendants of a directional cluster basis.

Parameters

cb	dclusterbasis root.

Returns: Maximum rank.

size_t getsize_dclusterbasis ( pcdclusterbasis cb )

Get the size of a given dclusterbasis object.

Yields the total size of this object and all its descendants.

Parameters

cb	dclusterbasis root.

Returns: Size of allocated storage in bytes.

size_t getsize_nonrecursive_dclusterbasis ( pcdclusterbasis cb )

Get the size of a given dclusterbasis object, without considering its sons.

Yields the total size of a directional cluster basis without taking all its descendants into account.

Parameters

cb	dclusterbasis root.

Returns: Size of allocated storage in bytes.

pdclusterbasis init_dclusterbasis	(	pdclusterbasis	cb,
		pcdcluster	t
	)

Initialize a dclusterbasis object.

Sets up all components of the dclusterbasis object. If t is not a leaf, the array son is allocated, otherwise it is set to null.

Attention: To initialize the matrices for every and direction $\iota\in D_t$ the ranks have to be find. Therefore the function findranks_dclusterbasis and initmatrices_dclusterbasis exists.

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

Parameters

cb	Object to be initialized.
t	Corresponding cluster.

Returns: Initialized dclusterbasis object.

void initmatrices_dclusterbasis ( pdclusterbasis cb )

Initialize the matrices for a dclusterbasis object.

Resize the matrices for the whole directional cluster basis so that all cluster basis $V$ and transfer matrices $E$ are initialized with the desired size and are ready to be filled.

Parameters

cb	Directional cluster basis, which matrices will be initialized.

void iterate_dclusterbasis	(	pdclusterbasis	cb,
		uint	tname,
		uint	pardepth,
		void()(pdclusterbasis cb, uint tname, uint pardepth, void data)	pre,
		void()(pdclusterbasis cb, uint tname, uint pardepth, void data)	post,
		void *	data
	)

Hierarchical iterator for a dclusterbasis.

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

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

Parameters

cb	Root of the directional cluster basis tree.
tname	Number of the root.
pardepth	Parallelization depth.
pre	Function to be called before the descendants of `cb` are processed.
post	Function to be called after the descentants of `cb` have been processed.
data	Additional data passed on to `pre` and `post`.

pdclusterbasis new_dclusterbasis ( pcdcluster t )

Create a new dclusterbasis object.

Allocates storage for a new directional cluster basis and sets up its components.

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

Parameters

t	Corresponding directional cluster.

Returns: Returns the newly created dclusterbasis object.

pavector newcoeffs_dclusterbasis ( pcdclusterbasis cb )

Create coefficient vector for a directional cluster basis.

Creates a vector of dimension cb->ktree to hold the coefficients computed by forward_dclusterbasis and expected by backward_dclusterbasis.

Parameters

cb	Directional custer basis.

Returns: Coefficient vector of size cb->ktree.

void ortho_dclusterbasis	(	pdclusterbasis	cb,
		pdclusteroperator	co
	)

Create an orthogonal directional cluster basis.

Compute an orthogonal directional cluster basis $(Q_t,\iota)_{t\in{\mathcal T}_{\mathcal I}, \iota\in D_t}$ and factors $(R_t,\iota)_{t\in{\mathcal T}_{\mathcal I}\iota\in D_t}$ such that $V_t,\iota = Q_t,\iota R_t,\iota$ holds for all directional clusters $t$ and directions $\iota \in D_{t}$ .

Remarks: If the directional clusterbasis of an already existing directional $\mathcal{DH}^2$ -matrix is orthogonalized, you need to call resize_coupling_dh2matrix to get the new coupling matrices.

Attention: The resize_coupling_dh2matrix needs the directional cluster operator filled in this function!

Parameters

cb	Original directional cluster basis $(V_t,\iota)_{t\in{\mathcal T}_{\mathcal I}, \iota\in D_t}$ , will be overwritten with the orthogonal cluster basis.
co	dclusteroperator object will be overwritten with basis change matrices. A simple way to set up this dclusteroperator is to use build_from_dclusterbasis_dclusteroperator.

void print_tree_dclusterbasis ( pcdclusterbasis cb )

Print the tree structure of a given dclusterbasis object.

Prints the structure of the given directional cluster basis and for every basis and directions his rank, cb->ktree and the size of the corresponding cluster.

Parameters

cb	Directional cluster basis to be printed.

void setrank_dclusterbasis	(	pdclusterbasis	cb,
		uint	iota,
		uint	k
	)

Change the rank of a directional cluster basis and resize cb->V[iota], while for all sons i the transfer matrices cb->E[i][iota] is resized.

Parameters

cb	Directional cluster basis that will be changed.
iota	Direction whose rank is changed.
k	New rank, i.e., number of columns of `V` or `cb->E[i][iota]`.

void slowbackward_dclusterbasis	(	pcdclusterbasis	cb,
		pcavector	yt,
		pavector	y
	)

Slow version of the backward transformation.

Version of backward_dclusterbasis that uses the matrices cb->V for all clusters, not only for leaves. If cb is not a leaf cluster V is reconstructed.

Parameters

cb	Directional cluster basis.
yt	Source vector of dimension `cb->ktree`, filled with a mix of transformed coefficients and permuted coefficients. This vector will be overwritten by the function.
y	Target vector.

void slowforward_dclusterbasis	(	pcdclusterbasis	cb,
		pcavector	x,
		pavector	xt
	)

Slow version of the forward transformation.

Version of forward_dclusterbasis that uses the matrices cb->V for all clusters, not only for leaves. If cb is not a leaf cluster V is reconstructed.

Parameters

cb	Directional cluster basis.
x	Source vector.
xt	Target vector of dimension `cb->ktree`, will be filled with a mix of transformed coefficients and permuted coefficients.

void uninit_dclusterbasis ( pdclusterbasis cb )

Uninitializes a dclusterbasis object.

Invalidates pointers, freeing corresponding storage if appropriate, and prepares the object for deletion.

Parameters

cb	Object to be uninitialized.

void update_dclusterbasis ( pdclusterbasis cb )

Updates bookkeeping information, e.g., cb->ktree, for a dclusterbasis object after its sons have been altered.

Remarks: This function will not update the sons recursively!

Parameters

cb	dclusterbasis that will be updated.

void weight_dclusterbasis_dclusteroperator	(	pdclusterbasis	cb,
		pdclusteroperator	co
	)

Compute weight matrices with QR-decomposition.

Compute factors $(R_t,\iota)_{t\in{\mathcal T}_{\mathcal I}\iota\in D_t}$ for all directional clusters $t$ and save them in the directional cluster operator.

Parameters

cb	Directional cluster basis.
co	Directional cluster operator for saving the weight matrices.

Data Structures

Typedefs

Functions

Detailed Description

Function Documentation