Represents a sparse matrix. More...

#include <jem/numeric/sparse/SparseMatrix.h>

Public Types
typedef SparseStructure	Structure
	The structure of a sparse matrix. More...

typedef Structure::Shape	Shape
	The shape of a sparse matrix. More...

Public Member Functions
	SparseMatrix ()
	Constructs an empty sparse matrix. More...

	SparseMatrix (const Structure &s)
	Constructs a sparse matrix with a given structure. More...

	SparseMatrix (const Structure &s, const Array< T > &values)
	Constructs a sparse matrix with a given structure and value array. More...

	SparseMatrix (const Shape &sh, const Array< int > &offsets, const Array< int > &indices)
	Constructs a sparse matrix given an offset and an index array. More...

	SparseMatrix (const Shape &sh, const Array< int > &offsets, const Array< int > &indices, const Array< T > &values)
	Constructs a sparse matrix given an offset, an index and a value array. More...

	SparseMatrix (const SparseMatrix &rhs)
	Creates a shallow copy of another sparse matrix. More...

SparseMatrix &	operator= (const SparseMatrix &rhs)
	Makes a shallow copy of another sparse matrix. More...

void	swap (SparseMatrix &rhs)
	Interchanges the contents of two sparse matrices. More...

SparseMatrix	clone () const
	Returns a deep copy of this sparse matrix. More...

SparseMatrix	transpose () const
	Returns the transpose of this sparse matrix. More...

Structure	getStructure () const
	Tests whether the structure of this matrix is valid. More...

int	nonZeroCount () const
	Returns the number of non-zero elements in this sparse matrix. More...

Shape	shape () const
	Returns the shape of this sparse matrix. More...

int	size (int dim) const
	Returns the size of this sparse matrix in a given dimension. More...

const Array< int > &	getRowOffsets () const
	Returns a reference to the row offset array. More...

const Array< int > &	getColumnIndices () const
	Returns a reference to the column index array. More...

Array< int >	getColumnIndices (int i) const
	Returns the column indices of the non-zero elements on a particular row. More...

const Array< T > &	getValues () const
	Returns a reference to the value array. More...

Array< T >	getValues (int i) const
	Returns the values of the non-zero elements on a particular row. More...

Related Functions
(Note that these are not member functions.)
template<class T >
io::DataInput &	operator>> (io::DataInput &in, SparseMatrix< T > &a)
	Sparse matrix de-serialization operator. More...

template<class T >
io::DataOutput &	operator<< (io::DataOutput &out, const SparseMatrix< T > &a)
	Sparse matrix serialization operator. More...

template<class T >
io::TextOutput &	operator<< (io::TextOutput &out, const SparseMatrix< T > &a)
	Sparse matrix print operator. More...

template<class T >
void	swap (SparseMatrix< T > &lhs, SparseMatrix< T > &rhs)
	Interchanges the internal states of two sparse matrices. More...

Detailed Description

template<class T>
class jem::numeric::SparseMatrix< T >

The template class SparseMatrix can be used to store and manipulate sparse matrices containing elements of type T. An instance of the SparseMatrix class encapsulates three arrays that contain the locations and the values of the non-zero matrix elements. The first array, called the column index array, stores the column indices of the non-zero elements. The second array, called the row offset array, stores the starting position of each row in the column index array. The third array, called the value array, stores the values of the non-zero matrix elements. This array is ordered in the same way as the column index array.

The column index array and the offset array are encapsulated by a SparseStructure object that is a member of a SparseMatrix object. The documentation of the SparseStructure class explains in more detail how the locations of the non-zero matrix elements are encoded by the column index and offset arrays.

Consider the following (5x5) sparse matrix:

[ 0, 1, 0, 0, 4 ]
[ 2, 0, 3, 0, 0 ]
[ 0, 0, 0, 0, 0 ]
[ 0, 0, 1, 2, 3 ]
[ 7, 3, 0, 0, 0 ]

The corresponding column index array, value array and row offset array are given by:

indices = [ 1, 4, 0, 2, 2, 3, 4, 0, 1 ]
values  = [ 1, 4, 2, 3, 1, 2, 3, 7, 3 ]
offsets = [ 0, 2, 4, 4, 7, 9 ]

Note that the column indices do not have to be stored in ascending order. Thus, the index and value arrays in the example above can also be stored as:

indices = [ 4, 1, 0, 2, 4, 2, 3, 1, 0 ]

values = [ 4, 1, 2, 3, 3, 1, 2, 3, 7 ]

The next code fragment demonstrates how to access the contents of a SparseMatrix.

// This function computes a sparse matrix-vector product
Array<double>                  multiply
  ( const SparseMatrix<double>&  lhs,
    const Array<double>&         rhs )
{
  const int             rowCount = lhs.size(0);
  const Array<int>&     offsets ( lhs.getRowOffsets()    );
  const Array<int>&     indices ( lhs.getColumnIndices() );
  const Array<double>&  values  ( lhs.getValue()         );
  Array<double>         result  ( rowCount );
  double x;
  int    i, j, n;
  for ( i = 0; i < rowCount; i++ )
  {
    x = 0.0;
    j = offsets[i];
    n = offsets[i + 1];
    for ( ; j < n; j++ )
    {
      x += values[j] * rhs[ indices[j] ];
    }
    
    result[i] = x;
  }
  return result;
}

In addition to the SparseMatrix member functions, the package jem.numeric provides many other non-member functions that operate on SparseMatrix objects. More information is available in the following sections:

SparseMatrix expressions - a collection of overloaded operators that implement sparse matrix addition, substraction, and a other operations.

SparseMatrix assignment operators - a collection of additional assignment operators.

Sparse matrix-matrix and matrix-vector multiplication - a set of functions that implement sparse matrix-matrix and sparse matrix-vector multiplications.

Sparse matrix utility functions - a collection of handy functions that operate on sparse matrices and sparse structures [NOT YET DOCUMENTED].

See also: SparseStructure, SparseLU

Member Typedef Documentation

template<class T >

typedef SparseStructure jem::numeric::SparseMatrix< T >::Structure

A type representing the structure of a sparse matrix. It is an alias for SparseStructure.

template<class T >

typedef Structure::Shape jem::numeric::SparseMatrix< T >::Shape

A type representing the shape of a sparse matrix. It is an alias for Tuple<int,2>. The first element in the tuple equals the number of rows, and the second element equals the number of columns.

Constructor & Destructor Documentation

template<class T >

jem::numeric::SparseMatrix< T >::SparseMatrix ( )

Constructs an empty sparse matrix.

Postcondition: this->size(0) == 0 && this->size(1) == 0

template<class T >

jem::numeric::SparseMatrix< T >::SparseMatrix ( const Structure & s )

explicit

Constructs a sparse matrix with structure s. This constructor is equivalent with:

SparseMatrix ( s, Array<T>( s.nonZeroCount() ) )

Precondition: The type T has a default constructor.

See also: SparseMatrix( const Structure&, const Array<T>& )

template<class T >

jem::numeric::SparseMatrix< T >::SparseMatrix	(	const Structure &	s,
		const Array< T > &	values
	)

Constructs a sparse matrix given the structure s and the value array values. Since both s and values are copied by reference, this sparse matrix object points to the same data as s and values. Any modifications to these two objects will therefore be visible in this sparse matrix, and the other way around.

Parameters

s	- a `SparseStructure` representing the non-zero pattern of this sparse matrix.
values	- an `Array` containing the values of the non-zero elements in this sparse matrix.

Precondition: s.nonZeroCount() == values.size()
and the type T has a default constructor.

Postcondition: equal( this->shape(), s.shape() ) && equal( this->getRowOffsets(), s.getRowOffsets() ) && equal( this->getColumnIndices(), s.getColumnIndices() ) && equal( this->getValues(), values )

template<class T >

jem::numeric::SparseMatrix< T >::SparseMatrix	(	const Shape &	sh,
		const Array< int > &	offsets,
		const Array< int > &	indices
	)

Constructs a sparse matrix with shape sh, row offset array offsets and column index array indices. This constructor is equivalent with:

SparseMatrix ( Structure( sh, offsets, indices ) )

Precondition: The type T has a default constructor.

See also: SparseMatrix( const Structure& )

template<class T >

jem::numeric::SparseMatrix< T >::SparseMatrix	(	const Shape &	sh,
		const Array< int > &	offsets,
		const Array< int > &	indices,
		const Array< T > &	values
	)

Constructs a sparse matrix with shape sh, row offset array offsets, column index array indices and values values. This constructor is equivalent with:

SparseMatrix ( Structure( sh, offsets, indices ), values )

Precondition: The type T has a default constructor.

See also: SparseMatrix( const Structure&, const Array<T>& )

template<class T >

jem::numeric::SparseMatrix< T >::SparseMatrix ( const SparseMatrix< T > & rhs )

Creates a shallow copy of the rhs sparse matrix. Consequently, this sparse matrix points to the same data as the rhs sparse matrix. Any modifications to this sparse structure will therefore be visible in the rhs sparse structure, and the other way around.

The data shared between two or more sparse matrix objects is deallocated when the last sparse matrix pointing to that data is destroyed.

Because of the shallow copy semantics, returning a sparse matrix from a function is a relatively cheap operation.

Parameters

rhs	- the `SparseMatrix` to be copied.

Postcondition: equal( this->shape(), rhs.shape() ) && equal( this->getRowOffsets(), rhs.getRowOffsets() ) && equal( this->getColumnIndices(), rhs.getColumnIndices() ) && equal( this->getValues(), rhs.getValues() )

Member Function Documentation

template<class T >

SparseMatrix& jem::numeric::SparseMatrix< T >::operator= ( const SparseMatrix< T > & rhs )

Like the copy constructor, the assignment operator has shallow copy semantics. This means that after invoking the assignment operator, this sparse matrix points to the same data as the rhs spare matrix. The current contents of this sparse structure are deleted if no other sparse structures point to the same data.

Parameters

rhs	- the `SparseMatrix` to be copied.

Postcondition: equal( this->shape(), rhs.shape() ) && equal( this->getRowOffsets(), rhs.getRowOffsets() ) && equal( this->getColumnIndices(), rhs.getColumnIndices() ) && equal( this->getValues(), rhs.getValues() )

template<class T >

void jem::numeric::SparseMatrix< T >::swap ( SparseMatrix< T > & rhs )

Swaps the internal state of this sparse matrix with that of the rhs sparse matrix.

Parameters

rhs	- a `SparseMatrix` object.

template<class T >

SparseMatrix jem::numeric::SparseMatrix< T >::clone ( ) const

Returns a deep copy of this sparse matrix.

Returns: SparseMatrix ( this->getStructure().clone(), this->getValues().clone() )

template<class T >

SparseMatrix jem::numeric::SparseMatrix< T >::transpose ( ) const

Returns the transpose of this sparse matrix. The returned sparse matrix object does not share its data with this sparse matrix.

Returns: The transpose of this sparse matrix.

template<class T >

Structure jem::numeric::SparseMatrix< T >::getStructure ( ) const

Tests whether the structure of this sparse matrix is valid. This function has the same effect as:

return getStructure().isValid()

Returns: true if the structure of this matrix is valid, and false otherwise.

Returns the structure of this sparse matrix.

Returns a SparseStructure representing the non-zero pattern of this sparse matrix.

Returns: A SparseStructure representing the structure of this sparse matrix.

template<class T >

int jem::numeric::SparseMatrix< T >::nonZeroCount ( ) const

Returns the number of non-zero elements in this sparse matrix.

Returns: this->getValues().size()

template<class T >

Shape jem::numeric::SparseMatrix< T >::shape ( ) const

Returns a Tuple<int,2> that represents the shape of this matrix. The first element in this tuple equals the number of rows, while the second element equals the number of columns.

Returns: The shape of this sparse matrix.

template<class T >

int jem::numeric::SparseMatrix< T >::size ( int dim ) const

Returns the size of this sparse matrix in the dimension dim. Thus, size(0) returns the number of rows, while size(1) returns the number of columns.

Parameters

dim	- the dimension index.

Precondition: dim >= 0 && dim < 2

Returns: this->shape()[dim]

template<class T >

const Array<int>& jem::numeric::SparseMatrix< T >::getRowOffsets ( ) const

Returns a const reference to the row offset array of this sparse matrix. The reference is valid until the destructor of this sparse matrix is invoked.

Returns: this->getStructure().getRowOffsets()

template<class T >

const Array<int>& jem::numeric::SparseMatrix< T >::getColumnIndices ( ) const

Returns a const reference to the column index array of this sparse matrix. The reference is valid until the destructor of this sparse matrix is invoked.

Returns: this->getStructure().getColumnIndices()

template<class T >

Array<int> jem::numeric::SparseMatrix< T >::getColumnIndices ( int i ) const

Returns an integer array containing the column indices of the non-zero matrix elements on row i. The returned array shares its data with the column index array of this sparse matrix.

Parameters

i	- a valid row index.

Precondition: i >= 0 && i < this->size(0)

Returns: this->getStructure().getColumnIndices(i)

template<class T >

const Array<T>& jem::numeric::SparseMatrix< T >::getValues ( ) const

Returns a const reference to the value array of this sparse matrix. The reference is valid until the destructor of this sparse matrix is invoked.

Returns: The value array of this sparse matrix.

template<class T >

Array<T> jem::numeric::SparseMatrix< T >::getValues ( int i ) const

Returns an array containing the values of the non-zero elements on row i. The returned array shares its data with the value array of this sparse matrix.

This function is equivalent with:

const int first = getRowOffsets()[i];
const int last  = getRowOffsets()[i + 1];
return getValues()[ slice(first,last) ];

Parameters

i	- a valid row index.

Precondition: i >= 0 && i < this->size(0)

Returns: The values of the non-zero elements on row i.

Friends And Related Function Documentation

template<class T >

io::DataInput & operator>>	(	io::DataInput &	in,
		SparseMatrix< T > &	a
	)

Parameters

in	- a data input stream.
a	- the `SparseMatrix` to be read.

Returns: in

Exceptions

io::IOException	- if an I/O error occurs.
io::SerializationException	- if the input data are inconsistent.

Precondition: The type T provides a de-serialization operator.

template<class T >

io::DataOutput & operator<<	(	io::DataOutput &	out,
		const SparseMatrix< T > &	a
	)

Parameters

out	- a data output stream.
a	- the `SparseMatrix` to be written.

Returns: out

Exceptions

io::IOException - if an I/O error occurs.

Precondition: The type T provides a serialization operator.

template<class T >

io::TextOutput & operator<<	(	io::TextOutput &	out,
		const SparseMatrix< T > &	a
	)

Parameters

out	- a text output stream.
a	- the `SparseMatrix` to be written.

Returns: out

Exceptions

io::IOException - if an I/O error occurs.

Precondition: The type T provides a print operator.

template<class T >

void swap	(	SparseMatrix< T > &	lhs,
		SparseMatrix< T > &	rhs
	)

lhs.swap( rhs )

Parameters

lhs	- a `SparseMatrix` object.
rhs	- another `SparseMatrix` object.

Public Types

Public Member Functions

Related Functions

Detailed Description

template<class T> class jem::numeric::SparseMatrix< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

template<class T>
class jem::numeric::SparseMatrix< T >