Sparse Matrix

In this example you will see how to represent sparse matrix using C programming language. A sparse matrix is one where most of its elements are zero (0). For example, the following image represents a sparse matrix:

Such matrix can be represented more economically in terms of space if two dimensional array is not used to represent the matrix. The idea is to store the data regarding non-zero elements only. In this manner the matrix is thought of as an ordered list of non-zero elements with three parts:

• An integer represents its row
• An integer represents its column
• The data associated with this element or at row & column indices

Sparse Matrix Implementation

So you can define a structure in C programming language as shown below.

An element can be implemented as shown below:

typedef struct element {
    int row, col, val;
} element;

A sparse matrix can be implemented as shown below:

typedef struct spmat {
    element data[100];
    int noOfRows, noOfCols, noOfElements;
} spmat;

So the above 4×5 matrix as shown in the image, can be described as a one-dimensional array sp, such that sp.noOfElements is 6, sp.noOfRows is 4, sp.noOfCols is 5 and sp.data can be depicted as shown below:

So each element in the array is 3-tuples in the above representation.

Now you will see how to find out number of elements in each column. The below function in C program does the job.

void noOfElementsInColoumn(spmat *s) {
    int i,j, count = 0;

    for(i=0; i<s->noOfCols; i++) {
        count = 0;

        for(j=0; j<s->noOfElements; j++) {
            if(s->data[j].col == i) {
                count++;
            }
        }

        printf("\nNumber of elements in column %d is %d", i , count);
    }
}

The next problem is to deal with computing the transpose of the sparse matrix.

The below function does the required job to perform the transpose of the given sparse matrix.

spmat* transposeMatrix(spmat *s) {
    int i, j, k=0;
    spmat *t;

    t = malloc(sizeof(spmat));

    t->noOfRows = s->noOfCols;
    t->noOfCols = s->noOfRows;
    t->noOfElements = s->noOfElements;

    for(i=0; i<s->noOfCols; i++) {
        for(j=0; j<s->noOfElements; j++) {
            if(s->data[j].col == i) {
                t->data[k].row = i;
                t->data[k].col = s->data[j].row;
                t->data[k].val = s->data[j].val;
                k++;
            }
        }
    }

    return t;
}

I will define below function in C program to print the sparse matrix:

void printMatrix(spmat *s) {
    int i;

    for(i=0; i<s->noOfElements; i++) {
        printf("[%d, %d, %d] ", s->data[i].row, s->data[i].col, s->data[i].val);
    }

    printf("\n");
}

Testing Sparse Matrix

The main function that will ask for user input for sparse matrix, it will print the given sparse matrix, it will display the number of elements in each column and it will display the transpose of the given sparse matrix.

That’s all about sparse matrix representation using C program.

Source Code

Download