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