The Block Hilbert triplet scheme. More...

#include <BlockHilbert.hpp>

Inheritance diagram for BlockHilbert< T >:

Collaboration diagram for BlockHilbert< T >:

Public Member Functions
virtual	~BlockHilbert ()
	Base deconstructor. More...

	BlockHilbert ()
	Base constructor. More...

	BlockHilbert (std::string file, T zero=0, char bisect=0)
	Base constructor. More...

	BlockHilbert (std::vector< Triplet< T > > &input, LI m, LI n, T zero)
	Base constructor. More...

	BlockHilbert (std::vector< Triplet< T > > &input, LI m, LI n, char bisect, T zero)
	Base constructor. More...

virtual void	load (std::vector< Triplet< T > > &input, const LI m, const LI n, const T zero)

virtual void	getFirstIndexPair (LI &row, LI &col)
	Returns the first nonzero index, per reference. More...

virtual void	zxa (const T x, T z)
	Calculates z=xA. More...

virtual void	zax (const T x, T z)
	Calculates z=Ax. More...

virtual size_t	bytesUsed ()
	Function to query the amount of storage required by this sparse matrix. More...

Public Member Functions inherited from SparseMatrix< T, LI >
	SparseMatrix ()
	Base constructor. More...

	SparseMatrix (const LInzs, const LInr, const LInc, const T zero)
	Base constructor. More...

virtual	~SparseMatrix ()
	Base deconstructor. More...

void	loadFromFile (const std::string file, const T zero=0)
	Function which loads a matrix from a matrix market file. More...

virtual unsigned long int	m ()
	Queries the number of rows this matrix contains. More...

virtual unsigned long int	n ()
	Queries the number of columns this matrix contains. More...

virtual unsigned long int	nzs ()
	Queries the number of nonzeroes stored in this matrix. More...

virtual T *	mv (const T *x)
	Calculates and returns z=Ax. More...

virtual void	zax (const T __restrict__ x, T __restrict__ z)=0
	In-place z=Ax function. More...

virtual void	zxa (const T __restrict__ x, T __restrict__ z)=0
	In-place z=xA function. More...

Public Member Functions inherited from Matrix< T >
	Matrix ()
	Base constructor. More...

virtual	~Matrix ()
	Base deconstructor. More...

virtual void	zax (const T __restrict__ x, T __restrict__ z, const size_t k, const clockid_t clock_id=0, double *elapsed_time=NULL)
	Wrapper function to call the zax kernel multiple times successively, while timing the duration of the operation. More...

template<size_t k>
void	ZaX (const T __restrict__ const __restrict__ const X, T __restrict__ const __restrict__ const Z)
	In-place Z=AX function, where A is m x n, Z = m x k, and X is n x k. More...

template<size_t k>
void	ZXa (const T __restrict__ const __restrict__ const X, T __restrict__ const __restrict__ const Z)
	In-place Z=XA function, where A is m x n, Z = k x n, and X is k x m. More...

virtual void	zxa (const T __restrict__ x, T __restrict__ z, const unsigned long int repeat, const clockid_t clock_id=0, double *elapsed_time=NULL)
	Wrapper function to call the zxa kernel multiple times successively, while timing the operation duration. More...

Protected Member Functions
char	bisect (std::vector< HilbertTriplet< std::vector< Triplet< T > > > > &build, std::vector< Triplet< T > > &input, const unsigned long int blocki, const unsigned long int blockj, const unsigned char depth)
	Recursive bisection, leaf case. More...

void	bisect (std::vector< HilbertTriplet< std::vector< Triplet< T > > > > &build)
	Automatically performs recursive bisection on the input nonzeroes to achieve sparse blocking. More...

std::vector< HilbertTriplet < std::vector< Triplet< T > > > >	buildBisectionBlocks (std::vector< Triplet< T > > &input)
	Builds block array by bisection. More...

std::vector< HilbertTriplet < std::vector< Triplet< T > > > >	buildBlocks (std::vector< Triplet< T > > &input)
	Builds block array by ordering them in fixed-size sparse submatrices.

bool	cmp (HilbertTriplet< std::vector< Triplet< T > > > &left, HilbertTriplet< std::vector< Triplet< T > > > &right)
	HilbertCoordinate comparison function. More...

unsigned long int	find (HilbertTriplet< std::vector< Triplet< T > > > &x, ULI &left, ULI &right, ULI &minexp)
	Binary search for finding a given triplet in a given range. More...

Protected Attributes
char	bisection
	Whether we use fixed block grid or a bisection-based grid.

ULI	minexp
	Minimum number of expansions.

std::vector< HilbertTriplet < std::vector< Triplet< T > > > >	hilbert
	Vector storing the block indices and their Hilbert coordinates.

HBICRS< T > *	ds
	The actual data structure.

Protected Attributes inherited from SparseMatrix< T, LI >
LI	nor
	Number of rows. More...

LI	noc
	Number of columns.

LI	nnz
	Number of non-zeros. More...

Static Protected Attributes
static const ULI	BLOCK_M = 2048
	Minimum number of rows in a block.

static const ULI	BLOCK_N = 2048
	Minimum number of columns in a block.

static const ULI	MAX_BLOCKS = 1024*128
	Maximum number of blocks.

static const ULI	MAX_DEPTH = 64
	Maximum depth of bisection. More...

static const signed char	DS = 2
	Which data structure to use for each block. More...

Additional Inherited Members
Public Attributes inherited from SparseMatrix< T, LI >
T	zero_element
	The element considered to be zero. More...

Detailed Description

template<typename T>
class BlockHilbert< T >

The Block Hilbert triplet scheme.

In effect similar to (HierarchicalBICRS), but uses Hilbert coordinates to determine the order of the blocks, and a bisection algorithm to construct the individual blocks.

Constructor & Destructor Documentation

template<typename T>

virtual BlockHilbert< T >::~BlockHilbert ( )

inlinevirtual

Base deconstructor.

References BlockHilbert< T >::ds.

template<typename T>

BlockHilbert< T >::BlockHilbert ( )

inline

Base constructor.

References BlockHilbert< T >::bisection.

template<typename T>

BlockHilbert< T >::BlockHilbert	(	std::string	file,
		T	zero = `0`,
		char	bisect = `0`
	)

inline

Base constructor.

Will read in from Matrix Market file.

Parameters

file	The input sparse matrix file.
zero	What element constitutes a matrix zero.
bisect	Whether bisection-based blocking should be used.

See also: SparseMatrix::SparseMatrix( file, zero )

References BlockHilbert< T >::bisect(), BlockHilbert< T >::bisection, and SparseMatrix< T, LI >::loadFromFile().

template<typename T>

BlockHilbert< T >::BlockHilbert	(	std::vector< Triplet< T > > &	input,
		LI	m,
		LI	n,
		T	zero
	)

inline

Base constructor.

Warning: the zero parameter is currently NOT USED!

Parameters

input	Raw input of normal triplets.
m	Total number of rows.
n	Total number of columns.
zero	What elements is considered to-be zero.

References BlockHilbert< T >::bisection, and BlockHilbert< T >::load().

template<typename T>

BlockHilbert< T >::BlockHilbert	(	std::vector< Triplet< T > > &	input,
		LI	m,
		LI	n,
		char	bisect,
		T	zero
	)

inline

Base constructor.

Warning: the zero parameter is currently NOT USED!

Parameters

input	Raw input of normal triplets.
m	Total number of rows.
n	Total number of columns.
bisect	Whether bisection-based blocking should be used.
zero	What elements is considered to-be zero.

References BlockHilbert< T >::bisect(), BlockHilbert< T >::bisection, and BlockHilbert< T >::load().

Member Function Documentation

template<typename T>

char BlockHilbert< T >::bisect	(	std::vector< HilbertTriplet< std::vector< Triplet< T > > > > &	build,
		std::vector< Triplet< T > > &	input,
		const unsigned long int	blocki,
		const unsigned long int	blockj,
		const unsigned char	depth
	)

inlineprotected

Recursive bisection, leaf case.

Parameters

build	A series of sparse blocks with their Hilbert coordinates.
input	The input series of nonzeroes.
blocki	The row blocking size.
blockj	The column blocking size.
depth	Current recursion depth.

Returns: Exit code: 0=failed split, 1=OK, 2=not split.

References BlockHilbert< T >::BLOCK_M, BlockHilbert< T >::BLOCK_N, BlockHilbert< T >::MAX_DEPTH, SparseMatrix< T, LI >::noc, and SparseMatrix< T, LI >::nor.

Referenced by BlockHilbert< T >::bisect(), BlockHilbert< T >::BlockHilbert(), and BlockHilbert< T >::buildBisectionBlocks().

template<typename T>

void BlockHilbert< T >::bisect ( std::vector< HilbertTriplet< std::vector< Triplet< T > > > > & build )

inlineprotected

Automatically performs recursive bisection on the input nonzeroes to achieve sparse blocking.

Parameters

build A series of sparse blocks with their Hilbert coordinates.

References BlockHilbert< T >::bisect(), BlockHilbert< T >::MAX_BLOCKS, and BlockHilbert< T >::MAX_DEPTH.

template<typename T>

std::vector< HilbertTriplet< std::vector< Triplet< T > > > > BlockHilbert< T >::buildBisectionBlocks ( std::vector< Triplet< T > > & input )

inlineprotected

Builds block array by bisection.

resulting in variably-sized submatrices.

Parameters

input Original nonzero input.

Returns: A series of sparse blocks (with Hilbert coordinates).

References BlockHilbert< T >::bisect(), and SparseMatrix< T, LI >::nnz.

Referenced by BlockHilbert< T >::load().

template<typename T>

virtual size_t BlockHilbert< T >::bytesUsed ( )

inlinevirtual

Function to query the amount of storage required by this sparse matrix.

Returns: The size of the sparse matrix in bytes.

Implements Matrix< T >.

References HBICRS< _t_value >::bytesUsed(), and BlockHilbert< T >::ds.

template<typename T>

bool BlockHilbert< T >::cmp	(	HilbertTriplet< std::vector< Triplet< T > > > &	left,
		HilbertTriplet< std::vector< Triplet< T > > > &	right
	)

inlineprotected

HilbertCoordinate comparison function.

References SparseMatrix< T, LI >::noc, and SparseMatrix< T, LI >::nor.

Referenced by BlockHilbert< T >::find().

template<typename T>

unsigned long int BlockHilbert< T >::find	(	HilbertTriplet< std::vector< Triplet< T > > > &	x,
		ULI &	left,
		ULI &	right,
		ULI &	minexp
	)

inlineprotected

Binary search for finding a given triplet in a given range.

Parameters

x	triplet to-be found.
left	Left bound of the range to search in.
right	Right bound of the range to search in.
minexp	The minimum amount of Hilbert coordinate expansions necessary for successful comparison during binary search.