Implement Compressed Row Sparse Matrix (CSR) Format Conversion

Problem

Convert a dense matrix to Compressed Sparse Row (CSR) format. Return three arrays: values (non-zero elements), col_indices (column index of each non-zero element), and row_ptr (index in values where each row starts).

Solution

def dense_to_csr(matrix):
    values = []
    col_indices = []
    row_ptr = [0]

    for row in matrix:
        for j, val in enumerate(row):
            if val != 0:
                values.append(val)
                col_indices.append(j)
        row_ptr.append(len(values))

    return values, col_indices, row_ptr

Explanation

1. Iterate through each row of the matrix.
2. For each non-zero element, store its value and column index.
3. After processing each row, record the cumulative count of non-zero elements in row_ptr.
4. row_ptr[i] to row_ptr[i+1] gives the range of indices in values and col_indices for row i.
5. CSR is efficient for row-wise access and matrix-vector multiplication.

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