HierMat package

Submodules

HierMat.block_cluster_tree module

block_cluster_tree.py: BlockClusterTree, build_block_cluster_tree(), recursion_build_block_cluster_tree()

class HierMat.block_cluster_tree.BlockClusterTree(left_clustertree, right_clustertree, sons=None, level=0, is_admissible=False, plot_info=None)

Bases: object

Compares two cluster trees level wise with respect to an admissibility condition and builds a tree

depth(root_level=None)

Get depth of the tree

Parameters:root_level (int) – internal use. Returns:depth Return type:int

Hint

recursive function

draw(axes, admissible_color='#1e26bc', inadmissible_color='#bc1d38')

Draw a patch into given axes

Parameters:

• axes (matplotlib.pyplot.axes) – axes instance to draw in
• admissible_color (str) – color for admissible patch (see matplotlib for color specs)
• inadmissible_color (str) – color for inadmissible patch

export(form='xml', out_file='bct_out')

Export obj in specified format.

Parameters:

• form (str) – format specifier
• out_file (str) – path to output file

Raises:

NotImplementedError – if form is not supported

Note

implemented so far:

• xml
• dot
• bin

plot(filename=None, ticks=False, face_color='#133f52', admissible_color='#76f7a8', inadmissible_color='#ff234b')

Plot the block cluster tree

Parameters:

• filename (str) – filename to save the plot. if omitted, the plot will be displayed
• ticks (bool) – show ticks in the plot
• face_color – background color (see matplotlib for color specs)
• admissible_color (str) – color for admissible patch
• inadmissible_color (str) – color for inadmissible patch

Note

depends on matplotlib.pyplot

plot_recursion(axes, admissible_color='#1e26bc', inadmissible_color='#bc1d38')

shape()

Return length of left and right cluster tree

Returns:x and y dimension Return type:tuple(int, int)

to_list()

Give list representation for export

Return a list containing the object and a list with its sons

Hint

recursive function

HierMat.block_cluster_tree.build_block_cluster_tree(left_cluster_tree, right_cluster_tree=None, start_level=0, admissible_function=<function admissible>)

Factory for building a block cluster tree

Parameters:

• left_cluster_tree (ClusterTree) – “left side” cluster tree
• right_cluster_tree (ClusterTree) – “right side” cluster tree
• start_level (int) – counter that keeps track of the level
• admissible_function (function that returns a bool) – function that determines whether two cluster trees are admissible or not. This is crucial for the structure of the block cluster tree. (See utils.admissible for an example)

Returns:

block cluster tree

Return type:

BlockClusterTree

HierMat.block_cluster_tree.recursion_build_block_cluster_tree(current_tree, admissible_function)

Recursion to build_block_cluster_tree()

HierMat.cluster module

cluster.py: Cluster object and iterator

class HierMat.cluster.Cluster(grid, indices=None)

Bases: object

Handles operations on a Grid object by manipulating an index list

diameter()

Compute diameter

Return the maximal Euclidean distance between two points For big Clusters this is costly

Returns:diameter Return type:float

dim()

Compute dimension

Returns:dim of Grid Return type:int

distance(other)

Compute distance to other cluster

Return minimal Euclidean distance between points of self and other

Parameters:other – another instance of Cluster Returns:distance Return type:float

get_grid_item(item)

Return item from grid

Parameters:item (int) – index

get_index(item)

Return index at item

Parameters:item (int) – index Returns:item-th index Return type:int

get_patch_coordinates()

Return min and max out of indices

Returns:min and max Return type:tuple(int, int)

class HierMat.cluster.ClusterIterator(cluster)

Bases: object

Iterator to Cluster object

next()

HierMat.cluster_tree module

cluster_tree.py: ClusterTree, build_cluster_tree(), recursion_build_cluster_tree()

class HierMat.cluster_tree.ClusterTree(content, sons=None, max_leaf_size=1, level=0)

Bases: object

Tree structure built according to the Splitable in use

Splits are done until max_leaf_size is reached

depth(root_level=None)

Get depth of the tree

Parameters:root_level (int) – internal use. Returns:depth Return type:int

Hint

recursive function

diameter()

Return the diameter of content

Returns:diameter Return type:float

distance(other)

Return distance to other

Parameters:other (ClusterTree) – other cluster tree Returns:distance Return type:float

export(form='xml', out_file='out')

Export obj in specified format.

Parameters:

• form (str) – format specifier
• out_file (str) – path to output file

Raises:

NotImplementedError – if form is not supported

Note

implemented so far:

• xml
• dot
• bin

get_grid_item(item)

Get grid item from content

Parameters:item (int) – index of item to get

get_index(item)

Get index from content

Parameters:item (int) – index to get Returns:index Return type:int

get_patch_coordinates()

Return min and max out of indices

Returns:min and max Return type:tuple(int, int)

to_list()

Give list representation for export

Return a list containing the object and a list with its sons

Hint

recursive function

HierMat.cluster_tree.build_cluster_tree(splitable, max_leaf_size=1, start_level=0)

Factory for building a cluster tree

Parameters:

• splitable (Splitable) – strategy that decides the structure
• max_leaf_size (int) – cluster size at which recursion stops
• start_level (int) – counter to identify levels

Returns:

cluster tree

Return type:

ClusterTree

HierMat.cluster_tree.recursion_build_cluster_tree(current_tree)

Recursion to build_cluster_tree()

HierMat.cuboid module

cuboid.py: Cuboid and minimal_cuboid()

class HierMat.cuboid.Cuboid(low_corner, high_corner)

Bases: object

Cuboid that is parallel to the axis in Cartesian coordinates.

Characterized by two diagonal corners.

• Attributes:

  low_corner: numpy.array with minimal values in each dimension

  high_corner: numpy.array with maximal values in each dimension

diameter()

Return the diameter of the cuboid.

Diameter is the Euclidean distance between low_corner and high_corner.

Returns:diameter Return type:float

distance(other)

Return distance to other Cuboid.

Distance is the minimal Euclidean distance between points in self and points in other.

Parameters:other (Cuboid) – other cuboid Returns:distance Return type:float

split(axis=None)

Split the cuboid in half

If axis is specified, the cuboid is split along the given axis, else the maximal axis is chosen.

Parameters:axis (int) – axis along which to split (optional) Returns:cuboid1, cuboid2 Return type:tuple(Cuboid, Cuboid)

HierMat.grid module

grid.py: Grid object and iterator

class HierMat.grid.Grid(points, links)

Bases: object

Discretized grid characterized by points and links

dim()

Dimension of the Grid

Returns:dimension Return type:int

get_link(item)

Return link at position item

Parameters:item (int) – index Returns:links

get_point(item)

Return point at position item

Parameters:item (int) – index Returns:point

plot(filename=None)

Plot the grid

Parameters:filename (str) – file to save the plot in. If not specified, the figure is returned

class HierMat.grid.GridIterator(grid)

Bases: object

Iterator to Grid object

next()

HierMat.hmat module

hmat.py: HMat

class HierMat.hmat.HMat(blocks=(), content=None, shape=(), root_index=())

Bases: object

Implement a hierarchical Matrix

to_matrix()

Full matrix representation

Returns:full matrix Return type:numpy.matrix

HierMat.hmat.build_hmatrix(block_cluster_tree=None, generate_rmat_function=None, generate_full_matrix_function=None)

Factory to build an HMat instance

Parameters:

• block_cluster_tree (BlockClusterTree) – block cluster tree giving the structure
• generate_rmat_function – function taking an admissible block cluster tree and returning a rank-k matrix
• generate_full_matrix_function – function taking an inadmissible block cluster tree and returning a numpy.matrix

Returns:

hmatrix

Return type:

RMat

Raises:

ValueError if root of BlockClusterTree is admissible

HierMat.hmat.recursion_build_hmatrix(current_hmat, block_cluster_tree, generate_rmat, generate_full_mat)

Recursion to build_hmatrix()

HierMat.rmat module

rmat.py: RMat

class HierMat.rmat.RMat(left_mat, right_mat=None, max_rank=None)

Bases: object

Rank-k matrix

Implementation of the low rank matrix as described in [HB2015]

form_add(other, rank=None)

Formatted addition of self and other, i.e. addition and reduction to rank:

(self + other).reduce(rank)

If rank is omitted, reduction to min(rank(self), rank(other))

Parameters:

• other (RMat) – other rank-k matrix
• rank (int) – rank after reduction

Returns:

reduced result

Return type:

RMat

from_matrix(matrix, max_rank)

Convert a full matrix to the rank k format

Parameters:

• matrix (numpy.matrix) – Matrix to convert to RMat
• max_rank (int) – maximum rank

Returns:

Best approximation of matrix in RMat format

Return type:

RMat

norm(order=None)

Norm of the matrix

Parameters:order – order of the norm (see in numpy.linalg.norm()) Returns:norm Return type:float

reduce(new_k)

Perform a reduced QR decomposition to rank new_k

Parameters:new_k (int) – rank to reduce to Returns:reduced matrix Return type:RMat

to_matrix()

Full matrix representation:

left_mat * right_mat.T

Returns:full matrix Return type:numpy.matrix

HierMat.splitable module

splitable.py: Splitable (Interface) and iterator and different strategies

• RegularCuboid

  Starting from a minimal cuboid that get’s split in half on every level, points are distributed according to their geometric location

• MinimalCuboid

  Same as RegularCuboid, but after every split, the cuboids are reduced to minimal size

• Balanced

  Distributes the points evenly on every level, depends solely on the order of the initial list

class HierMat.splitable.Balanced(cluster)

Bases: HierMat.splitable.Splitable

Balanced strategy, where a cluster is always split in half only according to its size, without regarding the geometry

Gives a binary tree

diameter()

Return the diameter

Diameter of the contained cluster

Returns:diameter Return type:float

distance(other)

Distance to other balanced

Parameters:other (Balanced) – other balanced Returns:distance Return type:float

get_grid_item(item)

Get grid item from cluster

Parameters:item (int) – index of item to get

get_index(item)

Get index from cluster

Parameters:item (int) – index to get Returns:index Return type:int

get_patch_coordinates()

Return min and max out of indices

Returns:min and max Return type:tuple(int, int)

split()

Split in two

distribute the first (smaller) half to the left and the rest to the right

return itself if it has only one point

Return type:list(Balanced)

class HierMat.splitable.MinimalCuboid(cluster)

Bases: HierMat.splitable.RegularCuboid

Method of minimal cuboids

Split is implemented by splitting the surrounding cuboid in half along longest axis and distributing indices according to the cuboid they belong to. Afterwards all resulting cuboids are shrunk to minimal.

Gives a binary tree

split()

Split the cuboid and distribute items in cluster according to the cuboid they belong to. Reduce every split to minimal size

Returns:list of minimal cuboids of smaller size Return type:list(MinimalCuboid)

class HierMat.splitable.RegularCuboid(cluster, cuboid=None)

Bases: HierMat.splitable.Splitable

Method of regular cuboids

If no cuboid is given, a minimal cuboid is built around initial list of indices. Split is then implemented by splitting the surrounding cuboid in half along longest axis and distributing indices according to the cuboid they belong to.

Gives a binary tree

diameter()

Return the diameter of the cuboid

Diameter of the surrounding cuboid

Returns:diameter Return type:float

distance(other)

Return the distance between own cuboid and other cuboid

Parameters:other (RegularCuboid) – other regular cuboid Returns:distance Return type:float

get_grid_item(item)

Get grid item from cluster

Parameters:item (int) – index of item to get

get_index(item)

Get index from cluster

Parameters:item (int) – index to get Returns:index Return type:int

get_patch_coordinates()

Return min and max out of indices

Returns:min and max Return type:tuple(int, int)

split()

Split the cuboid and distribute items in cluster according to the cuboid they belong to

Returns:list of smaller regular cuboids Return type:list(RegularCuboid)

class HierMat.splitable.Splitable

Bases: object

Interface to the different strategies that can be used to split a cluster in two or more.

Note

Methods that need to be implemented by subclasses:

• __len__: return the length of the cluster
• __iter__: return SplitableIterator(self)
• __repr__: give a meaningful string representation
• __getitem__: return item from inner cluster
• __eq__: check for equality against other Splitable
• get_index: return index from inner cluster
• get_grid_item: return grid item from inner cluster
• get_patch_coordinates: return min and max of index list of cluster
• split: split the object in two or more, return new instances
• diameter: return the diameter of the object
• distance: return the distance to other object

diameter()

distance(other)

get_grid_item(item)

get_index(item)

get_patch_coordinates()

split()

class HierMat.splitable.SplitableIterator(obj)

Bases: object

Iterator to the Splitable implementations.

next()

HierMat.utils module

utils.py: Utilities for the HMatrix module

HierMat.utils.admissible(left_clustertree, right_clustertree)

Default admissible condition for BlockClusterTree

True if the smaller diameter of the input is smaller or equal to the distance between the two ClusterTrees

Parameters:

• left_clustertree (ClusterTree) – “Left-side” ClusterTree
• right_clustertree (ClusterTree) – “Right-side” ClusterTree

Returns:

admissible

Return type:

bool

HierMat.utils.divisor_generator(n)

Return divisors of n

Parameters:n (int) – integer to find divisors of Returns:divisors Return type:list[int]

Warning

This is a generator! To get a list with all divisors call:

list(divisor_generator(n))

Note

found at StackOverflow on 2017.03.08

HierMat.utils.load(filename)

Load a ClusterTree or BlockClusterTree from file

Parameters:filename (String) – file to import Returns:object Return type:BlockClusterTree or ClusterTree

Note

Depends on pickle

HierMat.utils.minimal_cuboid(cluster)

Build minimal cuboid

Build minimal cuboid around cluster that is parallel to the axis in Cartesian coordinates

Parameters:cluster (Cluster) – cluster to build cuboid around Returns:minimal cuboid Return type:Cuboid

Module contents