CSR Matrix

template<typename ElemType>
class CSRMatrix : public mocca::MatrixBase<CSRMatrix<ElemType>>

One of the basic types within MOCCA. The CSRMatrix implement a variant of the widely-used Compressed Sparse Row (CSR) scheme, storing only the non-zero elements. See CSR Matrix in Basic Datatypes for more details.

Template Parameters:

  • ElemType - Type of the nonzero elements

Constructor

CSRMatrix()

Default Constructor. Creates an empty CSRMatrix (with cols() == 0 and rows() == 0).

Complexity: Constant

CSRMatrix(index_t nrows, index_t ncols)

Creates a CSRMatrix filled with zeros.

Complexity: Constant

Parameters:

  • ncols – [in] number of columns

  • nrows – [in] number of rows

CSRMatrix(index_t nrows, index_t ncols, index_t nz)

Creates a CSRMatrix and reserves space in the container for nz entries.

Complexity: Constant

Note

This constructor only reserves memory space, but does not initialise the nonzero entries. Use either fill_*, insert or the at_ref routines to assign values to these entries.

Parameters:

  • ncols – [in] number of columns

  • nrows – [in] number of rows

  • nz – [in] reserved size for non-zeros elements

template<typename OtherElemType>
CSRMatrix(const CSRMatrix<OtherElemType> &other)

Copy Constructor. Creates a CSRMatrix and then copies the content from other.

Complexity: Linear in other.size()

Parameters:

other – [in] another CSRMatrix to use as data source

CSRMatrix(const CSRMatrix &other)

Copy Constructor. Creates a CSRMatrix and then copies the content from other.

Complexity: Linear in other.size()

Parameters:

other – [in] another CSRMatrix to use as data source

CSRMatrix(CSRMatrix &&other) noexcept

Move Constructor. Creates an CSRMatrix and then moves the content from other, following the move semantics (i.e., the data is moved from other to this container). other is valid but left in a unspecified state afterwards.

Complexity: Constant

Parameters:

other – [in] another CSRMatrix to use as data source

template<typename E>
CSRMatrix(const MatrixBase<E> &expr)

Creates a CSRMatrix from an expression.

Complexity: Linear in this->size()

Parameters:

expr – [in] an expression

Throws:

std::length_error – if the dimensions of the operands in``expr`` do not match and cannot be broadcasted.

Destructor

virtual ~CSRMatrix() = default

Default Destructor. Complexity: Constant

Assignment

CSRMatrix &operator=(const CSRMatrix &other)

Copy Assignment Operator. Replaces the container’s content with the contents of other.

Complexity: Linear in other.size()

Parameters:

other – [in] another CSRMatrix to use as data source

Returns:

*this

template<typename OtherElemType>
CSRMatrix &operator=(const CSRMatrix<OtherElemType> &other)

Copy Assignment Operator. Replaces the container’s content with the contents of other.

Complexity: Linear in other.size()

Parameters:

other – [in] another CSRMatrix to use as data source

Returns:

*this

CSRMatrix &operator=(CSRMatrix &&other) noexcept

Move Assignment Operator. Replaces the container’s content with the contents of other, following the move semantics (i.e., the data is moved from other to this container). other is valid but left in a unspecified state afterwards.

Complexity: Constant

Parameters:

other – [in] another CSRMatrix to use as data source

Returns:

*this

template<typename E>
CSRMatrix &operator=(const MatrixBase<E> &expr)

Evaluates the matrix expression and assign the result to the CSRMatrix. This routine automatically resizes the CSRMatrix to match the expression dimensions. If the expression contains aliasing, this routine may use additional memory.

Complexity: Linear in expr.size()

Parameters:

expr – [in] a matrix expression

Throws:

std::length_error – if the dimensions of the operands in``expr`` do not match and cannot be broadcasted.

Returns:

*this

template<typename InIter, internal::require_input_iterator<InIter> = true>
void fill_sorted(InIter first, InIter last)

Fills the CSRMatrix based on the triplets defined in the range [first, last[. The entries in the range must be sorted by row and then by col in ascending order and cannot contain duplicates.

A triplet is a tuple (row, col, value) defining a nonzero entry in the matrix. The triplet should be a simple structure with the following interface: 

template<typename T>
   struct triplet {
    index_t row, col;
    T val;
};

Complexity: Linear in std::distance(first, last)

See also SparseTriplet, fill_sorted_by_col and fill_unsorted.

Note

The matrix must be properly sized beforehand either with the CSRMatrix(index_t, index_t) constructor or the resize() method.

Parameters:

  • first – [in] iterator to the first entry in the range

  • last – [in] iterator to the ‘past-the-end’ entry in the range

Throws:

  • std::out_of_range – if a triplet is outside of matrix.

  • std::runtime_error – if the CSRMatrix was not properly initialized from the triplet range

template<typename InIter, internal::require_input_iterator<InIter> = true>
void fill_sorted_by_col(InIter first, InIter last)

Fills the CSRMatrix based on the triplets defined in the range [first, last[. The range can be unsorted as long as the entries for the same row have ascending columns and do not contain duplicates. For example, 

(row, col, val)
(1, 2, 40)
(2, 6, 50)
(1, 5, 30)
(1, 10, 10)
...

A triplet is a tuple (row, col, value) defining a nonzero entry in the matrix. The triplet should be a simple structure with the following interface: 

template<typename T>
   struct triplet {
    index_t row, col;
    T val;
};

Complexity: Linear in std::distance(first, last)

See also SparseTriplet, fill_sorted_by_col and fill_unsorted.

Note

The matrix must be properly sized beforehand either with the CSRMatrix(index_t, index_t) constructor or the resize() method.

Parameters:

  • first – [in] iterator to the first entry in the range

  • last – [in] iterator to the ‘past-the-end’ entry in the range

Throws:

  • std::out_of_range – if a triplet is outside of matrix.

  • std::runtime_error – if the CSRMatrix was not properly initialized from the triplet range

template<typename InIter, typename Op = std::plus<>, internal::require_input_iterator<InIter> = true>
void fill_unsorted(InIter first, InIter last, Op acc_func = std::plus<>())

Fills the CSRMatrix based on the triplets defined in the range [first, last[. If the routine encounters a duplicate entry in the range, it will call acc_func to combine it with the previous entry. The triplet range do not need to sorted.

A triplet is a tuple (row, col, value) defining a nonzero entry in the matrix. The triplet should be a simple structure with the following interface: 

template<typename T>
   struct triplet {
    index_t row, col;
    T val;
};

Complexity: \( O(n log n_r) \) with n = std::distance(first, last) and \( n_r \), the average number of nonzeros per row

See also SparseTriplet, fill_sorted_by_col and fill_unsorted.

Note

The matrix must be properly sized beforehand either with the CSRMatrix(index_t, index_t) constructor or the resize() method.

Parameters:

  • first – [in] iterator to the first entry in the range

  • last – [in] iterator to the ‘past-the-end’ entry in the range

  • acc_func – [in] callable object for combining duplicate entries (default: std::plus)

Throws:

  • std::out_of_range – if a triplet is outside of matrix.

  • std::runtime_error – if the CSRMatrix was not properly initialized from the triplet range

template<typename Filter>
void fill_filter_row(const CSRMatrix &other, Filter filter)

Filters the rows of other according with some function and then assign the results to this container. The filter function must receive the index of the row and then returns a boolean indicating if is included or not. The container will be set to the dimensions of other.

Complexity: Linear in other.rows()

Parameters:

  • other[in] – other CSRMatrix to use as data source

  • filter[in] – the filter function

void set_eye(index_t n)

Transforms the CSRMatrix into the identity matrix.

Parameters:

n – [in] matrix size Complexity: Linear in this->rows()

template<typename E>
void set_diagonal(const MatrixBase<E> &expr)

Transforms the CSRMatrix into diagonal matrix whose entries are determined by expr. The final matrix dimensions are determined by the expr.size() and it is always square.

Complexity: Linear in expr.size()

Parameters:

expr – [in] vector expression to use as data source

void set_diagonal(index_t count, ElemType scalar)

Transforms the CSRMatrix into diagonal matrix whose entries are equal to a constant value. The final matrix is always square.

Complexity: Linear in count

Parameters:

  • count – [in] the number of entries in the diagonal

  • scalar – [in] scalar to use as data source

Internal Buffers

Warning

These routines aims to provide interoperability to other libraries. Changing the properties of the internal buffers (e.g., its size) may result in undefined behaviour.

index_t *row_offset_ptr() noexcept

Complexity: Constant

Returns:

raw pointer to the row offset buffer (i.e., a buffer containing the index of the first nonzero element in each row for the columns() and nonzeros() containers).

index_t *columns_ptr() noexcept

Complexity: Constant

Returns:

raw pointer to the buffer containing the column of each nonzero element in the CSRMatrix).

ElemType *nonzeros_ptr() noexcept

Complexity: Constant

Returns:

raw pointer to buffer with values of each nonzero element in the CSRMatrix.

index_t *nz_per_row_ptr() noexcept

Complexity: Constant

Returns:

raw pointer to buffer that counts the number of nonzero entries per row. If the CSRMatrix is on compressed mode, this routine returns a nullptr.

Array<index_t> &row_offset() noexcept

Complexity: Constant

Returns:

the internal buffer containing the index of the first nonzero element in each row for the columns() and nonzeros() containers.

Array<index_t> &columns() noexcept

Complexity: Constant

Returns:

the internal buffer containing the column of each nonzero element in the CSRMatrix).

Array<ElemType> &nonzeros() noexcept

Complexity: Constant

Returns:

the internal buffer with values of each nonzero element in the CSRMatrix).

Array<index_t> &nz_per_row() noexcept

Complexity: Constant

Returns:

the internal buffer that counts the number of nonzero entries per row. If the CSRMatrix is on compressed mode, this routine returns an empty container.

Iterator

iterator begin() noexcept

Complexity: Constant

Returns:

an iterator to the begin of the CSRMatrix

iterator end() noexcept

Complexity: Constant

Returns:

an iterator to past-the-end element of the CSRMatrix

const_iterator cbegin() const noexcept

Complexity: Constant

Returns:

a const iterator to the begin of the CSRMatrix

const_iterator cend() const noexcept

Complexity: Constant

Returns:

a const iterator to past-the-end element of the CSRMatrix

Element Access

ElemType &operator[](index_t idx)

Accesses the nonzero element at (idx) position. In this case, the indexing only includes the nonzero elements.

Complexity: Constant

Returns:

reference to the value of the requested element

ElemType operator[](index_t idx) const

Accesses the nonzero element at (idx) position. In this case, the indexing only includes nonzeros elements.

Complexity: Constant

Returns:

the requested element

index_t index_at(index_t pos) const

Accesses the index of the nonzero element at (pos) position. In this case, the indexing only includes nonzeros elements.

Complexity: Constant

Returns:

the index of requested element

SparseTriplet<ElemType> nonzero_at(index_t idx) const

Accesses the nonzero element at (idx). In this case, the indexing only includes nonzeros elements.

Complexity: O(log(this->rows())) (binary search)

Returns:

a SparseTriplet containing the element value, row index and column index

ElemType operator()(index_t row, index_t col) const

Accesses the CSRMatrix element at (row, col).

Complexity: O(log(n)) (binary search), with n = number of nonzeros elements in the row

Warning

This routine do not create new elements. Modifying the value of a zero entry will have no effect on the container. To create a new nonzero entry, use either insert() or at_ref().

Parameters:

  • row – [in] row of the requested element

  • col – [in] column of the requested element

Returns:

the requested element

ElemType at(index_t row, index_t col) const

Accesses the CSRMatrix element at (row, col).

Complexity: O(log(n)) (binary search), with n = number of nonzeros elements in the row

Warning

This routine do not create new elements. Modifying the value of a zero entry will have no effect on the container. To create a new nonzero entry, use either insert() or at_ref().

Parameters:

  • row – [in] row of the requested element

  • col – [in] column of the requested element

Returns:

the requested element

ElemType &at_ref(index_t row, index_t col)

Accesses the CSRMatrix element at (row, col).

Complexity: O(log(n)) (binary search), with n = number of nonzeros elements in the row, plus the cost of insert(), if the element do not exist.

Note

If the element do not exists in the container, this routine will insert a new element in (row, col) and then return a reference to the newly created entry.

Parameters:

  • row – [in] row of the requested element

  • col – [in] column of the requested element

Returns:

a reference to the value of the requested element

Capacity

constexpr index_t rows() const noexcept

Complexity: Constant

Returns:

the number of rows in the CSRMatrix

constexpr index_t cols() const noexcept

Complexity: Constant

Returns:

the number of columns in the CSRMatrix

constexpr index_t size() const noexcept

Complexity: Constant

Returns:

the number of nonzeros entries in the CSRMatrix

void reserve(index_t nonzeros)

Reserves space in memory for nonzeros elements, clearing the CSRMatrix content. If nonzeros is less than the allocated capacity, this routine only clears the content from CSRMatrix.

Complexity: Constant

Parameters:

nonzeros – [in] reserved size

template<typename SizesVec>
void reserve(SizesVec &vec)

Reserves space for nonzeros entries in each row according to the vec content (i.e., reserve vec[i] for each row i with i = [0, rows()[). The resulting matrix will be on the uncompressed mode. This will clear any previous content in the matrix.

The vec object must support input iterators and expose the following interface: 

iterator begin();   // iterator to the first element in the container
iterator end();     // iterator for the 'past-the-end' element in the container

Typical choices for vec includes std::vector<int>, mocca::Array<int>, etc.

Complexity: Linear in this->rows()

Parameters:

vec – [in] object with the number of nonzeros entries per row

Modifiers

CSRow<CSRMatrix<ElemType>> row(index_t r)

Complexity: Constant

Parameters:

r – [in] the index of the desired row

Returns:

the row r of the matrix

CSRow<const CSRMatrix<ElemType>> row(index_t r) const

Complexity: Constant

Parameters:

r – [in] the index of the desired row

Returns:

the row r of the matrix

void clear() noexcept

Clears all the nonzero entries of the CSRMatrix. This routine do not change the number of rows and columns of the matrix.

Complexity: Constant

void resize(index_t nrows, index_t ncols)

Resizes the CSRMatrix, changing the number of rows and columns to new_nrows and new_ncols, respectively. This routine will clear the matrix content.

Complexity: Linear in nrows.

Parameters:

  • nrows – [in] number of rows

  • ncols – [in] number of columns

void insert(index_t row, index_t col, ElemType val)

Inserts a new nonzero element at (row, col). This element must not exist on the CSRMatrix.

It is strongly recommended that the user reserves the necessary space in the matrix before inserting the elements. In particular, this routine is optimized for inserting the elements sorted by row indices and columns indices.

Using reserve(const SizesVec&) will reduce the cost for inserting out-of-the-order elements.

Complexity: Constant if the elements are inserted in order and the container is properly allocated. Linear in size(), otherwise.

Parameters:

  • row – [in] row of the inserted element

  • col – [in] column of the inserted element

  • val – [in] value of the inserted element

void compress()

Compress the CSRMatrix, removing any additional space between rows. This will also remove any additional memory allocation.

Complexity: Linear in this->size() at most.

constexpr bool is_compressed() const

Complexity: Constant

Returns:

true if the object is on compressed mode, false otherwise

void swap(CSRMatrix &other)

Swaps the CSRMatrix content with other, including any memory allocation.

Complexity: Constant

Parameters:

other – another CSRMatrix to exchange content with

TripletArray<ElemType> to_array()

Creates an TripletArray from a CSRMatrix.

Returns:

a copy of the data from the CSRMatrix in the TripletArray. Complexity: Linear in this->size()

void transpose_inplace()

Transpose CSRMatrix inplace. Complexity: Linear in this->size()

template<typename Filter>
void filter_values(Filter filter)

Filters the values of the CSRMatrix according to function specified in the filter. The filter function must receive the value of the nonzero element and then returns a boolean indicating if is included or not. The resulting CSRMatrix will be in the uncompressed mode.

Complexity: Linear in size().

Parameters:

filter – the filter function

template<typename T>
friend std::ostream &operator<<(std::ostream &stream, const CSRMatrix<T> &mat)

Stream Operator. Writes the content of the CSRMatrix on a given stream.

Complexity: Linear in this->size()

Parameters:

  • stream – [in] output stream (e.g., std::cout)

  • expr – [in] CSRMatrix

Returns:

stream

Sparse Triplet

template<typename T>
struct SparseTriplet

Simple struct that holds the row, col and value of a nonzero entry in the matrix. This object can be used to fill_sorted_by_col a CSRMatrix. You can use TripletArray for creating an array containing these objects.

Template Parameters:

  • T - Type of the value of the nonzero

Public Members

index_t row

Row of the non zero element.

index_t col

Column of the non zero element.

T val

Value of the non zero element.