The compressed sparse row (CSR) or compressed row storage (CRS) or Yale format represents a matrix M by three (one-dimensional) arrays, that respectively contain nonzero values, the extents of rows, and column indices. It is similar to COO, but compresses the row indices, hence the name. This format allows fast row access and matrix-vector multiplications (Mx). The CSR format has been in use since at least the mid-1960s, with the first complete description appearing in 1967.[7] ,COO stores a list of (row, column, value) tuples. Ideally, the entries are sorted first by row index and then by column index, to improve random access times. This is another format that is good for incremental matrix construction.[6] ,LIL stores one list per row, with each entry containing the column index and the value. Typically, these entries are kept sorted by column index for faster lookup. This is another format good for incremental matrix construction.[5] ,The CSR format stores a sparse m × n matrix M in row form using three (one-dimensional) arrays (V, COL_INDEX, ROW_INDEX). Let NNZ denote the number of nonzero entries in M. (Note that zero-based indices shall be used here.)
V = [5 8 3 6] COL_INDEX = [0 1 2 1] ROW_INDEX = [0 1 2 3 4]
To extract a row, we first define:
row_start = ROW_INDEX[row] row_end = ROW_INDEX[row + 1]
Last Updated : 29 Jul, 2022
Examples:
Input: 0 0 0 0
5 8 0 0
0 0 3 0
0 6 0 0
Solution: When the matrix is read row by
row, the A vector is[5 8 3 6]
The JA vector stores column indices
of elements in A hence, JA = [0 1 2
1
].IA[0] = 0. IA[1] = IA[0] + no of non - zero elements in row 0
i.e 0 + 0 = 0.
Similarly,
IA[2] = IA[1] + 2 = 2
IA[3] = IA[2] + 1 = 3
IA[4] = IA[3] + 1 = 4
Therefore IA = [0 0 2 3 4]
The trick is remember that IA[i]
stores NNZ upto and not - including
i row.
Input: 10 20 0 0 0 0
0 30 0 4 0 0
0 0 50 60 70 0
0 0 0 0 0 80
Output: A = [10 20 30 4 50 60 70 80],
IA = [0 2 4 7 8]
JA = [0 1 1 3 2 3 4 5]Algorithm:
SPARSIFY(MATRIX)
Step 1: Set M to number of rows in MATRIX
Step 2: Set N to number of columns in MATRIX
Step 3: I = 0, NNZ = 0. Declare A, JA, and IA.
Set IA[0] to 0
Step 4: for I = 0...N - 1
Step 5: for J = 0...N - 1
Step 5: If MATRIX[I][J] is not zero
Add MATRIX[I][J] to A
Add J to JA
NNZ = NNZ + 1[End of IF]
Step 6: [End of J loop]
Add NNZ to IA
[End of I loop]
Step 7: Print vectors A, IA, JA
Step 8: END0 0 0 0 1 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 A = [1 5 8 3 6 1] IA = [0 1 3 4 6] JA = [4 0 1 2 1 4]
0 0 0 0 1 5 8 0 0 0 0 0 3 0 0 0 6 0 0 1 A = [1 5 8 3 6 1] IA = [0 1 3 4 6] JA = [4 0 1 2 1 4]
Compressed Sparse Column Format (CSC) Examples ,Compressed Sparse Row Format (CSR),Block Compressed Row Format (BSR), Collapse document to compact view
>>> mtx = sparse.csc_matrix((3, 4), dtype = np.int8) >>> mtx.todense() matrix([ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0] ], dtype = int8)
>>> row = np.array([0, 0, 1, 2, 2, 2]) >>>
col = np.array([0, 2, 2, 0, 1, 2]) >>>
data = np.array([1, 2, 3, 4, 5, 6]) >>>
mtx = sparse.csc_matrix((data, (row, col)), shape = (3, 3)) >>>
mtx <
3 x3 sparse matrix of type '<... '
numpy.int64 '>'
with 6 stored elements in Compressed Sparse Column format >
>>>
mtx.todense()
matrix([
[1, 0, 2],
[0, 0, 3],
[4, 5, 6]
]...) >>>
mtx.data
array([1, 4, 5, 2, 3, 6]...) >>>
mtx.indices
array([0, 2, 2, 0, 1, 2], dtype = int32) >>>
mtx.indptr
array([0, 2, 3, 6], dtype = int32)>>> data = np.array([1, 4, 5, 2, 3, 6]) >>> indices = np.array([0, 2, 2, 0, 1, 2]) >>> indptr = np.array([0, 2, 3, 6]) >>> mtx = sparse.csc_matrix((data, indices, indptr), shape = (3, 3)) >>> mtx.todense() matrix([ [1, 0, 2], [0, 0, 3], [4, 5, 6] ])
is the standard CSC representation where the row indices for column i are stored in indices[indptr[i]:indptr[i+1]] and their corresponding values are stored in data[indptr[i]:indptr[i+1]]. If the shape parameter is not supplied, the matrix dimensions are inferred from the index arrays.,Convert this matrix to Compressed Sparse Column format.,Convert this matrix to Compressed Sparse Row format.,Compressed Sparse Column matrix
>>>
import numpy as np
>>>
from scipy.sparse
import csc_matrix
>>>
csc_matrix((3, 4), dtype = np.int8).toarray()
array([
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
], dtype = int8)>>> row = np.array([0, 2, 2, 0, 1, 2]) >>> col = np.array([0, 0, 1, 2, 2, 2]) >>> data = np.array([1, 2, 3, 4, 5, 6]) >>> csc_matrix((data, (row, col)), shape = (3, 3)).toarray() array([ [1, 0, 4], [0, 0, 5], [2, 3, 6] ])
>>> indptr = np.array([0, 2, 3, 6]) >>> indices = np.array([0, 2, 2, 0, 1, 2]) >>> data = np.array([1, 2, 3, 4, 5, 6]) >>> csc_matrix((data, indices, indptr), shape = (3, 3)).toarray() array([ [1, 0, 4], [0, 0, 5], [2, 3, 6] ])
8.2.4 Compressed Sparse Column (CSC),The Compressed Sparse Row (CSR) format represents a sparse matrix using three arrays, which we denote by data, indices, and indptr. An example is shown in the following figure:,The Compressed Sparse Column (CSC) format is very similar to the CSR format, except that the role of rows and columns is swapped. The data array stores non-zero matrix elements in sequential order from top to bottom along each column, then from the left-most column to the right-most. The indices array stores row indices, and each element of the indptr array corresponds to one column of the matrix. An example is shown below:,To create a sparse matrix in the CSC format, we use the csc_matrix function. This is analogous to the csr_matrix function for CSR matrices. For example,
Here is an example program which constructs a LIL matrix, and prints it:
from scipy import * import scipy.sparse as sp A = sp.lil_matrix((4, 5)) # Create empty 4 x5 LIL matrix A[0, 1] = 1.0 A[1, 1] = 2.0 A[1, 2] = -1.0 A[3, 0] = 6.6 A[3, 4] = 1.4 # # Verify the matrix contents by printing it print(A)
When we run the above program, it displays the non-zero elements of the sparse matrix:
(0, 1) 1.0
(1, 1) 2.0(1, 2) - 1.0(3, 0) 6.6(3, 4) 1.4You can also convert the sparse matrix into a conventional 2D array, using the toarray method. Suppose we replace the line print(A) in the above program with
B = A.toarray() print(B)
You can create a sparse matrix in the DIA format, using the dia_matrix function, which is provided by the scipy.sparse module. Here is an example program:
from scipy import * import scipy.sparse as sp N = 6 # Matrix size diag0 = -2 * ones(N) diag1 = ones(N) A = sp.dia_matrix(([diag1, diag0, diag1], [-1, 0, 1]), shape = (N, N)) # # Verify the matrix contents by printing it print(A.toarray())
Here, the first input to dia_matrix is a tuple of the form (data, offsets), where data and offsets are arrays of the sort described above. This returns a sparse matrix in the DIA format, with the specified contents (the elements in data which lie outside the bounds of the matrix are ignored). In this example, the matrix is tridiagonal with -2 along the main diagonal and 1 along the +1 and -1 diagonals. Running the above program prints the following:
[ [-2. 1. 0. 0. 0. 0.] [1. - 2. 1. 0. 0. 0.] [0. 1. - 2. 1. 0. 0.] [0. 0. 1. - 2. 1. 0.] [0. 0. 0. 1. - 2. 1.] [0. 0. 0. 0. 1. - 2.] ]
To create a sparse matrix in the CSR format, we use the csr_matrix function, which is provided by the scipy.sparse module. Here is an example program:
from scipy
import *
import scipy.sparse as sp
data = [1.0, 2.0, -1.0, 6.6, 1.4]
rows = [0, 1, 1, 3, 3]
cols = [1, 1, 2, 0, 4]
A = sp.csr_matrix((data, [rows, cols]), shape = (4, 5))
print(A)Here, the first input to csr_matrix is a tuple of the form (data, idx), where data is a 1D array specifying the non-zero matrix elements, idx[0,:] specifies the row indices, and idx[1,:] specifies the column indices. Running the program produces the expected results:
(0, 1) 1.0
(1, 1) 2.0(1, 2) - 1.0(3, 0) 6.6(3, 4) 1.4The csr_matrix function figures out and generates the three CSR arrays automatically; you don't need to work them out yourself. But if you like, you can inspect the contents of the CSR arrays directly:
>>> A.data array([1., 2., -1., 6.6, 1.4]) >>> A.indices array([1, 1, 2, 0, 4], dtype = int32) >>> A.indptr array([0, 1, 3, 3, 5], dtype = int32)
To create a sparse matrix in the CSC format, we use the csc_matrix function. This is analogous to the csr_matrix function for CSR matrices. For example,
>>> from scipy import *
>>> import scipy.sparse as sp
>>> data = [1.0, 2.0, -1.0, 6.6, 1.4]
>>> rows = [0, 1, 1, 3, 3]
>>> cols = [1, 1, 2, 0, 4]
>>>
>>> A = sp.csc_matrix((data, [rows, cols]), shape=(4,5))
>>> A
<4x5 sparse matrix of type '<class ' numpy.float64'>'
with 5 stored elements in Compressed Sparse Column format>