Representing sparse matrix in memory using array, Data Structure & Algorithms

Assignment Help:

Q. What do you understand by the term sparse matrix? How sparse matrix is stored in the memory of a computer? Write down the function to find out the transpose of a sparse matrix using this particular representation.                                                                                                             

Ans.

Sparse Matrix is described below

A m x n matrix A would be a sparse if most of its elements are zero. A matrix that is not sparse is known as dense matrix.

Representing Sparse Matrix in Memory Using Array is described below

In an array representation an array of triplets of type < row, col, element> is used to store non-zero elements, where 1st field of the triplet is used to trace row position second to record column and the 3rd to record the non zero elements of  sparse matrix.

In addition, we are required to record the size of the matrix ( i.e. number of rows and the number of columns) and non zero elements of array of triplets are used for this purpose where the 1st filed saves the number of rows and the 2nd field saves the number of columns and the third field saves the number of non zero elements. The remaining elements of the array saves matrix on row major order. The array representation will be

[2 * (n+1) * size of (int) + n*size of(T)] bytes of memory where n is the number of non-zero elements and T is the data type of the element.

Ex: consider a 5*6 sparse matrix which is written below

1713_sparse matrix2.png 

Array Representation of Sparse Matrix is given below

1754_sparse matrix3.png

Here n = 5 but the size of array is 6 as first row saves the order of array along with a number non-zero elements.

Memory declaration will be as followsas shown below

# define Max 50 struct triplet

{   int row;

int col;

float element;

}

struct triplet sparse_mat [MAX];

sparse matrix represented as above

[n is the number of non zero elements in array]

for I= 1,2,...n+1 temp = a[I].row a[I].row= a[I].col a[I].col = temp endfor.


Related Discussions:- Representing sparse matrix in memory using array

Merging, Merging two sequence using CREW merge

Merging two sequence using CREW merge

Convertion, how we can convert a graph into tree

how we can convert a graph into tree

Illustrate the intervals in mathematics, Illustrate the intervals in mathem...

Illustrate the intervals in mathematics Carrier set of a Range of T is the set of all sets of values v ∈ T such that for some start value s ∈ T and end value e ∈ T, either s ≤

Discrete time simulation of a queue, In this project you will write a progr...

In this project you will write a program to produce a discrete time simulation of a queue as shown in Fig. 1. Time is slotted on the input and the output. Each input packet follows

Sorting, explain quick sort algorithm

explain quick sort algorithm

Memory mapping, lower triangular matrix and upper triangular matrix

lower triangular matrix and upper triangular matrix

Data Structure, Ask consider the file name cars.text each line in the file ...

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Darw a flowchart to input 3 numbers, This algorithm inputs 3 numbers, every...

This algorithm inputs 3 numbers, every number goes through successive division by 10 until its value is less than 1. An output is produced which comprise the number input and a val

What is quick sort, What is quick sort?   Answer Quick sort is on...

What is quick sort?   Answer Quick sort is one of the fastest sorting algorithm used for sorting a list. A pivot point is chosen. Remaining elements are divided or portio

Encryption the plain-text using the round keys, Encryption the plain-text u...

Encryption the plain-text using the round keys: 1. (Key schedule) Implement an algorithm that will take a 128 bit key and generate the round keys for the AES encryption/decryp

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd