You cannot copy content of this page.

Tag Archive Sparse matrix

Sparse Matrix representation for polynomials

Sparse Matrix representation for polynomials

Program to represent two polynomials using Sparse Matrix representation using arrays, compute sum of two polynomials and represent the result using sparse matrix:

/* Sparse Matrix Representation for Polynomials */

#include <stdio.h>
#include <stdlib.h>

#define MAX 15

int main(){
int poly1[MAX][MAX]={0},poly2[MAX][MAX]={0},poly3[MAX][MAX]={0};
int i,j,k,m,n,nrows,nrows1,nrows2,nrows3,ncols,ct=0,ct1=0,ct2=0;
int spmat1[MAX][MAX]={0},spmat2[MAX][MAX]={0},spmat3[MAX][MAX]={0};
int deg,deg1,deg2,deg3;
printf(“nEnter degree of first polynomial?”);
scanf(“%d”,&deg1);
printf(“nEnter degree of second polynomial?”);
scanf(“%d”,&deg2);
deg3=(deg1>deg2)?deg1:deg2;

printf(“nFor first polynomial:”);
for(i=0;i<=deg1;i++){
printf(“nEnter coefficient for exponent %d> “,i);
scanf(“%d”,&poly1[0][i]);
if(poly1[0][i] != 0)
ct1++;
}
nrows1 = ct1 + 1;
ncols = 3;
spmat1[0][0] = 1;
spmat1[0][1] = deg1 + 1;
spmat1[0][2] = ct1;
m=1;
n=0;
for(i=0;i<1;i++){
for(j=0;j<deg1+1;j++){
if(poly1[i][j] != 0){
spmat1[m][n++]=i;
spmat1[m][n++]=j;
spmat1[m][n]=poly1[i][j];
m++;
n=0;
}
}
}
for(i=0;i<nrows1;i++){
for(j=0;j<ncols;j++)
printf(“%dt”,spmat1[i][j]);
printf(“n”);
}
ct2=0;
printf(“nFor second polynomial:”);
for(i=0;i<=deg2;i++){
printf(“nEnter coefficient for exponent %d> “,i);
scanf(“%d”,&poly2[0][i]);
if(poly2[0][i] != 0)
ct2++;
}
nrows2 = ct2 + 1;
ncols = 3;
spmat2[0][0] = 1;
spmat2[0][1] = deg2+1;
spmat2[0][2] = ct2;
m=1;
n=0;
for(i=0;i<1;i++){
for(j=0;j<deg2+1;j++){
if(poly2[i][j] != 0){
spmat2[m][n++]=i;
spmat2[m][n++]=j;
spmat2[m][n]=poly2[i][j];
m++;
n=0;
}
}
}
for(i=0;i<nrows2;i++){
for(j=0;j<ncols;j++)
printf(“%dt”,spmat2[i][j]);
printf(“n”);
}
printf(“nGenerating sum of polynomials…!”);
printf(“nPress any key to continue…”);

deg = deg1<deg2?deg1:deg2;
for(i=0;i<=deg;i++){
poly3[0][i]=poly1[0][i]+poly2[0][i];
ct++;
}
for(;i<=deg1;i++){
poly3[0][i]=poly1[0][i];
ct++;
}
for(;i<=deg2;i++){
poly3[0][i]=poly2[0][i];
ct++;
}
nrows = ct+1;
ncols = 3;
spmat3[0][0]=1;
spmat3[0][1]=ct;
spmat3[0][2]=ct;
m=1;
n=0;
for(i=0;i<1;i++){
for(j=0;j<deg+1;j++){
if(poly3[i][j] != 0){
spmat3[m][n++]=i;
spmat3[m][n++]=j;
spmat3[m][n]=poly3[i][j];
m++;
n=0;
}
}
}
printf(“nnAddition Result:nn”);
for(i=0;i<nrows;i++){
for(j=0;j<3;j++)
printf(“%dt”,spmat3[i][j]);
printf(“n”);
}
for(i=0;i<=deg1;i++)
printf(“(%d*x^%d)->”,poly1[0][i],i);

printf(“bb n”);

for(i=0;i<=deg2;i++)
printf(“(%d*x^%d)->”,poly2[0][i],i);

printf(“bb n”);

for(i=0;i<=deg3;i++)
printf(“(%d*x^%d)->”,poly3[0][i],i);

printf(“bb n”);

}

Tags, ,

Program to represent two polynomials using arrays and compute their sum

Sparse Polynomial representation and addition

Program to represent two polynomials using arrays and compute their sum

/* Representation of Polynomials using arrays */
/* Addition of two Polynomials */

#include <stdio.h>

#define MAX 10

int main(){
int poly1[MAX]={0},poly2[MAX]={0},poly3[MAX]={0};
int i,deg1,deg2,deg3;
printf(“nEnter degree of first polynomial?”);
scanf(“%d”,&deg1);
printf(“nEnter degree of second polynomial?”);
scanf(“%d”,&deg2);

printf(“nFor first polynomial:”);
for(i=0;i<deg1;i++){
printf(“nEnter Coefficient for Exponent %d> “,i);
scanf(“%d”,&poly1[i]);
}
printf(“nFor second polynomial:”);
for(i=0;i<deg2;i++){
printf(“nEnter Coefficient for Exponent %d> “,i);
scanf(“%d”,&poly2[i]);
}
printf(“nGenerating sum…!”);
printf(“nPress any key to continue…”);

deg3 = (deg1>deg2)?deg1:deg2;

for(i=0;i<deg3;i++)
poly3[i] = poly1[i] + poly2[i];
printf(“nnAddition Result:nn”);

for(i=deg1-1;i>=0;i–)
printf(“(%dx^%d)+”,poly1[i],i);
printf(“b n”);

for(i=deg2-1;i>=0;i–)
printf(“(%dx^%d)+”,poly2[i],i);
printf(“b n”);

for(i=deg3-1;i>=0;i–)
printf(“(%dx^%d)+”,poly3[i],i);
printf(“b n”);

}

Tags, ,

Sparse Polynomial representation and addition

Sparse Polynomial representation and addition:

Polynomial is an expression which is composed of terms, wherein terms are composed of coefficient and exponent.  An example of a polynomial is: 4x3+5x2+6x+9.  This polynomial is composed of four terms with the following sets of coefficient and exponent – {(4,3), (5,2), (6,1), (9,0)}.  Thus representation of a polynomial using arrays is straightforward.  The subscripts of the array may be considered as exponents and the coefficients may be stored at an appropriate place referred to by the subscript.  Array representation for the above example is:

arr:                9          6        5        4         coefficients

subscripts: 0         1        2         3          exponents

The above representation works fine for the above example, but for polynomials such as 5×6+7, array representation is considered feasible on account of memory usage, since it results in a sparse arrangement as follows:

 

arr    7         0         0        0        0        0          5

         0          1          2        3         4        5          6 (Subscripts)
Sparse matrix representation may be considered for the above matrix as given below:

Rows                     Cols                       Value
———————————————————–

1                              7                              2              (Total)

0                              0                              7

0                              6                              5

For addition of two polynomials using arrays, subscript-wise elements may be added to result in the polynomial containing result of addition of two polynomials.

Example:

Polynomial 1:     4x3 + 5x2 + 6x + 7

Polynomial 2:     3x3 + 4x2 + 2x + 2

———————–

7x3 + 9x2 + 8x + 9

———————–

Array Representation:

Subscripts:           0              1              2              3

———————————————————

Polynomial 1:     7              6              5              4

Polynomial 2:     2              2              4              3

Result of sum:   9              8              9               7

 
Program to represent two polynomials using arrays and compute their sum

Tags, ,

Program to represent Sparse Matrix using singly linked list (One dimensional list)

Sparse Matrix representation using singly Linked List:

/* Sparse Matrix representation using linked list */
#include <stdio.h>
#include <stdlib.h>

typedef struct list{
int rows, cols, value;
struct list *next;
}list;

list *create(){
list *temp = (list *)malloc(sizeof(list));
if(temp==NULL){
printf(“nMemory Allocation Error !”);
exit(1);
}
return temp;
}

list *makenode(int r, int c, int val){
list *temp = create();
temp->rows = r;
temp->cols = c;
temp->value = val;
temp->next = NULL;
return temp;
}

list *insert(list *head, int r, int c, int val){
list *ptr, *temp = head;
if(head == NULL){
head = makenode(r,c,val);
}
else{
while(temp->next != NULL)
temp = temp->next;
ptr = makenode(r,c,val);
temp->next = ptr;
}
return head;
}

void display(list *head){
list *temp;
if(head == NULL){
printf(“nList is empty.”);
exit(1);
}
temp = head;
while(temp != NULL){
printf(“(%d,%d,%d->)->”,temp->rows,temp->cols,temp->value);
temp = temp->next;
}
printf(“bb “);
}

int main(){
int arr[3][4],i,j,m,n,ct=0;
list *head = NULL;
for(i=0; i<3; i++){
printf(“nEnter the values for row %d?”, i+1);
for(j=0;j<4;j++){
scanf(“%d”,&arr[i][j]);
if(arr[i][j] != 0)
ct++;
}
}
head = makenode(3,4,ct);
for(i=0;i<3;i++){
for(j=0;j<4;j++){
if(arr[i][j] != 0)
head = insert(head,i,j,arr[i][j]);
}
}
printf(“nList representation of Sparse Matrix is: n”);
display(head);
getch();
}

Tags, ,

Program to represent Sparse Matrix using arrays

Program to represent Sparse Matrix using arrays:

/* Sparse Matrix representation using arrays */

#include <stdio.h>
#include <stdlib.h>

#define MAX 15

int main(){
int arr[3][4],i,j,m,n,nrows,ncols,ct=0;
int sparse_matrix[MAX][MAX];
for(i=0;i<3;i++){
printf(“nEnter values for row %d?”,i+1);
for(j=0;j<4;j++){
scanf(“%d”,&arr[i][j]);
if(arr[i][j] != 0)
ct++;
}
}
nrows = ct+1;
ncols = 3;
sparse_matrix[0][0] = 3;
sparse_matrix[0][1] = 4;
sparse_matrix[0][2] = ct;
m=1;
n=0;
for(i=0;i<3;i++){
for(j=0;j<4;j++){
if(arr[i][j]!=0){
sparse_matrix[m][n++]=i;
sparse_matrix[m][n++]=j;
sparse_matrix[m][n]=arr[i][j];
m++;
n=0;
}
}
}
printf(“nThe new sparse matrix in 3-tuple representation is:n”);
for(i=0;i<nrows;i++){
for(j=0;j<ncols;j++){
printf(“%dt”,sparse_matrix[i][j]);
}
printf(“n”);
}
}

Tags, ,

x Close

Like Us On Facebook