12 June 2024

Batch Insert CSC sparse Matrix in Armadillo C++

  1. Primer on Compressed Sparse Column Matrices
    1. Column offset
    2. Row Indices
    3. Values
  2. Armadillo Code

Primer on Compressed Sparse Column Matrices

First, I would recommend reading NVIDIA's post on it. You need 3 elements.

Column offset

This was the most confusing for me at first. This is sort of a vector that holds the index to the row indices vector. The first value is always a zero as a result of this fact; it points to the first element in the row indices vector. If the first column has 2 non-zero values, the first two elements of this vector would be [0, 2].

Another way to think about it; it is a counter for the number of non-zero values encountered so far. Refer to the graphic in the NVIDIA post. When it comes to the 3 element of the column offset vector, the value is 5. There are a total of 5 non-zero elements up until the start of the 3 column!

The length of this vector matches the total number of columns, not values! This is easy to implement in code.

Row Indices

For each non-zero value, which row index was it in? Extracting a indices of non-zero elements from a vector is easy, and I will show the code.

Values

This is straight forward. What is the non-zero value. The length of the values vector and row indices vector must match.

Armadillo Code

If you haven't already, refer to the Armadillo documentation. We will be using the form 4 of the batch insertion constructor.

sp_mat(rowind, colptr, values, n_rows, n_cols, check_for_zeros = true)

Shortly, you need to have std::vector for values, row indices and column offset.

std::vector<arma::uword> rowind;
std::vector<arma::uword> colptr;
std::vector<double> values;

In my example, I have a std::map where each pair is a key with a arma::vec. It is likely different from how you the reader, are going about it. Here is how I went about populating the 3 vectors.

for (auto& [key, my_vector] : vector_map) {
    arma::uvec row_indices = arma::find(my_vector > 0);
    colptr.push_back(colptr.back() + row_indices.n_elem);
    for (auto& idx : row_indices) {
        rowind.push_back(idx);
        values.push_back(my_vector(idx));
    }
}

And finally, to construct the sparse matrix in record time!

    arma::colvec values_vec = arma::conv_to<arma::colvec>::from(values);
    arma::uvec rowind_vec = arma::conv_to<arma::uvec>::from(rowind);
    arma::uvec colptr_vec = arma::conv_to<arma::uvec>::from(colptr);
    arma::sp_mat final_matrix(rowind_vec, colptr_vec, values_vec, a_matrix.n_rows, a_matrix.n_cols, false);

Hope it helped you. Feel free to leave a Disqus comment below.

Tags: cpp R