This blog is under construction

Saturday, 25 May 2013

Array Representation Of Sparse Matrix

If most of the elements in a matrix have the value 0, then the matrix is called spare matrix.

Example For 3 X 3 Sparse Matrix:
|  1   0   0 |
|  0   0   0 |
|  0   4   0 |

3-Tuple Representation Of Sparse Matrix: 
|  3   3   2 |
|  0   0   1 |
|  2   1   4 |

Elements in the first row represents the number of rows, columns and non-zero values in sparse matrix.
First Row  -  |  3   3   2 |
3 - rows
3 - columns
2 - non- zero values

Elements in the other rows gives information about the location and value of non-zero elements.
|  0   0   1 | ( Second Row) - represents value 1 at 0th Row, 0th column
|  2   1   4 | (Third Row)     - represents value 4 at 2nd Row, 1st column

See Also:

Example Program for 3-Tuple Representation of Sparse Matrix Using Arrays(in C):



  #include <stdio.h>
  #include <stdlib.h>

  int count;

  int main() {
        int *data, *tuple, row, col, tot, i, j, k =0, x = 0, y = 0;

        printf("Enter the no of rows & columns:");
        scanf("%d%d", &row, &col);

        tot = row * col;
        data = (int *) malloc(sizeof (int) * tot);
        for (i = 0; i < tot; i++) {
                if (y % col == 0 && y != 0) {
                        y = 0;
                        x++;
                }
                printf("data[%d][%d]:", x, y);
                scanf("%d", &data[i]);
                if (data[i])
                        count++;
                y++;
        }

        tuple = (int *) malloc(sizeof (int) * (count + 1) * 3);

        /* store row, column & count in 3-tuple array - in 1st row */
        tuple[k++] = row;
        tuple[k++] = col;
        tuple[k++] = count;
        x = y = 0;
        for (i = 0; i < tot; i++) {
                if (y % col == 0 && y != 0) {
                        y = 0;
                        x++;
                }


                /* store row, column and non-zero val in 3 tuple */
                if (data[i] != 0) {
                        tuple[k++] = x;
                        tuple[k++] = y;
                        tuple[k++] = data[i];
                }
                y++;
        }

        printf("Given Sparse Matrix has %d non-zero elements\n", count);
        x = y = 0;

        /* printing given sparse matrix */
        for (i = 0; i < tot; i++) {
                if (y % col == 0 && y != 0) {
                        y = 0;
                        x++;
                        printf("\n");
                }
                printf("%d ", data[i]);
                y++;
        }
        printf("\n\n");

        /* 3-tuple represenation of sparse matrix */
        printf("3-Tuple representation of Sparse Matrix:\n");
        for (i = 0; i < (count + 1) * 3; i++) {
                if (i % 3 == 0)
                        printf("\n");
                printf("%d ", tuple[i]);
        }

        printf("\n\n");
        return 0;
  }



  Output: (C Program For Array Representation Of Sparse Matrix)
  jp@jp-VirtualBox:~/$ ./a.out
  Enter the no of rows & columns:3 3
  data[0][0]:1
  data[0][1]:0
  data[0][2]:0
  data[1][0]:0
  data[1][1]:0
  data[1][2]:0
  data[2][0]:0
  data[2][1]:4
  data[2][2]:0

  Given Sparse Matrix has 2 non-zero elements
    1 0 0 
    0 0 0 
    0 4 0 

  3-Tuple representation of Sparse Matrix:
    3 3 2 
    0 0 1 
    2 1 4 



2 comments:

  1. Elements in the first row represents the number of rows, columns and non-zero values in sparse matrix.
    First Row - | 3 3 2 |
    3 - rows
    3 - columns
    2 - non- zero values

    This definition helped me a lot, thank you!

    ReplyDelete