15859E Programming Assignment 2:
Multigrid
Due Date: 11:59pm Wed. 21 Oct. 1998
Revision 2: 14 Oct. 98.
In this assignment,
you'll solve a 2D simulation problem using the multigrid method.
The recommended problem is Poisson's Equation on a unit square,
and working from Briggs' book.
I'm providing a bit of starter code, but not nearly as much
as in the previous assignment.
Requirements

Implement the multigrid algorithm for a simulation problem
in two or more dimensions.
By multigrid, I mean in particular the Vcycle or FMVcycle
or similar method.
You could implement this in C++, C, FORTRAN, Matlab, Java, Mathematica,
Maple, or other languages.
(I used C++).

You must implement the relaxation method, restriction, and
interpolation yourself down to the grid element level,
but you can use other people's code
(from the web, from books) for other parts of the program.

Your program need not be interactive.

Get your program running on a large grid
(at least 60000 unknowns).
The larger, the better.
In the following discussion, for concreteness I'll assume
that your largest (finest) grid is 2D and 256x256.

Demonstrate that your program's solutions are accurate.
If we define rel_residual(v,f) = norm(fAv)/norm(f),
where norm(x) is the L2 norm (square root of the sum of the
squares), then shoot for rel_residual < 1e6.

Demonstrate that it is fast.
Implement a simpler method for reference
(this could be your relaxation method on the finest grid, for example)
and compare the speed of your two methods at
a range of sizes, say 8x8, 16x16, 32x32, ... 256x256.
You probably won't have the patience to run your simple method on
the finer grids (it would take hours), but try to make your
speed comparison table as complete as possible by the deadline.

When preparing this table, make sure that each of the runs
is accurate within the above tolerance.
It's not very meaningful to compare the speeds of methods that
produce solutions of wildly different accuracies.

Make a graph of number of unknowns (probably N^2)
versus time for these two algorithms, labeled clearly with units,
showing (hopefully) that your simple method is very slow,
but multigrid is fast.
You could use gnuplot for this.

Fit a function to the empirical time cost curves.
Are they approximately c*N^k for some k, 1<=k<=6?
Can you determine the constants in the empirical cost formula?

Make a picture of the solution function.
You might try Maple, Mathematica, Matlab, or OpenGL for this.
See the
class software page
for info on availability of the first three packages.
The picture could be grayscale or color, 2D (contour plot, say), or 3D.

Finish your code by the date listed at top.
To submit your program, copy your source code, executable,
and test files (if any) to
students/yourlastname/multigrid.
Include a README file explaining:
what you did,
whether you wrote all the code, and if not, what other code you used
(give author, URL, program name, book and page... as appropriate),
what system your executable runs on (e.g. 900 MHz Pentium 4).
Also include the comparative table mentioned earlier,
and discussion of the functions that fit it.
If you find a text README file too restrictive,
other formats are OK (Latex, Word, Framemaker, Mathematica...).

During class on 22 Oct., turn in a printout of your README,
a printout of your comparative time graph,
and a picture of your solution.
We'll discuss the outcome in class, but
we probably won't do demos, since most of these programs will
be noninteractive.
Tips
15859, Hierarchical Methods for Simulation
Paul Heckbert