INTRODUCTION :- Spares matrix has only 3 columns and (no. of non-zero elements + 1) rows. The position [0][0] represents number of rows. The position [0][1] represents number of columns. The position [0][2] represents number of non-zero elements. While column 1 after position [0][0] contains indices of rows, the column 2 after position [0][1] contains indices of columns and the column 2 after position [0][2] contains the non-zero elements. The program has three sub-tasks. Following three functions have to be performed:-
DATA STRUCTURE USED :-
The data structure used is two dimensional array of data type int(integer). CONCEPT USED :- The concept of operator overloading is used in the addition of two sparse matrices. PREREQUISITES :- Before performing the three above mentioned functions we need to:-
CONVERT TO SPARSE MATRIX:-Initially we have a pre declared two dimensional array s[size][3]. To convert simple (m x n) matrix to sparse matrix we again traverse each element of the array A from [0][0] to [m-1][n-1] and check if the element at a particular position is equal to 0(zero) or not. If not, we copy the first index of the found position of array A as the row index to be stored in column 1 of sparse matrix. Similarly, we copy the second index of the found position of array A as the column index to be stored in column 2 sparse matrix. Finally, we copy the element at the found position as the non-zero element to be stored in column 3 of sparse matrix. We repeat these steps until we traverse the array A completely. REFER THE INTRODUCTION AND THE COMPLETE CODE BELOW FOR BETTER UNDERSTANDING TRANSPOSE BY SIMPLE METHOD:-To find the transpose of a matrix all we need to do is replace the column indices with that of rows. The sparse matrix already has the row indices in ascending order. Now to find transpose we need to traverse each column index in column 2 of sparse matrix. The column index with least value is made the first row index of the transpose sparse matrix and the corresponding row index of sparse matrix is made the column index of the transpose sparse matrix. While the corresponding non-zero element occupies the corresponding position in the column 3 of transpose sparse matrix. We repeat these steps until we traverse all the column indices of the sparse matrix s. REFER THE INTRODUCTION AND THE COMPLETE CODE BELOW FOR BETTER UNDERSTANDING TRANSPOSE BY FAST METHOD :-Finding transpose by simple method involves time complexity of O(n2). But doing the same operation with fast method involves time complexity of only O(n). Hence it is more efficient than the normal method. To find transpose by fast method can be understood by following steps. :-
ADDITION OF TWO SPARSE MATRICES:-The two sparse matrices can be added only if the number of rows and columns of both the matrices are same. We can perform the addition by operator overloading. This will let us write the create function only once and we can access the two sparse matrices with two objects. The logic to perform addition can be explained as follows. :-
DISPLAY THE SPARSE MATRIX:-To display the sparse matrix we first display the total number of rows, columns and non-zero elements stored at positions [0][0], [0][1] and [0][2] respectively. Then we run a for loop until all the elements are traversed and display the row index column index and the non-zero element on every iteration.
0 Comments
Leave a Reply. |
AuthorProf. Ketan Sanjay Desale Archives
April 2020
Categories |