OneNoughtOne
0/332
Loading content...
In computational mathematics and scientific computing, efficiently storing and manipulating sparse matrices—matrices where the majority of elements are zero—is critical for performance. One of the most widely used representations is the Column Compressed Sparse (CCS) format, also known as Compressed Sparse Column (CSC).
The CCS format dramatically reduces memory consumption by storing only non-zero elements and their positional metadata. This representation is particularly advantageous for column-slicing operations, matrix-vector products, and numerical algorithms that traverse matrices column by column.
Understanding CCS Format:
The CCS representation consists of three arrays:
Values Array: Contains all non-zero elements of the matrix, traversed in column-major order (column 0 first, then column 1, etc.).
Row Indices Array: For each value in the values array, records the row index where that element resides in the original matrix.
Column Pointers Array: An array of length (number of columns + 1) that indicates where each column begins in the values array. The difference between consecutive pointers gives the number of non-zeros in each column.
Traversal Logic:
To construct these arrays, iterate through each column of the matrix from left to right. Within each column, scan from top to bottom, collecting non-zero elements along with their row positions. The column pointer for each column indicates the cumulative count of non-zeros encountered so far.
Your Task:
Write a Python function that transforms a dense matrix (represented as a 2D list) into its CCS format. Return a tuple containing the three arrays: values, row indices, and column pointers.
dense_matrix = [
[0, 0, 3, 0],
[1, 0, 0, 4],
[0, 2, 0, 0]
][1, 2, 3, 4] [1, 2, 0, 1] [0, 1, 2, 3, 4]Explanation
**Step-by-step column traversal:** **Column 0:** - Row 0: 0 (skip), Row 1: 1 (store), Row 2: 0 (skip) - Values: [1], Row indices: [1] **Column 1:** - Row 0: 0 (skip), Row 1: 0 (skip), Row 2: 2 (store) - Values: [1, 2], Row indices: [1, 2] **Column 2:** - Row 0: 3 (store), Row 1: 0 (skip), Row 2: 0 (skip) - Values: [1, 2, 3], Row indices: [1, 2, 0] **Column 3:** - Row 0: 0 (skip), Row 1: 4 (store), Row 2: 0 (skip) - Values: [1, 2, 3, 4], Row indices: [1, 2, 0, 1] **Column pointers:** [0, 1, 2, 3, 4] - Column 0 starts at index 0 (1 element) - Column 1 starts at index 1 (1 element) - Column 2 starts at index 2 (1 element) - Column 3 starts at index 3 (1 element) - End marker at index 4
dense_matrix = [
[1, 0],
[0, 2]
][1, 2] [0, 1] [0, 1, 2]Explanation
This is a 2×2 diagonal matrix with non-zeros only on the main diagonal. **Column 0:** Row 0 has value 1 **Column 1:** Row 1 has value 2 Values: [1, 2] (column-major order) Row indices: [0, 1] (row positions of each value) Column pointers: [0, 1, 2] (each column has exactly 1 non-zero element)
dense_matrix = [
[1, 2, 0],
[0, 3, 4],
[5, 0, 6]
][1, 5, 2, 3, 4, 6] [0, 2, 0, 1, 1, 2] [0, 2, 4, 6]Explanation
**Detailed traversal of a denser matrix:** **Column 0:** Values 1 (row 0) and 5 (row 2) **Column 1:** Values 2 (row 0) and 3 (row 1) **Column 2:** Values 4 (row 1) and 6 (row 2) Values array: [1, 5, 2, 3, 4, 6] Row indices: [0, 2, 0, 1, 1, 2] Column pointers: [0, 2, 4, 6] - Column 0 starts at index 0 (2 elements: indices 0-1) - Column 1 starts at index 2 (2 elements: indices 2-3) - Column 2 starts at index 4 (2 elements: indices 4-5) - End marker at index 6 (total non-zeros)
Constraints