Sparse Matrix In C

Formal Definition:

A matrix is considered sparse if:

Number of Zero Elements>Number of Non-Zero Elements

For example:

0  0  0  0
5  0  0  0
0  0  8  0
0  0  0  0

It's a 4×4 matrix containing 14 zeros and just 2 non-zero values, classifying it as a sparse matrix.

Why do we use Sparse Matrices?

There are several scenarios where we can use the sparse matrix in C.

• ✅ Storage: A sparse matrix contains fewer non-zero elements than zero, so less memory can be used to store elements. It evaluates only the non-zero elements.
• ✅ Computing time: In the case of searching in a sparse matrix, we need to traverse only the non-zero elements rather than traversing all the sparse matrix elements. It saves computing time by logically designing a data structure that traverses non-zero elements.
• ✅ Speed: Multiplying, adding, or searching through zero elements can be performed faster with no consideration of the zero elements.

Sparse Matrices Memory Representation

In C programming, a sparse matrix refers to a matrix where the majority of elements have a value of zero. Instead of storing all elements, including zeros, we optimize memory usage and improve computational efficiency by only storing non-zero elements.

There are two common methods for storing a sparse matrix in memory in C programming.

1) Array Representation (Coordinate List/3-Tuple form)

We represent a sparse matrix as a 2D array of triplets, where each row of the array holds:

• ✅ Row index of the non-zero element
• ✅ Column position of that non-zero element
• ✅ Non-zero element value
• ✅ Metadata such as the overall number of rows, columns, and non-zero elements is commonly placed in the first row.

Matrix:

0 0 5
0 8 0
3 0 0

Array Representation:

[3, 3, 3]    // rows, columns, non-zero count
[0, 2, 5]
[1, 1, 8]
[2, 0, 3]

Array Representation Example in C

Let's consider an illustration to showcase the array depiction using a sparse array in the C programming language.

Example

#include <stdio.h>
#define MAX 100 // Maximum non-zero elements
// using 3-tuple form
struct SparseMat {
    int row;    //defining row
    int col;    //defining col
    int val;   //defining val
};
int main() {   //main function
    int x, y;
    int matrix[8][8];
    struct SparseMat sparse[MAX];
    int k = 0; // Index for sparse array
   
    printf("Enter number of rows and columns: ");
    scanf("%d %d", &x, &y);
    
    printf("Enter the elements of the matrix:\n");
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < y; j++) {
            scanf("%d", &matrix[i][j]);
            if (matrix[i][j] != 0) {
                sparse[k].row = i;
                sparse[k].col = j;
                sparse[k].val = matrix[i][j];
                k++;
            }
        }
    }
    // Print Sparse Matrix
    printf("\nSparse Matrix Representation (row, col, value):\n");
    for (int i = 0; i < k; i++) {
        printf("%d\t%d\t%d\n", sparse[i].row, sparse[i].col, sparse[i].val);
    }
    return 0;
}

Output:

Enter number of rows and columns: 3 4
Enter the elements of the matrix:
0 0 3 0
22 0 0 0
0 0 0 4

Sparse Matrix Representation (row, col, value):
0   2   3
1   0   22
2   3   4

Explanation:

In this instance, we display a sparse matrix utilizing a triplet format that retains solely non-zero values alongside their respective row and column indexes. Rather than storing every element, it conserves memory by storing solely the relevant values. Subsequently, it showcases the sparse matrix in a format comprising row, column, and value.

2) Linked List Representation

Each non-zero element is stored in a node, which contains:

• ✅ Row index
• ✅ Column index
• ✅ Value
• ✅ Pointer to the next node (in row-major or column-major order).
• ✅ Sometimes, multiple linked lists are used for faster access (one per row or column).

Example Node Structure in C:

struct Node {
    int row, col, value;
    struct Node* next;
};

Visual Example for the Same Matrix:

(0,2,5) -> (1,1,8) -> (2,0,3) -> NULL

Linked List Representation Example in C

Let's consider a scenario to demonstrate the linked list depiction utilizing a sparse array in the C programming language.

Example

#include <stdio.h>
#include <stdlib.h>
// Node structure for linked list representation
struct Node {
    int row, col, val;
    struct Node *next;
};
// Function to create a new node
struct Node* createNode(int row, int col, int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->row = row;
    newNode->col = col;
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}
// Function to insert a node at the end of the list
void insertNode(struct Node** head, int row, int col, int val) {
    struct Node* newNode = createNode(row, col, val);
    if (*head == NULL) {
        *head = newNode;
    } else {
        struct Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}
// Function to display the sparse matrix linked list
void display(struct Node* head) {
    printf("\nSparse Matrix Representation (row, col, value):\n");
    while (head != NULL) {
        printf("%d\t%d\t%d\n", head->row, head->col, head->val);
        head = head->next;
    }
}
int main() {   //main function
    int m, n, val;
    struct Node* head = NULL;
    printf("Enter number of rows and columns: ");
    scanf("%d %d", &m, &n);
    printf("Enter the elements of the matrix:\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &val);
            if (val != 0) {
                insertNode(&head, i, j, val);
            }
        }
    }
    display(head);
    return 0;
}

Output:

Enter the elements of the matrix:
0 0 7 0
18 0 0 0
0 5 0 0

Sparse Matrix Representation (row, col, value):
0       2       7
1       0       18
2       1       5

Explanation:

In this instance, a sparse matrix is depicted through a linked list, wherein solely non-zero elements are retained alongside their respective row, column, and value. By omitting the storage of zero values, sparse matrices effectively minimize memory consumption. Subsequently, an optimized display of the matrix is achieved by showcasing the data in a structured format comprising of row, column, and corresponding value.

Properties of a Sparse Matrix

There are several properties of a sparse matrix in C. Some of them are as follows:

• ✅ High Zero Density: The number of zero elements is very high in comparison to non-zero elements.
• ✅ Efficient Storage Formats: Specific use cases use different storage formats to store sparse matrices (such as COO, CSR, and CSC).
• ✅ Performance Optimization: Skipping of zero elements in several operations, such as addition, multiplication, and traversal, improves the computation speed.
• ✅ Position-Value Mapping: We need to store row number, column number, and value of every non-zero element to reconstruct the matrix.

Conclusion

In summary, sparse matrices are employed in C to store exclusively non-zero values, optimizing memory usage and boosting efficiency when handling extensive datasets. The array-based format in C is efficient and facilitates quick data retrieval but lacks flexibility for modifications. On the other hand, the linked list format allows for dynamic updates but consumes additional memory for pointer storage. Sparse matrices find extensive applications in various domains like image processing, graph analysis, machine learning, and more.

Sparse Matrix FAQs

1) What does it mean by Sparse Matrix?

A sparse matrix is a specific type of matrix where the majority of elements have a value of zero, and only a small number of non-zero elements are retained in order to conserve memory space.

Using a sparse matrix in C programming is advantageous because it allows for efficient storage of matrices that contain a large number of zero elements. This optimization helps in reducing memory consumption and improving the overall performance of matrix operations.

Sparse matrices are primarily utilized to minimize storage space and improve efficiency in operations, particularly when dealing with large matrices containing numerous zero values.

In an array-based data structure, dynamic resizing involves creating a new array with a larger size, copying the existing elements to the new array, and then deallocating the old array. This process can be time-consuming, especially if the array is large.

On the other hand, in a linked list, dynamic resizing typically involves adding new nodes to the existing linked list. This can be more efficient than resizing an array because adding a new node does not require copying existing elements.

Array-based storage requires frequent memory allocation and data duplication as it expands, resulting in high costs for frequent modifications. On the other hand, linked lists offer dynamic growth without the need for complete reallocation, although they come with additional memory overhead due to the presence of pointers.

4) Where are sparse matrices used in C?

Sparse matrices can be utilized in several fields, such as:

• ✅ Image processing
• ✅ Scientific
• ✅ Machine Learning
• ✅ Graph Algorithm, and many more

The 3-tuple representation of a sparse matrix in C refers to a format where each non-zero element in the matrix is stored along with its row index, column index, and value. This representation is commonly used to efficiently store and manipulate matrices that have a large number of zero elements, saving memory and computational resources.

In the realm of C programming, a 3-tuple structure represents a condensed array format in which every non-zero element is specified by its row, column, and corresponding value.