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.