CS 240A, Homework 3

 There are  three parts to this  homework.  You are  to write routines
 for:

 1. Multiplying a sparse matrix by a dense vector.

 2. Solving a sparse linear  system by conjugate gradients, using part
    (1)

 3. Two data generation routines,  which will generate sparse matrices
    (in parallel) to be used in parts (1) and (2)


 The matrix should be distributed as a parallel CSR structure.


1. Sparse matvec

 The bulk of the work of CG  will be done in a matvec call.  Since the
matrix is sparse,  it is important to distribute  the rows properly so
that no one processor is left with all the computational work.  In the
first data generator that you  will write, the matrix will be regular,
and so  the distribution of  the rows will  be easy.  The  second data
generator will  not have this regular structure,  and thus performance
of the matvec will depend on good distribution of data.


2. Conjugate Gradient


The computation part of this homework involves writing a linear solver
using the conjugate gradient method.  A reference implementation of CG
in Matlab is posted on  the website.

 We are  solving Ax=b.  The conjugate gradient  routine calculates and
 returns x.

 The signature for the conjugate gradient is:

 double *conjugate(PPcsr *A, double *b_vals, double tol, int maxit);

 Where tol  is the tolerance  that is desired.   When the norm  of the
 residual is tol  times the norm of the initial  residual, then the CG
 should stop.  When turning in the code, set tol to 10e-11

 Maxit is the max number  of iterations, similar to what was discussed
 in class on Monday.  The CG should stop if maxit number of iterations
 are already done.  When turning in the code, set maxit to n/4.

 b_vals is the local part of the b vector on this processor.

 conjugate returns a pointer to the solution x, which is distributed.

 The  CG routine  should print  out the  following data  on successful
 completion, as in the example output below:
 Number of iterations: 310
 Tol=1e-10,  maxit=10000
 Norm of the initial residual=200
 Norm of the final residual=5.23e-8

 The conjugate gradient should also write the final answer to the file
called "x.txt" with each element of x(i) on a line by itself.

 Once you finish writing this, you will have a parallel implementation
of an unpreconditioned conjugate gradient that you should hopefully be
able to use elsewhere as well.


3. Data Generators

In  large parallel  programs,  the data  cannot  all fit  on a  single
processor, and  so in this case,  we generate the data  in parallel as
well. Two data generators are  required in this assignment, though you
are free to write other generators to debug your code.

 * Data generator  for the  Poisson problem in  three dimensions  on a
   regular k-by-k-by-k grid. Each node of the grid is connected to its
   immediate neighbors  in all  three axes (x,y,z).  Every node  has 6
   neighbors  except the  ones on  the  boundaries. The  matrix is  an
   n-by-n sparse matrix, where n = k^3. The values of the matrix A are

   A(i,j) = -1  (i not equal to j, and i,j are neighbors in the mesh)
   A(i,i) = degree(i) = 6


 * Data generator for a matrix  based on the following graph: Consider
   the unit cube in three  dimensions, consisting of all points (x, y,
   z) with x, y, and z between  0 and 1. Generate n points inside this
   cube at random (each coordinate  is chosen uniformly at random from
   the interval [0,1]). The points  are the vertices of the graph. Two
   points are joined by an edge if their Euclidean distance is at most
   1.5/n^(1/3).  The  n-by-n sparse matrix  A has A(i,i) equal  to one
   plus the degree of vertex i, and  has A(i,j) = -1 if vertices i and
   j are neighbors in the graph.


   Note that both these matrices are symmetric


 The signature of the data generators is:
 PPscr *data_generate(n)

 data_generate  returns  only the  matrix  A.   The  vector b  can  be
 generated elsewhere,  since it is not  difficult, and can  be used to
 call the conjugate gradient.
 
 Along  with the  data generators,  you should  provide  the following
 functions to enable testing of your code.

 * A function to return the matrix generated.  This function will also
   be  useful to  you  while  debugging and  testing  your code.   The
   signature for this function is:

   void data_A_return();

   The data_A_return  function writes to a  file called "matrixA.txt",
   and writes  the matrix  as the ordered  triple: i, j,  A(i,j).  The
   first line of this matrix is  n, the dimension.  So the Unit 3-by-3
   matrix is written as:

   n
   1, 1, 1
   2, 2, 1
   3, 3, 1

   For both these generators, b(i) =  100 on the first k^2 nodes and 0
   otherwise, and is not generated by the data_generate function.



CVS and other infrastructure:

 Current CVS instructions for this homework will be available at:

 http://www.cs.ucsb.edu/~cs240a/hw3.html

 Please  follow the  Google Groups  closely because  a lot  of related
information is  discussed there.  Also, TAs  will announce information
related  to the  homework on  Google groups  before the  web-page gets
updated.

Grading:

 There will be credit for performance for both the data generators and
the  conjugate  gradient.   The  data_A_return()  function  should  be
correct to enable  us to grade your homework, but  will not be checked
for performance.

 If you do  not adhere to the class  infrastructure: cvs, make, proper
 filenames, your grade will be solely at the discretion of the grader.


Turning in:

 Submission requires code in  the languages assigned, along with plots
of performance  of your code on  various input sizes (as  large as you
can).


 Homework submissions  are only  permitted through the  turnin script,
and a penalty  will be imposed if the turnin script  is not used.  The
homework is  due on  Monday, 23  May, at 2359hrs.   There shall  be no
extension on the deadline for this homework, so do begin early.