Sparse Matrices
sparse … many elements are zero
dense … few elements are zero
0 0 3 0 4
0 0 5 7 0
Matrix = 0 0 0 0 0
0 2 6 0 0
0 0 0 0 0
Representation of Sparse Matrices
• There are two ways to represent the sparse matrix that are listed as
follows :
➢ Array representation
➢ Linked list representation
0 0 3 0 4
0 0 5 7 0
Matrix = 0 0 0 0 0
0 2 6 0 0
0 0 0 0 0
Array Representation
0 0 3 0 4
0 0 5 7 0
Matrix = 0 0 0 0 0
0 2 6 0 0
0 0 0 0 0
int sparseMatrix[5][5] = row 1 1 2 2 4 4
{ column 3 5 3 4 2 3
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 }, value 3 4 5 7 2 6
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }, int compactMatrix[3][size];
{0 , 0 , 0 , 0 , 0 },
};
15 0 0 22 0 -15 row col value
a[0] 6 6 8
0 11 3 0 0 0
a[1] 0 0 15
Matrix = 0 0 0 -6 0 0 a[2] 0 3 22
0 0 0 0 0 0 a[3] 0 5 -15
91 0 0 0 0 0 a[4] 1 1 11
0 0 28 0 0 0 a[5] 1 2 3
a[6] 2 3 -6
a[7] 4 0 91
a[8] 5 2 28
#define MAX_TERMS 101
/*max. no of terms +1 (to keep no of row and no of column information at 0 index)*/
typedef struct node
{
int col;
int row;
int value;
}term;
term a[MAX_TERMS];
Linear list Representation of Sparse Matrices
Single linear list in row-major order.
• Scan the nonzero elements of the sparse matrix in row-major order
• Each nonzero element is represented by a triple
(row, column, value)
0 0 3 0 4
0 0 5 7 0
Matrix = 0 0 0 0 0
0 2 6 0 0
0 0 0 0 0
Linked List Representation
Node structure:
row col
value next
•The advantage of using a linked list to represent the sparse
matrix is that the complexity of inserting or deleting a node in
a linked list is less than the array.
Single Linear List
0 0 3 0 4
0 0 5 7 0
Matrix = 0 0 0 0 0
0 2 6 0 0
0 0 0 0 0
row 1 1 2 2 4 4
list = column 3 5 3 4 2 3
value 3 4 5 7 2 6
1 3 1 5 2 3 2 4 4 2 4 3
3 4 5 7 2 6 null
firstNode
Array of Row Chains
Node structure:
next
col value
Prepared by: Dr Deepak Gupta, CSED, MNNIT Allahabad, India
Array Of Row Chains
00304
00570 null
00000 3 3 5 4
02600 null
3 5 4 7
// Node to represent row - list
struct row_list
{
int row_number;
struct row_list *link_down; null
struct value_list *link_right;
};
// Node to represent triples null
struct value_list
{
row[] 2 2 3 6
int column_index;
int value;
struct value_list *next;
};
Orthogonal List Representation
or Dictionary List
Both row and column lists.
Node structure:
row col value
down right
Header node:
next
down right
Row Lists
1 3 3 1 5 4
n
00304 2 3 5 2 4 7
00570 n
00000
null
02600
4 2 2 4 3 6
n
Column Lists
1 3 3 1 5 4
00304 n
00570 2 3 5 2 4 7
n
00000
02600
4 2 2 4 3 6
n n
Prepared by: Dr Deepak Gupta, CSED, MNNIT Allahabad, India
Orthogonal Lists
Column[ ]
1 3 3 1 5 4
00304 n n
00570 2 3 5 2 4 7
n n
00000
02600 null
4 2 2 4 3 6
n n n
row[ ]
May use circular lists instead of chains.
Show the Link representation of Sparse Matrix of the
following matrix: # define MAX_SIZE 50
typedef enum {head, entry} tagfield;
2 0 0 0
4 0 0 3 typedef struct matrixNode *matrixPointer;
Matrix = 0 0 0 0 typedef struct
{
8 0 0 1 int row;
0 0 6 0 int col;
int value;
} entryNode;
typedef struct
{
matrixPointer down;
matrixPointer right;
tagfield tag;
union
{
matrixPointer next;
entryNode entry;
}u;
}matrixNode;
matrixPointer hdnode[MAX_SIZE];
#define MAX_SIZE 50
// Enum for distinguishing between 'head' and 'entry' nodes
enum tagfield {head, entry};
// Structure to represent an individual matrix entry (non-zero values)
struct entryNode {
int row; // Row index of the matrix element
int col; // Column index of the matrix element
int value; // Value at the matrix element
};
// Structure for the nodes in the sparse matrix
struct matrixNode {
struct matrixNode* down; // Pointer to the next node in the same column
struct matrixNode* right; // Pointer to the next node in the same row
enum tagfield tag; // Indicates whether it's a head or entry node
union {
struct matrixNode* next; // Used when the node is a 'head'
struct entryNode entry; // Used when the node is an 'entry'
} u;
};
// Array of pointers to the head nodes of the sparse matrix
struct matrixNode* hdnode[MAX_SIZE];
H0 H1 H2 H3 H4
H
4 5 6 next next next next next
down right down right down right down right down right down right
H0 next 0 0 2
down right down right
next 1 0 4 1 3 3
H1
down right down right down right
next
H2
down right
next 3 0 8 3 3 1
H3
down right down right down right
next 4 2 6
H4 down right down right
NOTE:
If we wish to represent a numRows X numCols matrix with
numTerms nonzero terms then we need max(numRows ,
numCols) + numTerms + 1 nodes.
