The incremental compressed row storage sparse matrix data structure. More...

#include <vecBICRS.hpp>

Inheritance diagram for vecBICRS< T, block_length_row, block_length_column, _i_value >:

Collaboration diagram for vecBICRS< T, block_length_row, block_length_column, _i_value >:

Public Member Functions
	vecBICRS ()
	Base constructor. More...

	vecBICRS (std::string file, T zero=0)
	Base constructor. More...

	vecBICRS (const ULI number_of_nonzeros, const ULI number_of_rows, const ULI number_of_cols, T zero)
	Base constructor which only initialises the internal arrays. More...

	vecBICRS (vecBICRS< T > &toCopy)
	Copy constructor. More...

	vecBICRS (std::vector< Triplet< T > > &input, const ULI m, const ULI n, const T zero=0)
	Constructor which transforms a collection of input triplets to CRS format. More...

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

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

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

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

	~vecBICRS ()
	Base deconstructor. 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, ULI >
	SparseMatrix ()
	Base constructor. More...

	SparseMatrix (const ULInzs, const ULInr, const ULInc, 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...

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...

Static Public Member Functions
static int	compareTriplets (const void left, const void right)
	Comparison function used for sorting input data. More...

static int	pColumnSort (const void left, const void right)
	Comparison function used for sorting vectorised blocks; in-row column ordering.

static int	pRowSort (const void left, const void right)
	Comparison function used for sorting vectorised blocks; row ordering.

Public Attributes
size_t	fillIn
	Fill-in (explicitly added nonzeroes to enable vectorisation). More...

Public Attributes inherited from SparseMatrix< T, ULI >
T	zero_element
	The element considered to be zero. More...

Protected Member Functions
void	allocate ()
	Utility function: allocate memory areas using the allocsize and jumpsize fields. More...

void	deallocate ()
	Utility function: free all memory areas.

void	postProcessRowIncrements (std::vector< _i_value > &r_ind)
	Makes suitable for vectorisation the row increment array. More...

Static Protected Member Functions
static void	addPadding (std::vector< _i_value > &row_increments, const std::map< size_t, size_t > &row2local, const size_t blockingSize, const size_t prev_row, const size_t m)
	Helper function for vecBICRS construction. More...

static size_t	prepareBlockIteration (std::vector< size_t > *const row_indices, std::vector< _i_value > &row_increments, _i_value &prev_row, const std::vector< Triplet< double > > &input, const size_t k, const size_t m)
	Helper method for oBICRS constructor. More...

Protected Attributes
T *	ds
	Array containing the actual nnz non-zeros. More...

_i_value *	c_ind
	Array containing the column jumps. More...

_i_value *	r_ind
	Array containing the row jumps. More...

size_t	bytes
	Remembers the number of bytes allocated. More...

size_t	allocsize
	The number of nonzeroes allocated (may differ from the actual number of nonzeroes). More...

size_t	jumpsize
	The number of row jumps plus one; i.e., the length of r_ind. More...

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

ULI	noc
	Number of columns.

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

Static Protected Attributes
static const size_t	block_length = block_length_row * block_length_column
	Combined blocking size. More...

Detailed Description

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>
class vecBICRS< T, block_length_row, block_length_column, _i_value >

The incremental compressed row storage sparse matrix data structure.

Constructor & Destructor Documentation

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS ( )

inline

Base constructor.

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS	(	std::string	file,
		T	zero = `0`
	)

inline

Base constructor.

Will read in from Matrix Market file.

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

References SparseMatrix< T, ULI >::loadFromFile().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS	(	const ULI	number_of_nonzeros,
		const ULI	number_of_rows,
		const ULI	number_of_cols,
		T	zero
	)

inline

Base constructor which only initialises the internal arrays.

Note that to gain a valid ICRS structure, these arrays have to be filled by some external mechanism (i.e., after calling this constructor, the internal arrays contain garbage, resuling in invalid datastructure).

Parameters

number_of_nonzeros	The number of non-zeros to be stored.
number_of_rows	The number of rows of the matrix to be stored.
number_of_cols	The number of columns of the matrix to be stored.
zero	Which element is considered to be the zero element.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::allocsize, vecBICRS< T, block_length_row, block_length_column, _i_value >::jumpsize, and SparseMatrix< T, ULI >::nnz.

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS ( vecBICRS< T > & toCopy )

inline

Copy constructor.

Parameters

toCopy Reference to the ICRS datastructure to copy.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::allocsize, vecBICRS< T, block_length_row, block_length_column, _i_value >::c_ind, vecBICRS< T, block_length_row, block_length_column, _i_value >::ds, vecBICRS< T, block_length_row, block_length_column, _i_value >::jumpsize, SparseMatrix< T, ULI >::nnz, SparseMatrix< T, ULI >::noc, SparseMatrix< T, ULI >::nor, vecBICRS< T, block_length_row, block_length_column, _i_value >::r_ind, and SparseMatrix< T, ULI >::zero_element.

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS	(	std::vector< Triplet< T > > &	input,
		const ULI	m,
		const ULI	n,
		const T	zero = `0`
	)

inline

Constructor which transforms a collection of input triplets to CRS format.

The input collection is considered to have at most one triplet with unique pairs of indices. Unspecified behaviour occurs when this assumption is not met.

Parameters

input	The input collection of triplets (i,j,val).
m	The number of rows of the input matrix.
n	The number of columns of the input matrix.
zero	Which element is considered zero.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::load().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

vecBICRS< T, block_length_row, block_length_column, _i_value >::~vecBICRS ( )

inline

Base deconstructor.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::deallocate().

Member Function Documentation

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

static void vecBICRS< T, block_length_row, block_length_column, _i_value >::addPadding	(	std::vector< _i_value > &	row_increments,
		const std::map< size_t, size_t > &	row2local,
		const size_t	blockingSize,
		const size_t	prev_row,
		const size_t	m
	)

inlinestaticprotected

Helper function for vecBICRS construction.

Parameters

row_increments	The row increments array.
row2local	Maps global row indices to local indices.
blockingSize	Pads to this boundary (sensible values are block_length_row or block_length)
prev_row	Base row index.
m	Maximum row index.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::block_length, and SparseMatrix< T, ULI >::m().

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::prepareBlockIteration().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

void vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate ( )

inlineprotected

Utility function: allocate memory areas using the allocsize and jumpsize fields.

See also: allocsize; jumpsize

References vecBICRS< T, block_length_row, block_length_column, _i_value >::allocsize, vecBICRS< T, block_length_row, block_length_column, _i_value >::bytes, vecBICRS< T, block_length_row, block_length_column, _i_value >::c_ind, vecBICRS< T, block_length_row, block_length_column, _i_value >::ds, vecBICRS< T, block_length_row, block_length_column, _i_value >::jumpsize, and vecBICRS< T, block_length_row, block_length_column, _i_value >::r_ind.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::load(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

virtual size_t vecBICRS< T, block_length_row, block_length_column, _i_value >::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 vecBICRS< T, block_length_row, block_length_column, _i_value >::bytes.

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

static int vecBICRS< T, block_length_row, block_length_column, _i_value >::compareTriplets	(	const void *	left,
		const void *	right
	)

inlinestatic

Comparison function used for sorting input data.

References Triplet< T >::i(), and Triplet< T >::j().

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::load().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

virtual void vecBICRS< T, block_length_row, block_length_column, _i_value >::getFirstIndexPair	(	ULI &	row,
		ULI &	col
	)

inlinevirtual

Returns the first nonzero index, per reference.

Implements SparseMatrix< T, ULI >.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::c_ind, and vecBICRS< T, block_length_row, block_length_column, _i_value >::r_ind.

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

virtual void vecBICRS< T, block_length_row, block_length_column, _i_value >::load	(	std::vector< Triplet< T > > &	input,
		const ULI	m,
		const ULI	n,
		const T	zero
	)

inlinevirtual

See also: SparseMatrix::load

Implements SparseMatrix< T, ULI >.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

void vecBICRS< T, block_length_row, block_length_column, _i_value >::postProcessRowIncrements ( std::vector< _i_value > & r_ind )

inlineprotected

Makes suitable for vectorisation the row increment array.

Parameters

r_ind The row increment array.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::block_length.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::load().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

static size_t vecBICRS< T, block_length_row, block_length_column, _i_value >::prepareBlockIteration	(	std::vector< size_t > *const	row_indices,
		std::vector< _i_value > &	row_increments,
		_i_value &	prev_row,
		const std::vector< Triplet< double > > &	input,
		const size_t	k,
		const size_t	m
	)

inlinestaticprotected

Helper method for oBICRS constructor.

Takes an input array of nnz triplets. This function looks at all triplets from index k on, takes the first block_length_row different rows that are encountered, and adds the nonzeroes on those row with a maximum of eight per row.

If a new row index is encountered but block_length_rows were already added, this function stops iterating.

If a new column index on a given row is encountered, but that row already contains block_length_col elements, then this function also stops iterating.

The above two constraints ensure the nonzeroes are always processed in the intended order.

Parameters

row_indices	an array of block_length_row sets that will contain the nonzero indices that will be added to each block.
row_increments	Keep track of row increments.
prev_row	The global index of the last previously added row.
input	the input triplet array.
k	From which k on to start iterating.
m	The number of matrix rows.

Returns: The k at which iteration stopped (exclusive).

References vecBICRS< T, block_length_row, block_length_column, _i_value >::addPadding(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::block_length.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::load().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

virtual void vecBICRS< T, block_length_row, block_length_column, _i_value >::zax	(	const T *__restrict__	pDataX,
		T *__restrict__	pDataZ
	)

inlinevirtual

In-place z=Ax function.

Adapted from the master thesis of Joris Koster, Utrecht University.

Parameters

pDataX	Pointer to array x to multiply by the current matrix (Ax).
pDataZ	Pointer to result array. Must be pre-allocated and its elements set to zero for correct results.

Implements SparseMatrix< T, ULI >.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::allocsize, vecBICRS< T, block_length_row, block_length_column, _i_value >::block_length, vecBICRS< T, block_length_row, block_length_column, _i_value >::c_ind, vecBICRS< T, block_length_row, block_length_column, _i_value >::ds, SparseMatrix< T, ULI >::nnz, SparseMatrix< T, ULI >::noc, SparseMatrix< T, ULI >::nor, and vecBICRS< T, block_length_row, block_length_column, _i_value >::r_ind.

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

virtual void vecBICRS< T, block_length_row, block_length_column, _i_value >::zxa	(	const T *__restrict__	pDataX,
		T *__restrict__	pDataZ
	)

inlinevirtual

In-place z=xA function.

Adapted from the master thesis of Joris Koster, Utrecht University.

Parameters

pDataX	Pointer to array x to multiply by the current matrix (Ax).
pDataZ	Pointer to result array. Must be pre-allocated and its elements set to zero for correct results.

Implements SparseMatrix< T, ULI >.

References vecBICRS< T, block_length_row, block_length_column, _i_value >::allocsize, vecBICRS< T, block_length_row, block_length_column, _i_value >::block_length, vecBICRS< T, block_length_row, block_length_column, _i_value >::c_ind, vecBICRS< T, block_length_row, block_length_column, _i_value >::ds, SparseMatrix< T, ULI >::nnz, SparseMatrix< T, ULI >::noc, SparseMatrix< T, ULI >::nor, and vecBICRS< T, block_length_row, block_length_column, _i_value >::r_ind.

Member Data Documentation

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

size_t vecBICRS< T, block_length_row, block_length_column, _i_value >::allocsize

protected

The number of nonzeroes allocated (may differ from the actual number of nonzeroes).

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::load(), vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS(), vecBICRS< T, block_length_row, block_length_column, _i_value >::zax(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::zxa().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

const size_t vecBICRS< T, block_length_row, block_length_column, _i_value >::block_length = block_length_row * block_length_column

staticprotected

Combined blocking size.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::addPadding(), vecBICRS< T, block_length_row, block_length_column, _i_value >::load(), vecBICRS< T, block_length_row, block_length_column, _i_value >::postProcessRowIncrements(), vecBICRS< T, block_length_row, block_length_column, _i_value >::prepareBlockIteration(), vecBICRS< T, block_length_row, block_length_column, _i_value >::zax(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::zxa().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

size_t vecBICRS< T, block_length_row, block_length_column, _i_value >::bytes

protected

Remembers the number of bytes allocated.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::bytesUsed().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

_i_value* vecBICRS< T, block_length_row, block_length_column, _i_value >::c_ind

protected

Array containing the column jumps.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::deallocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::getFirstIndexPair(), vecBICRS< T, block_length_row, block_length_column, _i_value >::load(), vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS(), vecBICRS< T, block_length_row, block_length_column, _i_value >::zax(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::zxa().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

T* vecBICRS< T, block_length_row, block_length_column, _i_value >::ds

protected

Array containing the actual nnz non-zeros.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::deallocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::load(), vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS(), vecBICRS< T, block_length_row, block_length_column, _i_value >::zax(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::zxa().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

size_t vecBICRS< T, block_length_row, block_length_column, _i_value >::fillIn

Fill-in (explicitly added nonzeroes to enable vectorisation).

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::load().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

size_t vecBICRS< T, block_length_row, block_length_column, _i_value >::jumpsize

protected

The number of row jumps plus one; i.e., the length of r_ind.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::load(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS().

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>

_i_value* vecBICRS< T, block_length_row, block_length_column, _i_value >::r_ind

protected

Array containing the row jumps.

Referenced by vecBICRS< T, block_length_row, block_length_column, _i_value >::allocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::deallocate(), vecBICRS< T, block_length_row, block_length_column, _i_value >::getFirstIndexPair(), vecBICRS< T, block_length_row, block_length_column, _i_value >::load(), vecBICRS< T, block_length_row, block_length_column, _i_value >::vecBICRS(), vecBICRS< T, block_length_row, block_length_column, _i_value >::zax(), and vecBICRS< T, block_length_row, block_length_column, _i_value >::zxa().

The documentation for this class was generated from the following file:

vecBICRS.hpp

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI> class vecBICRS< T, block_length_row, block_length_column, _i_value >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename T, size_t block_length_row = 1, size_t block_length_column = 8, typename _i_value = LI>
class vecBICRS< T, block_length_row, block_length_column, _i_value >