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

Pseudo code, I need help writing a pseudocode for my assignment can anyone ...

I need help writing a pseudocode for my assignment can anyone help?

Luminous Jewels - The Polishing Game, Byteland county is very famous for lu...

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

Applications, Arrays are simple, however reliable to employ in more conditi...

Arrays are simple, however reliable to employ in more condition than you can count. Arrays are utilized in those problems while the number of items to be solved out is fixed. They

Linked lists - implementation, The Linked list is a chain of structures whe...

The Linked list is a chain of structures wherein each structure contains data in addition to pointer, which stores the address (link) of the next logical structure in the list.

Write down the algorithm of quick sort, Write down the algorithm of quick s...

Write down the algorithm of quick sort. An algorithm for quick sort: void quicksort ( int a[ ], int lower, int upper ) {  int i ;  if ( upper > lower ) {   i = split ( a,

Random searching, write a program that find,search&replace a text string

write a program that find,search&replace a text string

Total weight of minimum spanning tree, a) Run your program for α = 0.05, 0...

a) Run your program for α = 0.05, 0.5, and 0.95. You can use n = 30, and W = 10. What is impact of increasing value of α on connectivity of G'? To answer this question, for each v

Define the term counting - pseudocode, Define the term counting - Pseudocod...

Define the term counting - Pseudocode Counting in 1s is quite simple; use of statement count = count + 1 would enable counting to be done (for example in controlling a repeat

Binary search, In a sorted list, Binary search is carried out by dividing t...

In a sorted list, Binary search is carried out by dividing the list into two parts depends on the comparison of the key. Since the search interval halves each time, the iteration o

Tower of hanoi problem., Write an algorithm for getting solution to the Tow...

Write an algorithm for getting solution to the Tower's of Hanoi problem. Explain the working of your algorithm (with 4 disks) with appropriate diagrams. Ans: void Hanoi(int

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