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

 

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

diagonal.

2)  Tridiagonal Matrix

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

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

 

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

Ask an Expert

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

Write your message here..

Related Questions

Nonrecursive implementation of a recursive algorithm?, What data structure ... What data structure would you mostly likely see in a nonrecursive execution of a recursive algorithm? Stack

Use a random number generator to create 10 numbers, Use a random number gen... Use a random number generator to create 10 numbers between 1 and 1000 and store them in 2 different arrays.  The first array should contain the numbers as they are generated.  The

Sparse metrics, Q. Define the sparse metrics and also explain the represent... Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

#, if two relations R and S are joined, then the non matching tuples of bot... if two relations R and S are joined, then the non matching tuples of both R and S are ignored in

Naïve recursive algorithm for binomial coefficients, How many recursive cal... How many recursive calls are called by the naïve recursive algorithm for binomial coefficients, C(10, 5) and C(21, 12) C(n,k){c(n-1,k)+c(n-1,k-1) if 1 1 if k = n or k = 0

Matrices multiplication, Write an algorithm for multiplication of two spars... Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Dqueue, how can i delete from deque while deletion is restricted from one e... how can i delete from deque while deletion is restricted from one end

Several operations on a aa-tree, The following are several operations on a ... The following are several operations on a AA-tree: 1. Searching: Searching is done using an algorithm which is similar to the search algorithm of a binary search tree. 2. Ins

Best case, Best Case: If the list is sorted already then A[i] T (n) = ... Best Case: If the list is sorted already then A[i] T (n) = c1n + c2 (n -1) + c3(n -1) + c4 (n -1)  = O (n), which indicates that the time complexity is linear. Worst Case:

Sequential files, In this section, we will discuss about Sequential file or... In this section, we will discuss about Sequential file organization. Sequential files have data records stored in a particular sequence. A sequentially organized file might be stor