Sparse matrix, Data Structure & Algorithms

Assignment Help:

Q. Define a sparse matrix. Explain different types of sparse matrices? Show how a triangular array is stored in memory. Evaluate the method to calculate address of any element ajk of a matrix stored in memory.                                                                                                                             

Ans.

Sparse Matrix

A m x n matrix A is said to be sparse if MOST of its elements are zero. A matrix that is not sparse is called dense matrix.

Types of Sparse matrix

1)            Diagonal Matrix

488_Diagonal matrix.png 

This is the square matrix where the non zero elements are only where row = col ie at

diagonal.

2)  Tridiagonal Matrix

897_tridiagonal matrix.png

In  this  square  matrix  all  elements  other  than  those  on  and  on  the  diagonals immediately above and below this one are zero.

Triangular Matrices

Tiangular Matrices is of 2 types:

a)  Lower triangular b)  Upper triangular

720_Diagonal matrix1.png

In an n*n lower triangular matrix A, row 1 has one non zero element, row 2 has 2,

....., and row n has n. whereas, in an n*n upper triangular matrix A, row 1 has n non zero elements, row 2 has n-1 ,.... , and row n has 1. In both the cases, the total number of non-zero elements is n(n+1)/2.

Both of these matrices can be represented using an one dimensional array la of size n(n+1)/2.

Consider lower triangular matrix L. the elements can be mapped by rows or by columns.

In a row-wise mapping, the element L[i,j], i>=j, is preceded by ∑k  for k=1 to i-1, elements that are in row 1 through i-1, and j-1 such elements from row i. the total number of elements that precede it in a row-wise mapping is

1620_Diagonal matrix2.png

 

This expression also gives the position l[i,j] in la.

Method  to  calculate  address  of  any  element  ajk   of  a  matrix     stored  in memory.

Let us consider 2 dimensional array a of size m*n further consider that the lower bound for the row index is lbr and for column index is lbc.

Like linear array, system keeps track of the first element only i.e. , the base address of the array.

Using this base address, the computer computes the address of the element in the ith row and jth column i.e. loc(a[i][j]), using the following formulae:

Column major order:-

Loc (a[i][j]) = base (a) + w [m (j - lbc) + ( i - lbr)] in general

Row major order:-

Loc (a[i][j]) = base (a) + w [n(i - lbr) + ( j - lbc)]            in general

where w is number of bytes per storage location for any one element of the array.


Related Discussions:- Sparse matrix

Inorder traversal, Inorder traversal: The left sub tree is visited, then t...

Inorder traversal: The left sub tree is visited, then the node and then right sub-tree. Algorithm for inorder traversal is following: traverse left sub-tree visit node

BST has two children, If a node in a BST has two children, then its inorder...

If a node in a BST has two children, then its inorder predecessor has No right child

Data structure queue, In this unit, we described about the data structure Q...

In this unit, we described about the data structure Queue. It had two ends. One is front from where the elements can be removed and the other is rear where the elements can be inse

A binary tree in which levels except possibly the last, A binary tree in wh...

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as

Explain thread, Thread By changing the NULL lines in a binary tree to ...

Thread By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using either a stack

Mcs-021, #questWrite an algorithm for multiplication of two sparse matrices...

#questWrite an algorithm for multiplication of two sparse matrices using Linked Lists.ion..

Algorithm to sort a given list by quick sort method, Q. Write down an algor...

Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

Data structure, Ask question #Minimum 1Mark each of the following statement...

Ask question #Minimum 1Mark each of the following statements as valid or invalid. If a statement is invalid, explain why. a. current ¼ list; b. temp->link->link ¼ NULL; c. trail->l

Difference in grounded header and circular header Link List, Q. State the d...

Q. State the difference between a grounded header link list and a circular header link list?     Ans: A header linked list is a linked list which all the time c

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