class App1

{

public static void main(String args[])

{

EasyIn easy = new EasyIn();

System.out.println("Size of the vector to generate?");

int n = easy.readInt(); // size

Vector v1,v2,v3; // vectors

// Define vectors

v1=new VectorArray(n);

v2=new VectorArray(n);

// fill up the vectors

v1.fill(); // random

for (int i=0;i

// Add vectors v1+v2

v3=new VectorArray(n);

for (int i=0;i

v3.set(i,v1.get(i)+v2.get(i));

}

System.out.println("Vector 1");

v1.display();

System.out.println("Vector 2");

v2.display();

System.out.println("Vector 1 + Vector 2");

v3.display();

System.out.println("Vector normLoo= "+v3.normLoo()+" normL2= "+v3.normL2());

}

}

class App2

{

public static void main(String args[])

{

EasyIn easy = new EasyIn();

System.out.println("Size of the vector to generate?");

int n = easy.readInt(); // size

Vector v1,v2,v3; // vectors

// Define vectors

v1=new VectorLL(n);

v2=new VectorLL(n);

// fill up the vectors

v1.fill(); // random

for (int i=0;i

// Add vectors v1+v2

v3=new VectorLL(n);

for (int i=0;i

v3.set(i,v1.get(i)+v2.get(i));

}

System.out.println("Vector 1");

v1.display();

System.out.println("Vector 2");

v2.display();

System.out.println("Vector 1 + Vector 2");

v3.display();

System.out.println("Vector normLoo= "+v3.normLoo()+" normL2= "+v3.normL2());

}

}

class App3

{

public static void main(String args[])

{

int n=3; //size

// define a Matrix

Matrix A=new DenseMatrix(n);

//Set Elements

A.set(0,0,2.0);

A.set(0,1,1.0);

A.set(1,1,1.0);

A.set(1,2,-3.0);

A.set(2,0,1.0);

A.set(2,2,1.0);

A.info(); // display info

A.display(); // display matrix in dense format

// Define a vector

Vector b=new VectorArray(A.getSize());

b.set(0,1.0);

b.set(1,1.0);

b.set(2,1.0);

System.out.println("Vector b");

b.display();

// multiplication

Vector f=A.multiply(b); // f=A*b

System.out.println("Matrix-Vector Multiplication x=A*b");

f.display();

}

}

class App4

{

public static void main(String args[])

{

int n=3; //size

// define a Matrix

Matrix A=new SparseMatrixLinkedList();

//Set Elements

A.set(0,0,2.0);

A.set(0,1,1.0);

A.set(1,1,1.0);

A.set(1,2,-3.0);

A.set(2,0,1.0);

A.set(2,2,1.0);

A.info(); // display info

A.display(); // display matrix in sparse format

// Define a vector

Vector b=new VectorArray(A.getSize()); // we could use LL or array

b.set(0,1.0);

b.set(1,1.0);

b.set(2,1.0);

System.out.println("Vector b");

b.display();

// multiplication

Vector f=A.multiply(b); // f=A*b

System.out.println("Matrix-Vector Multiplication x=A*b");

f.display();

}

}

class App5

{

public static void main(String args[])

{

int n=3; //size

int nnz=6; /nz (non-zero elements)

Matrix A1=new DenseMatrix(n);

//Set Elements

A1.set(0,0,2.0);

A1.set(0,1,1.0);

A1.set(1,1,1.0);

A1.set(1,2,-3.0);

A1.set(2,0,1.0);

A1.set(2,2,1.0);

System.out.println("Original Matrix in Dense Format");

A1.info();

A1.display(); // display matrix in dense format

Matrix A2=new SparseMatrixLinkedList(A1); // from dense to sparse

System.out.println("Original Matrix in Linked-List Format");

A2.info();

A2.display(); // display matrix in link-list format

A2.set(0,0,1.0); // change one element

A2.set(5,2,1.0); // increase dynamically

System.out.println("Modified Matrix in Linked-List Format");

A2.info();

A2.display(); // display matrix in link-list format

Matrix A3=new DenseMatrix(A2);

A3.info();

A3.display(); // display matrix in dense format

System.out.println("Diagonal elements");

double[] diagS=A2.getDiagonal();

double[] diagD=A3.getDiagonal();

for (int i=0;i

System.out.println();

}

}

class App6

{

public static void main(String args[])

{

int size,nnz;

long startTime, endTime;

EasyIn easy = new EasyIn();

// dense matrix A1

System.out.println("Size of the dense matrix to generate?");

size = easy.readInt();

System.out.println("Nb of non-zero elements?");

nnz = easy.readInt();

Matrix A1=new DenseMatrix(size,nnz);

A1.info();

// sparse matrix A2 (from dense to sparse)

Matrix A2=new SparseMatrixLinkedList(A1);

A2.info();

// Vector b and fill randomly

Vector b=new VectorArray(A1.getSize()); // array based-implementation

//Vector b=new VectorLL(A1.getSize()); // linked list based implementation

b.fill(); // fill randomly

// multiplication A1*b

startTime = System.currentTimeMillis(); // capture time

Vector x=A1.multiply(b); // x=A1*b

endTime = System.currentTimeMillis(); // capture time

System.out.println("Matrix-Vector Multiplication using dense matrix done in "+(endTime-startTime)+"ms");

// multiplication A2*b

startTime = System.currentTimeMillis(); // capture time

x=A2.multiply(b); // x=A2*b

endTime = System.currentTimeMillis(); // capture time

System.out.println("Matrix-Vector Multiplication using sparse matrix done in "+(endTime-startTime)+"ms");

}

}

class App7

{

public static void main(String args[])

{

int size,nnz;

long startTime, endTime;

EasyIn easy = new EasyIn();

// sparse matrix A

System.out.println("Size of the sparse matrix to generate?");

size = easy.readInt();

System.out.println("Nb of non-zero elements?");

nnz = easy.readInt();

Matrix A=new SparseMatrixLinkedList(size,nnz);

A.info();

// Define a vector

Vector b=new VectorArray(A.getSize()); // array based-implementation

b.fill(); // fill randomly

// multiplication

startTime = System.currentTimeMillis(); // capture time

Vector x=A.multiply(b); // x=A*b

endTime = System.currentTimeMillis(); // capture time

System.out.println("Matrix-Vector Multiplication using sparse matrix done in "+(endTime-startTime)+"ms");

}

}

class App8

{

public static void main(String args[])

{

int size,nnz;

EasyIn easy = new EasyIn();

Matrix A;

Vector x;

// sparse matrix A

System.out.println("Size of the sparse matrix to generate? (Enter 0 for pregenerated Matrix)");

size = easy.readInt();

if (size!=0) {

System.out.println("Nb of non-zero elements?");

nnz = easy.readInt();

A=new SparseMatrixLinkedList(size,nnz);

x=new VectorArray(A.getSize()); // array based-implementation

x.fill(); // fill randomly (initial guess)

}

else

{

A=new SparseMatrixLinkedList();

A.set(0,0,1.5);

A.set(0,1,0.5);

A.set(1,0,0.5);

A.set(1,1,1.5);

A.display();

x=new VectorArray(A.getSize()); // array based-implementation

// initial guess

x.set(0,0);

x.set(1,1);

}

A.info();

// Compute the *largest* eigenvalue/eigenvector: Ax=lambda x

// Using the power method

// Algo: Iterate: y

// until |lambda-lambda_prev|/|lambda_prev|

double lambda=1,lambda_prev;

double eps=1e-13;

double error=1.0;

/// TO COMPLETE

// Check: Compute norm Residual norm(A*x-lambda*x)

Vector r=A.multiply(x);

for (int i=0;i

System.out.println(" Residual normLoo= "+r.normLoo()+" normL2= "+r.normL2());

}

}

// Simple input from the keyboard for all primitive types. ver 1.0 // Copyright (c) Peter van der Linden, May 5 1997. // corrected error message 11/21/97 // // The creator of this software hereby gives you permission to: // 1. copy the work without changing it // 2. modify the work providing you send me a copy which I can // use in any way I want, including incorporating into this work. // 3. distribute copies of the work to the public by sale, lease, // rental, or lending // 4. perform the work // 5. display the work // 6. fold the work into a funny hat and wear it on your head. // // This is not thread safe, not high performance, and doesn't tell EOF. // It's intended for low-volume easy keyboard input. // An example of use is: // EasyIn easy = new EasyIn(); // int i = easy.readInt(); // reads an int from System.in // float f = easy.readFloat(); // reads a float from System.in

import java.io.*; import java.util.*;

class EasyIn { static InputStreamReader is = new InputStreamReader( System.in ); static BufferedReader br = new BufferedReader( is ); StringTokenizer st;

StringTokenizer getToken() throws IOException { String s = br.readLine(); return new StringTokenizer(s); }

boolean readBoolean() { try { st = getToken(); return new Boolean(st.nextToken()).booleanValue(); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readBoolean"); return false; } }

byte readByte() { try { st = getToken(); return Byte.parseByte(st.nextToken()); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readByte"); return 0; } }

short readShort() { try { st = getToken(); return Short.parseShort(st.nextToken()); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readShort"); return 0; } }

int readInt() { try { st = getToken(); return Integer.parseInt(st.nextToken()); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readInt"); return 0; } }

long readLong() { try { st = getToken(); return Long.parseLong(st.nextToken()); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readLong"); return 0L; } }

float readFloat() { try { st = getToken(); return new Float(st.nextToken()).floatValue(); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readFloat"); return 0.0F; } }

double readDouble() { try { st = getToken(); return new Double(st.nextToken()).doubleValue(); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readDouble"); return 0.0; } }

char readChar() { try { String s = br.readLine(); return s.charAt(0); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readChar"); return 0; } }

String readString() { try { return br.readLine(); } catch (IOException ioe) { System.err.println("IO Exception in EasyIn.readString"); return ""; } }

// This method is just here to test the class public static void main (String args[]){ EasyIn easy = new EasyIn();

System.out.print("enter char: "); System.out.println("You entered: " + easy.readChar() );

System.out.print("enter String: "); System.out.println("You entered: " + easy.readString() );

System.out.print("enter boolean: "); System.out.println("You entered: " + easy.readBoolean() );

//System.out.print("enter byte: "); //System.out.println("You entered: " + easy.readByte() );

System.out.print("enter short: "); System.out.println("You entered: " + easy.readShort() );

System.out.print("enter int: "); System.out.println("You entered: " + easy.readInt() );

System.out.print("enter long: "); System.out.println("You entered: " + easy.readLong() );

System.out.print("enter float: "); System.out.println("You entered: " + easy.readFloat() );

System.out.print("enter double: "); System.out.println("You entered: " + easy.readDouble() ); }

}

import java.util.*;

interface Matrix

{

// Assign the value x to element i,j

void set(int i,int j, double x);

// get the value of the element i,j

double get(int i, int j);

// Extract the diagonal of the matrix

double[] getDiagonal();

// get the size of the matrix-- number of rows

int getSize();

// get the number of non-zero elements

int getNnz();

// Multiply a matrix by a vector

Vector multiply(Vector B);

// Print matrix using a specific format

void display();

// return info about the matrix

void info();

}

//////////////////////////////////// ARRAY DENSE MATRIX IMPLEMENTATION

class DenseMatrix implements Matrix

{

//////// TO COMPLETE--you can uncomment the instructions below

private int size=0; // size of the matrix- number of rows/columns

private int nnz=0; // number of non-zero elements

private double[][] data;

/////// return info about the matrix

public void info(){

System.out.println("Dense Matrix n="+size+", nnz="+nnz+", Storage="+(8*size*size)+"b or "+(8*size*size)/(1024*1024)+"Mb");

}

}

//////////////////////////////////// Linked-List SPARSE MATRIX IMPLEMENTATION

class RowNode{

public int rowindex;

public ColNode col;

public RowNode next;

RowNode(int i){rowindex=i; col=null; next=null;}

}

class ColNode{

public double entry;

public int colindex;;

public ColNode next;

ColNode(int j,double x){

colindex=j;

entry=x;

next=null;}

}

class SparseMatrixLinkedList implements Matrix

{

private RowNode top;

private int size=0;

private int nnz=0;

// constructors

// Basic constructor- no element in the list yet

SparseMatrixLinkedList(){top=null;}

// methods

public void display(){

RowNode current = top; //start probe at the beginning

System.out.println("i");

while (current!=null) { // until the end of the list

System.out.print(current.rowindex+" ");

ColNode jcurrent = current.col;

while (jcurrent!=null) { // until the end of the list

System.out.format("==> (j=%d, a=%.4f)",jcurrent.colindex,jcurrent.entry);

jcurrent = jcurrent.next;

}

System.out.println();

current = current.next; // move to next Link

}

System.out.println();

}

// return info about the matrix

public void info(){

System.out.println("Sparse Matrix n="+size+", nnz="+nnz+", Storage="+(8*nnz)+"b or "+(8*nnz)/(1024*1024)+"Mb");

}

}

import java.util.*;

interface Vector { // randomly fill all entries with number 0

//////////////////////// USING ARRAY IMPLEMENTATION

//class VectorArray implements Vector //{ // //}

//////////////////////// USING Linked-List IMPLEMENTATION

class VecNode{ public int index; public double entry; public VecNode next; VecNode(int i,double x){index=i;entry=x;next=null;} }

//class VectorLL implements Vector //{ // //}

ECE 242: Data Structures and Algorithms- Fall 2017 Project 3: FunWithMatrices Due Date: see Website Description This project is intended to familiarize you with (i) Matrix data structure, (ii) Basic Operations on matrices, (iii) Dynamic Linked-List implementation iv) Interfaces, (v) Analysis of algorithms and Big-O notation The main goal of the project is to design and implement a basic Matrix collections usig ether dense or storage: . A dense storage can be naturally represented by a 2-dimensional arrays. As a resut, Ali will represent the matrix element at the row i and column j . A sparse storage is well optimized to address the case of matrices populated primarily with zeros... It will not store the zero elements. Matrices are ubiquitous in Science and Engineering. For examples, they can arise from (i) the represen- tation of a set of linear equations,i) the discretization of differential equations, or) the representation of graphs connecting various nodes of a network. A simple example on how to form a matrix from a set of linear equations (3 equations, 3 unknowns) s provided below: 2 1 01 [o 1-3 2 leads to 0-3-2 10 1 We consider the matrix A3x3 of size 3 (i.e. number of rows equals to the number of columns both equal to 3) such that. A-1 a 1,0 a 1,21 and obviously here ao,2 1,0-a2',-0 a 1,1 2,0 a2,1 2,2 In general, the main numerical operations on matrices include 1. matrix-vect or multiplications- perform A*x, where z is a vector, 2. solving linear systems-find such that Ax = y, y is a known vector 3. solving eigenvalue problems Ax = 2 find all (eigen)vectors associated with their (eigen)value The majority of problems encountered in scientific and engineering applications gives rise to very large sparse matrices (matrices with a lot of zero elements) As a typical (s to medium) real-life example, consider a linear system consisting of 200,000 equations. If each equation only involves 40 unknowns on average, the resulting matrix will have 40 nonzero elements per row giving a total of 8 106 nonzero entries for the matrix (see Figure 1) When storing and manipulating sparse matrices on the computer, t is often necessary to modify the standard algorithms and take advantage of the sparse data structure of the matrix. A sparse storage where only the non-zero elements of the matrix are stored, can yield enormous savings in both memory usage and computational time. For example, if we decided to store all the 2 105 * 2 105-4 1010 elements of the matrix in Figure 1, one would need (using double) 305Gb of memory! In contrast, the sparse storage would require only 61Mb of memory! In this project, we are using two different ways to store matrices: (i) a traditional dense storage for square matrix, (ii) a linked list-based sparse storage (using the coordinate format) Wewl only deal with square matrices in this project; in other words, our matrices will have the same number of rows as columns, and we will refer to the mber of rows and columns as simply the size of the matrix. In addition, the main numerical operation that we consider here is the matrix-vector multiplication. It is the important basic tool in numerical linear algebra and plays an important role in many applications including page rank computations. ECE 242: Data Structures and Algorithms- Fall 2017 Project 3: FunWithMatrices Due Date: see Website Description This project is intended to familiarize you with (i) Matrix data structure, (ii) Basic Operations on matrices, (iii) Dynamic Linked-List implementation iv) Interfaces, (v) Analysis of algorithms and Big-O notation The main goal of the project is to design and implement a basic Matrix collections usig ether dense or storage: . A dense storage can be naturally represented by a 2-dimensional arrays. As a resut, Ali will represent the matrix element at the row i and column j . A sparse storage is well optimized to address the case of matrices populated primarily with zeros... It will not store the zero elements. Matrices are ubiquitous in Science and Engineering. For examples, they can arise from (i) the represen- tation of a set of linear equations,i) the discretization of differential equations, or) the representation of graphs connecting various nodes of a network. A simple example on how to form a matrix from a set of linear equations (3 equations, 3 unknowns) s provided below: 2 1 01 [o 1-3 2 leads to 0-3-2 10 1 We consider the matrix A3x3 of size 3 (i.e. number of rows equals to the number of columns both equal to 3) such that. A-1 a 1,0 a 1,21 and obviously here ao,2 1,0-a2',-0 a 1,1 2,0 a2,1 2,2 In general, the main numerical operations on matrices include 1. matrix-vect or multiplications- perform A*x, where z is a vector, 2. solving linear systems-find such that Ax = y, y is a known vector 3. solving eigenvalue problems Ax = 2 find all (eigen)vectors associated with their (eigen)value The majority of problems encountered in scientific and engineering applications gives rise to very large sparse matrices (matrices with a lot of zero elements) As a typical (s to medium) real-life example, consider a linear system consisting of 200,000 equations. If each equation only involves 40 unknowns on average, the resulting matrix will have 40 nonzero elements per row giving a total of 8 106 nonzero entries for the matrix (see Figure 1) When storing and manipulating sparse matrices on the computer, t is often necessary to modify the standard algorithms and take advantage of the sparse data structure of the matrix. A sparse storage where only the non-zero elements of the matrix are stored, can yield enormous savings in both memory usage and computational time. For example, if we decided to store all the 2 105 * 2 105-4 1010 elements of the matrix in Figure 1, one would need (using double) 305Gb of memory! In contrast, the sparse storage would require only 61Mb of memory! In this project, we are using two different ways to store matrices: (i) a traditional dense storage for square matrix, (ii) a linked list-based sparse storage (using the coordinate format) Wewl only deal with square matrices in this project; in other words, our matrices will have the same number of rows as columns, and we will refer to the mber of rows and columns as simply the size of the matrix. In addition, the main numerical operation that we consider here is the matrix-vector multiplication. It is the important basic tool in numerical linear algebra and plays an important role in many applications including page rank computations

<>

<>

<>

<>