🧮 Sparse Matrices

After completing this level, you should be able to:

• Identify when a matrix should be treated as sparse.
• Compare dense storage with triplet, CSR and CSC representations.
• Construct row pointers and column pointers correctly.
• Transpose a sparse matrix using the simple and fast methods.
• Add compatible sparse matrices by merging ordered terms.
• Explain sparse-matrix multiplication and its practical uses.
• Analyze storage requirements and operation complexity.

A matrix is called sparse when most of its elements are zero. Instead of storing every zero, a sparse representation stores only the non-zero values and enough position information to reconstruct the matrix.

Every non-zero term is stored as (row, column, value). A header may additionally store the matrix dimensions and the number of non-zero terms.

CSR stores non-zero terms row by row using three arrays:

CSC is the column-oriented counterpart of CSR. It stores:

The transpose Aᵀ changes an m × n matrix into an n × m matrix, with Aᵀ[j][i] = A[i][j].

Two matrices can be added only when they have identical dimensions. If their triplets are sorted by (row, column), addition resembles merging two sorted arrays.

For A(m × n) × B(n × p), a result entry C[i][j] is formed from matching column indices of row i in A and row indices of column j in B. Efficient implementations commonly use CSR for A and CSC for B.

The first triplet stores rows, columns and nnz. The algorithm counts original columns and uses starting positions to build an ordered transpose.

#include <stdio.h>

#define MAX_TERMS 100
#define MAX_COLS 50

typedef struct {
    int row, col, value;
} Term;

void fastTranspose(Term a[], Term b[]) {
    int rows = a[0].row;
    int cols = a[0].col;
    int terms = a[0].value;
    int count[MAX_COLS] = {0};
    int start[MAX_COLS];

    b[0] = (Term){cols, rows, terms};
    for (int i = 1; i <= terms; i++)
        count[a[i].col]++;

    start[0] = 1;
    for (int i = 1; i < cols; i++)
        start[i] = start[i - 1] + count[i - 1];

    for (int i = 1; i <= terms; i++) {
        int position = start[a[i].col]++;
        b[position] = (Term){a[i].col, a[i].row, a[i].value};
    }
}

int main(void) {
    Term a[MAX_TERMS], b[MAX_TERMS];
    scanf("%d %d %d", &a[0].row, &a[0].col, &a[0].value);
    for (int i = 1; i <= a[0].value; i++)
        scanf("%d %d %d", &a[i].row, &a[i].col, &a[i].value);

    fastTranspose(a, b);
    printf("%d %d %d\n", b[0].row, b[0].col, b[0].value);
    for (int i = 1; i <= b[0].value; i++)
        printf("%d %d %d\n", b[i].row, b[i].col, b[i].value);
    return 0;
}

4 5 5
0 2 5
1 0 8
1 3 7
2 1 6
3 4 9

5 4 5
0 1 8
1 2 6
2 0 5
3 1 7
4 3 9

Trace column counting, starting-position calculation and placement of all five non-zero terms.

b[0] = (Term){cols, rows, terms};
for (i = 1; i <= terms; i++)
    count[a[i].col]++;
start[0] = 1;
start[i] = start[i - 1] + count[i - 1];
position = start[a[i].col]++;
b[position] = {a[i].col, a[i].row, a[i].value};

row col value

• A sparse matrix contains mostly zero values; nnz counts its non-zero terms.
• Triplet/COO stores (row, column, value) for each non-zero term.
• CSR uses values, columnIndex and rowPointer arrays.
• CSC uses values, rowIndex and columnPointer arrays.
• Fast transpose takes O(columns + nnz) time.
• Ordered sparse addition merges terms in O(nnzA + nnzB) time.
• Sparse multiplication may create fill-in and a denser result.
• Choose a format according to access direction, update needs and actual sparsity.