Sparse Matrix
A matrix in which the number of zero elements > non-zero elements.
Example:
0050
0 800
0 0 0 10
Here, most values are 0, only a few are useful.
Storing Zeroes is Waste of Memory
● In a normal array, every element (including 0) occupies memory.
● Example: 3×4 matrix = 12 elements.
○ Storage (int = 4 bytes) = 48 bytes.
○ Only 3 values are useful (12 bytes).
○ 36 bytes wasted for zeroes.
Memory reserved for zeroes is blocked and can’t be used by other variables.
How Sparse Matrix Saves Memory?
Sparse matrix does not store zeroes.
It only stores: row index, column index, and value of non-zero elements.
This way, memory depends only on non-zero count, not full matrix size.
Example:
● 5×5 matrix = 25 elements (100 bytes).
● Suppose only 5 non-zero values.
● Sparse representation: 5×3×4= =60 bytes.
● Saved 40 bytes → free for other processes.
Does Sparse Matrix Reduce Size?
● Normal array size = rows × columns × element size (fixed).
● Sparse matrix size = non-zero count × 3 × element size (variable).
● Hence, yes sparse representation reduces overall memory size.
Representations of Sparse Matrix
1. Triplet Form (3-tuple):
○ Stores row, col, value for each non-zero element.
Example:
Row Col Value
0 2 5
1 1 8
2 3 10
○ Yes, triplet form uses extra memory for row & column indices.
○ But overall memory is still saved only if the matrix is truly sparse (i.e., very few
non-zero elements).
○ If matrix has many non-zero elements, normal storage may be better
2 . Compressed Row Storage (CRS)
CRS ek efficient representation hai sparse matrix ka.
Isme hum 3 arrays banate hain:
1. val[] → Non-zero elements values.
2. col_ind[] → Column index of each non-zero element.
3. row_ptr[] → Starting position of each row in val[].
[Link] Column Storage (CCS):
○ Similar to CRS but stores column-wise.
CCS me 3 arrays hote hain:
1. values[] → saare non-zero elements ko store karta hai column-wise order me.
2. row_index[] → har non-zero element ke corresponding row ka index store karta hai.
3. col_ptr[] → ek array jo batata hai ki har column me non-zero elements values[] me
kahan se start ho rahe hain
Applications of sparse matrix
1. Computer Graphics & Image Processing
○ Images (like black & white) often have large areas of black pixels (zeros).
○ Storing them as sparse matrices saves space.
2. Machine Learning & Data Mining
○ In text analysis (like document-word matrix in NLP), most words don’t appear in every
document.
○ These are stored as sparse matrices.
3. Search Engines (Google, Bing, etc.)
○ The web graph (pages vs links) is very sparse.
○ Sparse matrix helps in efficient storage and algorithms like PageRank.
4. Social Networks
○ The adjacency matrix of a huge social network graph is sparse because not everyone is
connected to everyone else.
#code 1
import [Link];
public class SparseCheck {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
// Input dimensions
[Link]("Enter rows: ");
int rows = [Link]();
[Link]("Enter cols: ");
int cols = [Link]();
int[][] matrix = new int[rows][cols];
int zeroCount = 0, nonZeroCount = 0;
// Input elements
[Link]("Enter matrix elements:");
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
matrix[i][j] = [Link]();
if(matrix[i][j] == 0) zeroCount++;
else nonZeroCount++;
}
}
// Check sparse condition
if(zeroCount > nonZeroCount) {
[Link]("The matrix is SPARSE.");
} else {
[Link]("The matrix is NOT SPARSE.");
}
}
}
#code 2
import [Link];
public class MatrixToTriplet {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter rows: ");
int rows = [Link]();
[Link]("Enter cols: ");
int cols = [Link]();
int[][] matrix = new int[rows][cols];
[Link]("Enter matrix elements:");
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
matrix[i][j] = [Link]();
}
}
[Link]("\nTriplet Representation:");
[Link]("Row\tCol\tValue");
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(matrix[i][j] != 0) {
[Link](i + "\t" + j + "\t" + matrix[i][j]);
}
}
}
}
}