Sparse matrix, Data Structure & Algorithms

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.

Posted Date: 7/13/2012 1:11:15 AM | Location : United States







Related Discussions:- Sparse matrix, Assignment Help, Ask Question on Sparse matrix, Get Answer, Expert's Help, Sparse matrix Discussions

Write discussion on Sparse matrix
Your posts are moderated
Related Questions
What is Algorithm A finite sequence of steps for accomplishing some computational task. An algorithm should Have steps which are simple and definite enough to be done

Determine about the unreachable code assertion An unreachable code assertion is an assertion that is placed at a point in a program that shouldn't be executed under any circum

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

Define Big Omega notation Big Omega notation (?) : The lower bound for the function 'f' is given by the big omega notation (?). Considering 'g' to be a function from the non-n

Consider the following 5-city traveling salesman problem. The distance between each city (in miles) is shown in the following table: (a) Formulate an IP whose solution will

Define neotaxonomy. Discuss how electron microscopy can help in solving a zoological problem faced by taxonomist.

#include #include int sumFact(int numb); int calculateFactorial(int digit); main() { int numb, sumfact; do{ printf ("Enter a number 1 to 9999\n"); scanf("%

In this unit, we will describe a data structure called Graph. Actually, graph is a general tree along no parent-child relationship. In computer science, Graphs have several applica

Q. Convert the following given Infix expression to Postfix form using the stack function: x + y * z + ( p * q + r ) * s , Follow general precedence rule and suppose tha

Ask question #Minima binary search tree is used to locate the number 43 which of the following probe sequences are possible and which are not? explainum 100 words accepted#