Implement Compressed Column Sparse Matrix Format (CSC)

Problem

Convert a dense matrix to Compressed Sparse Column (CSC) format. Return three arrays: values (non-zero elements column-wise), row_indices (row index of each non-zero element), and col_ptr (index in values where each column starts).

Solution

def dense_to_csc(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0

    values = []
    row_indices = []
    col_ptr = [0]

    for j in range(cols):
        for i in range(rows):
            if matrix[i][j] != 0:
                values.append(matrix[i][j])
                row_indices.append(i)
        col_ptr.append(len(values))

    return values, row_indices, col_ptr

Explanation

1. Iterate column-by-column through the matrix.
2. For each non-zero element in the column, store its value and row index.
3. After processing each column, record the cumulative count of non-zero elements in col_ptr.
4. col_ptr[j] to col_ptr[j+1] gives the range of indices in values and row_indices for column j.
5. CSC is the column-oriented counterpart to CSR, efficient for column slicing and sparse matrix arithmetic.

Complexity

• Time: O(m * n) where m is rows and n is columns
• Space: O(nnz) where nnz is the number of non-zero elements