K L UNIVERSITY

FRESHMAN ENGINEERING DEPARTMENT

A Project Based Lab Report

On

SPARSE MATRIX IMPLEMENTATION

SUBMITTED BY:

I.D NUMBER NAME

190030164 B. Nagarjuna Reddy

190030203 B. Sumanth

190030219 B. Sritha

190030228 B. Naveen Reddy

UNDER THE ESTEEMED GUIDANCE OF

Dr. M. Anusha

Associative Professor

KL UNIVERSITY
Green fields, Vaddeswaram – 522 502
Guntur Dt., AP, India.
 DEPARTMENT OF BASIC ENGINEERING SCIENCES

CERTIFICATE

This is to certify that the project based laboratory report entitled

“SPARSE MATRIX IMPLEMENTATION” submitted by Mr. B. Nagarjuna Reddy ,
Mr. B. Sumanth , Ms. B. Sritha , Mr. B. Naveen Reddy bearing Regd. No.
190030164 , 190030203 , 190030219 , 190030228 to the Department of
Basic Engineering Sciences, KL University in partial fulfillment of the
requirements for the completion of a project based Laboratory in “Technical
Skills-I(Coding)” course in I B Tech I Semester, is a bonafide record of the work
carried out by him/her under my supervision during the academic year 2019 –
2020.

PROJECT SUPERVISOR HEAD OF THE DEPARTMENT

Dr. M. Anusha Dr. D. Haritha

 ACKNOWLEDGEMENTS

It is great pleasure for me to express my gratitude to our honorable

President Sri. Koneru Satyanarayana, for giving the opportunity and platform
with facilities in accomplishing the project based laboratory report.

We express the sincere gratitude to our Director Dr. A. Jagdeesh for his
administration towards our academic growth.

We express sincere gratitude to our Coordinator and HOD-BES Dr. D.

Haritha for her leadership and constant motivation provided in successful
completion of our academic semester. We record it as my privilege to deeply
thank for providing us the efficient faculty and facilities to make our ideas into
reality.

We express my sincere thanks to our project supervisor Dr. M. Anusha

for her novel association of ideas, encouragement, appreciation and intellectual
zeal which motivated us to venture this project successfully.

Finally, it is pleased to acknowledge the indebtedness to all those who

devoted themselves directly or indirectly to make this project report success.

Regd . No Name

190030164 B. Nagarjuna Reddy

190030203 B. Sumanth

190030219 B. Sritha

190030228 B.Naveen Reddy

 ABSTRACT

Implement a sparse matrix in which any or most of the entries are zero.
Because allocating memory space for all entries of the matrix will be wasteful we
intend to allocate memory space only for nonzero entries.
Modules:
(a) Represent a sparse matrix as a doubly linked circular or any other data
structure which you think is useful.
(b) Write a program to perform the following operations:
(i) Read in inputs for the entries of a sparse matrix and form a suitable
data structure.
(ii) Addition of two sparse matrices.
(iii) Subtraction of two sparse matrices.
(iv) Multiplication of two sparse matrices.
(v) Print sparse matrix (in matrix form).
 INDEX
S.NO TITLE PAGE NO

1 Introduction 1

2 Aim of the Project 2

2.1 Advantages & Disadvantages 2

2.2 Future Implementation 2

3 Software & Hardware Details 3

4 Implementation (A) 4

5 Implementation (B) 5 - 12

6 Outputs/ScreenShots 13 - 17

7 Conclusion 18
 INTRODUCTION
A matrix is a two-dimensional data object made of m rows and n columns,
therefore having total m x n values. If most of the elements of the matrix have 0
value, then it is called a sparse matrix.

In computer programming, a matrix can be defined with a 2-dimensional

array. Any array with 'm' columns and 'n' rows represent a m X n matrix. There
may be a situation in which a matrix contains more number of ZERO values than
NON-ZERO values. Such matrix is known as sparse matrix.

Sparse matrix is a matrix which contains very few non-zero elements.

When a sparse matrix is represented with a 2-dimensional array, we

waste a lot of space to represent that matrix. For example, consider a matrix of
size 100 X 100 containing only 10 non-zero elements. In this matrix, only 10
spaces are filled with non-zero values and remaining spaces of the matrix are
filled with zero. That means, totally we allocate 100 X 100 X 2 = 20000 bytes of
space to store this integer matrix. And to access these 10 non-zero elements we
have to make scanning for 10000 times. To make it simple we use the following
sparse matrix representation.

A sparse matrix can be represented by using TWO representations, those

are as follows:-

1. Triplet Representation (Array Representation).

2. Linked Representatipon.

[1]
 AIM
Memory usage and CPU time are generally inversely proportional,
because the computer needs more time to perform operations on a compactified
data structure. The idea of sparse matrices mirrors exactly the need for less
memory load, therefore it is natural that sparse algorithms take more time than
dense ones.

Advantages:-
1. Cheaper to store
2. As a lot of elements are zero, it reduces the total computational time
taken for operations

Disadvantages:-

1. The main disadvantage is that asparse matrix can contain a lot

less information than a non-sparse matrix, since a vast majority
of its entries must be equal to 0. Not everything can be modeled
by a sparse matrix.
2. Not everything can be made into a sparse matrix for representation.
3. Holds lesser information.

Future enhancements:-
1. Using Sparse Matrices for IR.
2. Proximity Search using Sparse Matrix Multiplication.
3. Relevance Feedback using Sparse Matrix Multiplication.

[2]
 SYSTEM REQUIREMENTS

➢ SOFTWARE REQUIREMENTS:
The major software requirements of the project are as follows:
Language : Java
Operating system: Windows Xp or later.
Complier: Java Compiler , JVM , Eclipse Ide.

➢ HARDWARE REQUIREMENTS:
The hardware requirements that map towards the software are as follows:

RAM : 4GB or later

Processor : Intel core i5 or later

[3]
[A] IMPLEMENTATION
Using Arrays:-

2D array is used to represent a sparse matrix in which there are three

rows named as:

• Row: Index of row, where non-zero element is located.

• Column: Index of column, where non-zero element is located.
• Value: Value of the non zero element located at index – (row,
column)

Using Linked List:-

In linked list, each node has four fields. These four fields are defined as:

• Row: Index of row, where non-zero element is located.

• Column: Index of column, where non-zero element is located.
• Value: Value of the non zero element located at index – (row,
column).
• Next node: Address of the next node.

[4]
[B] IMPLEMENTATION

<LIBARARY CLASS>
package matrix;
class Node
{
int value;
int row;
int col;
Node nxt;
}
<MAIN CLASSS>
package matrix;
import java.util.Scanner;
public class Project
{
Node
head1=null,head2=null,tail1=null,tail2=null,r1,r2,r,ra,temp,s,heada=null,taila
=null,tails=null,heads=null,rs,headm=null,tailm=null,rm;
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
Project obj=new Project();
int m1,m2,n1,n2,i,j,ch=0,k,sum=0;
System.out.println("ENTER YOUR FIRST MATRIX SIZE:");
m1=s.nextInt();
n1=s.nextInt();
System.out.println("ENTER YOUR SECOND MATRIX SIZE:");
m2=s.nextInt();
n2=s.nextInt();
int a[][]=new int[m1][n1];
int b[][]=new int[m2][n2];
int c[][]=new int[m1][n1];
int m[][]=new int[m1][n1];
int d[][]=new int[m1][n1];
System.out.println("ENTER YOUR FIRST MATRIX ELEMENTS:");
for(i=0;i<m1;i++)
{
for(j=0;j<n1;j++)
{
a[i][j]=s.nextInt();
if(a[i][j]!=0)
{ [5]
 obj.create1(a[i][j],i,j);
}
}
}
System.out.println("ENTER YOUR SECOND MATRIX ELEMENTS:");
for(i=0;i<m2;i++)
{
for(j=0;j<n2;j++)
{
b[i][j]=s.nextInt();
if(b[i][j]!=0)
{
obj.create2(b[i][j],i,j);
}
}
}

System.out.println("YOUR FIRST MATRIX IS:");

obj.display1();
System.out.println("YOUR SECOND MATRIX IS:");
obj.display2();
do
{
System.out.println("ENTER YOUR CHOICE OF OPERATION:");
System.out.println("1.ADDITION:");
System.out.println("2.SUBTRACTION:");
System.out.println("3.MULTIPLICATION:");
System.out.println("4.EXIT:");
ch=s.nextInt();
switch(ch)
{
case 1:
for(i=0;i<m1;i++)
{
for(j=0;j<n1;j++)
{
c[i][j]=a[i][j]+b[i][j];
if(c[i][j]!=0)
{
obj.createa(c[i][j],i,j);
}
}
}
obj.displaya();
break; [6]
 case 2:
for(i=0;i<m1;i++)
{
for(j=0;j<n1;j++)
{
d[i][j]=a[i][j]-b[i][j];
if(d[i][j]!=0)
obj.creates(d[i][j],i,j);
}
}
obj.displays();
break;
case 3:
if(m1==n2 && m2==n1)
{
for (i = 0; i < m1; i++)
{
for (j = 0; j < n2; j++)
{
for (k = 0; k < m2; k++)
{
sum = sum + a[i][k]*b[k][j];
}
m[i][j] = sum;
sum = 0;
}
}
}
else
System.out.println ("THE MATRIX MULTIPLICATION IS NOT
POSSIBLE:");
for(i=0;i<m1;i++)
{
for(j=0;j<n1;j++)
{
if(m[i][j]!=0)
obj.createm(m[i][j],i,j);
}
}
obj.displaym();
break;
case 4:
System.out.println ("ended");
break;
default : [7]
 System.out.println("WRONG OPTION:");
}

}while(ch>=1 && ch<=4);

s.close();
}
void create1(int x,int mr,int mc)
{
Node r1=new Node();
r1.value=x;
r1.row=mr;
r1.col=mc;
r1.nxt=null;
if(head1==null)
{
head1=tail1=r1;
}
else
{
tail1.nxt=r1;
tail1=r1;
}
}
void create2(int x,int mr,int mc)
{
Node r2=new Node();
r2.value=x;
r2.row=mr;
r2.col=mc;
r2.nxt=null;
if(head2==null)
{
head2=tail2=r2;
}
else
{
tail2.nxt=r2;
tail2=r2;
}
}
void display1()
{
temp=r=s=head1;
System.out.println("row :");
while(temp!=null) [8]
 {
System.out.println(temp.row);
temp=temp.nxt;
}
System.out.println("\n");
System.out.println("column :");
while(r!=null)
{
System.out.println(r.col);
r=r.nxt;
}
System.out.println("\n");
System.out.println("value :");
while(s!=null)
{
System.out.println(s.value);
s=s.nxt;
}
System.out.println("\n");
}
void display2()
{
temp=r=s=head2;
System.out.println("row :");
while(temp!=null)
{
System.out.println(temp.row);
temp=temp.nxt;
}
System.out.println("\n");
System.out.println("column :");
while(r!=null)
{
System.out.println(r.col);
r=r.nxt;
}
System.out.println("\n");
System.out.println("value :");
while(s!=null)
{
System.out.println(s.value);
s=s.nxt;
}
System.out.println("\n");
} [9]
 void createa(int x,int mr,int mc)
{
Node ra=new Node();
ra.value=x;
ra.row=mr;
ra.col=mc;
ra.nxt=null;
if(heada==null)
{
heada=taila=ra;
}
else
{
taila.nxt=ra;
taila=ra;
}
}
void displaya()
{
temp=r=s=heada;
System.out.println("YOUR NEW MATRIX AFTER ADDITON OPERATION
IS:");
System.out.println("row :");
while(temp!=null)
{
System.out.println(temp.row);
temp=temp.nxt;
}
System.out.println("\n");
System.out.println("column :");
while(r!=null)
{
System.out.println(r.col);
r=r.nxt;
}
System.out.println("\n");
System.out.println("value :");
while(s!=null)
{
System.out.println(s.value);
s=s.nxt;
}
System.out.println("\n");
}
void creates(int x,int mr,int mc) [10]
{
Node rs=new Node();
rs.value=x;
rs.row=mr;
rs.col=mc;
rs.nxt=null;
if(heads==null)
{
heads=tails=rs;
}
else
{
tails.nxt=rs;
tails=rs;
}
}
void displays()
{
temp=r=s=heads;
System.out.println("YOUR NEW MATRIX AFTER SUBTRACTION:");
System.out.println("row :");
while(temp!=null)
{
System.out.println(temp.row);
temp=temp.nxt;
}
System.out.println("\n");
System.out.println("column :");
while(r!=null)
{
System.out.println(r.col);
r=r.nxt;
}
System.out.println("\n");
System.out.println("value :");
while(s!=null)
{
System.out.println(s.value);
s=s.nxt;
}
System.out.println("\n");
}
void createm(int x,int mr,int mc)
{
Node rm=new Node(); [11]
 rm.value=x;
rm.row=mr;
rm.col=mc;
rm.nxt=null;
if(headm==null)
headm=tailm=rm;
else
{
tailm.nxt=rm;
tailm=rm;
}
}
void displaym()
{
temp=r=s=headm;
System.out.println("YOUR NEW MATRIX AFTER MULTIPLICATION
OPERATION:");
System.out.println("row :");
while(temp!=null)
{
System.out.println(temp.row);
temp=temp.nxt;
}
System.out.println("\n");
System.out.println("column :");
while(r!=null)
{
System.out.println(r.col);
r=r.nxt;
}
System.out.println("\n");
System.out.println("value :");
while(s!=null)
{
System.out.println(s.value);
s=s.nxt;
}
System.out.println("\n");
}
}

[12]
 INTEGRATION AND SYSTEM TESTING
OUTPUTS
Screen Shots:

[13]
[]
[15]
[16]
[17]
 CONCLUSION
Previously, we introduced a sparse matrix approach to information
retrieval. This approach represented the inverted index as a sparse matrix. The
motivation for the approach was the reuse of prior mathematical efforts for a
novel application, namely information retrieval. However, the approach was not
evaluated until now where an evaluation of this approach demonstrated up to a
30% reduction in storage space over a conventional approach.

In the future, we will evaluate the approach using traditional information

retrieval measures such as precision and recall and will implement the approach
on a parallel platform.

[18]