Sparse Matrices

Table of Contents

• CSC format
• Exporting to CSC in MATLAB

CSC format

Sparse matrix in C are formated in the compressed sparse column format.

Let $A\in\mathbb{R}^{m\times n}$ be a sparse matrix with $q$ nonzero elements.

The compressed sparse column, henceforth CSC, representation of $A$ is the triplet $(a, I, J)$ where

• $a$ is an array of length $q$ with the nonzero entries of $A$ in column-major order,
• $I$ is an array of length $n+1$ defined recursively in the following fashion
  • $I_0 = 0$
  • $I_{k+1} = I_{k} + \text{nonzeros in } k\text{-th column of } A$
• $J$ contains the row indices of the nonzero elements in $A$.

Let us give a comprehensive example...

Consider the following sparse matrix

$$\begin{eqnarray*} A &=& \begin{bmatrix} 0.3\\ & 0.7\\ && 0.2\\ -0.5 & 0.9 \end{bmatrix} \end{eqnarray*}$$

We shall derive the CSC representation of $A$.

We have $m=4$, $n=3$ and we count $q=5$ nonzero elements.

Traversing $A$ in column-major order, we have $a = (0.3, -0.5, 0.7, 0.9, 0.2)$.

$I$ is an array of length $n+1=4$; it is constructed recursively as follows:

• $I_0=0$
• $I_1=I_0 + \text{nonzeros in first column} = I_0 + 2 = 2$
• $I_2=I_1 + \text{nonzeros in second column} = I_1 + 2 = 4$
• $I_3=I_1 + \text{nonzeros in second column} = I_2 + 1 = 5$

Note that the last element of $I$ is the number of nonzero elements of the original matrix.

Lastly, $J$ is constructed as follows:

• $J_0 = \text{row coordinate of }a_0 = 0$
• $J_1 = \text{row coordinate of }a_1 = 3$
• $J_2 = \text{row coordinate of }a_2 = 1$
• $J_3 = \text{row coordinate of }a_3 = 3$
• $J_4 = \text{row coordinate of }a_4 = 2$

Exporting to CSC in MATLAB

In MATLAB, you may compute the CSC representation of a matrix A as follows:

[I,~,a] = find(sparse(A)); I = I - 1;
J = [0 cumsum(full(sum(A~=0)))];

For convenience, SuperSCS implements the MATLAB function sparse_to_csc with which you may convert a sparse matrix into its CSC format.

The function signature is:

[m, n, nnz, a, I, J] = sparse_to_csc(A);

Note that you first need to run make_scs (see the installation page).

Here is an example of use:

A = [0.3 0 0 ; 0 0.7 0; 0 0 0.2; -0.5 0.9 0];
A = sparse(A);
[m, n, nnz, a, I, J] = sparse_to_csc(A);

This will return:

m = 4
n = 3
nnz = 5
a =
    0.3000
   -0.5000
    0.7000
    0.9000
    0.2000

I =
     0
     2
     4
     5

J = 
     0
     3
     1
     3
     2

See Also

Saving and Loading Problems