Implementing Sparse Matrices In Arrays

A matrix is a two-dimensional data object with m rows and n columns, resulting in a total of m x n values. When most of the elements in a matrix have a value of 0, it is called a sparse matrix. Sparse matrices are common in various applications, such as scientific computing, graph algorithms, and machine learning.

Why Use Sparse Matrices?

1. Storage Efficiency: Sparse matrices have fewer non-zero elements than zeros. Storing only the non-zero elements saves memory.
2. Computational Efficiency: By focusing on non-zero elements, we can optimize computations and reduce processing time.

Array Representation

One way to represent a sparse matrix is using a 2D array. However, this approach leads to memory wastage since zeroes are irrelevant in most cases. Instead, we store only the non-zero elements using triples: (Row, Column, Value).

Example

Consider the following sparse matrix:

0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0

We can represent it as a compact matrix with three rows:

1. Row: Index of the row where the non-zero element is located.
2. Column: Index of the column where the non-zero element is located.
3. Value: Value of the non-zero element.

#include <iostream>using namespace std;

int main() {
    int sparseMatrix[4][5] = {
        {0, 0, 3, 0, 4},
        {0, 0, 5, 7, 0},
        {0, 0, 0, 0, 0},
        {0, 2, 6, 0, 0}
    };

    int size = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            if (sparseMatrix[i][j] != 0)
                size++;

    int compactMatrix[3][size];
    int k = 0;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 5; j++)
            if (sparseMatrix[i][j] != 0) {
                compactMatrix[0][k] = i;
                compactMatrix[1][k] = j;
                compactMatrix[2][k] = sparseMatrix[i][j];
                k++;
            }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < size; j++)
            cout << " " << compactMatrix[i][j];
        cout << "\\n";
    }

    return 0;

Output:

0 0 1 1 3 3 2 4 2 3 1 2 3 4 5 7 2 6

• Time Complexity: O(NM), where N is the number of rows and M is the number of columns in the sparse matrix.
• Auxiliary Space: O(NM)

Linked List Representation

Another approach is using linked lists. Each node contains four fields: Row, Column, Value, and a pointer to the next node.

#include <iostream>using namespace std;

class Node {
public:
    int row;
    int col;
    int data;
    Node* next;
};

// Create a new node
void create_new_node(Node** p, int row_index, int col_index, int x) {
    Node* temp = *p;
    Node* r;
    if (temp == NULL) {
        temp = new Node();
        temp->row = row_index;
        temp->col = col_index;
        temp->data = x;
        // ...
    }
    // ...
}

// Other linked list operations...

Remember to implement the linked list operations for a complete representation.

Conclusion

Sparse matrices provide efficient storage and computation for scenarios where most elements are zero. Choose the appropriate representation based on your application’s requirements.