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

Explain the representations of graph, Explain the representations of graph....

Explain the representations of graph. The different ways of representing a graph is: Adjacency list representation : This representation of graph having of an array Adj of

Algorithms, 2. Write a note on i) devising ii) validating and...

2. Write a note on i) devising ii) validating and iii) testing of algorithms.

Binary search trees, A Binary Search Tree is binary tree which is either em...

A Binary Search Tree is binary tree which is either empty or a node having a key value, left child & right child. By analyzing the above definition, we notice that BST comes int

Design a binary tree, (a) Suppose that t is a binary tree of integers (that...

(a) Suppose that t is a binary tree of integers (that is, an object of type BinTree of Int.) in the state shown in Figure 3.   Give the vectors returned by each of the f

Explain how the shuttle sort algorithm works, Question 1 Explain how th...

Question 1 Explain how the shuttle sort algorithm works by making use of the following list of integers:11, 4, 2, 8, 5, 33, 7, 3, 1, 6. Show all the steps. Question 2

High-level and bubble algorithm , 1. Give both a high-level algorithm and a...

1. Give both a high-level algorithm and an implementation (\bubble diagram") of a Turing machine for the language in Exercise 3.8 (b) on page 160. Use the ' notation to show the co

Different ways for representing s graph, W h at are the different ways by...

W h at are the different ways by which we can represent graph?  Represent the graph drawn below using those ways.     T he d iff e r e nt w a y s by

Program, What is a first-in-first-out data structure ? Write algorithms to...

What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.

Threads in main method, Create main method or a test class that creates 2 E...

Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h

Define game trees, Game trees An interesting application of trees is th...

Game trees An interesting application of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can picture the sequence of possible moves by m

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