Parallel Implementation of Multigrid Methods

Linda Stals


Many techniques which have been developed to model physical problems on a
computer involve the solution of a system of equations. Solving this
system is often one of the most expensive parts of the whole process,
consequently finding fast and efficient solvers has been the focus of
much research.

One particular solver is the multigrid method. In this method the
problem is solved on several layers of grids, with the solution from the
coarse grids being used to improve the solution on the fine grid. The
techniques used to solve the problem on the coarse grids are very cheap
and 'unsophisticated', however, the multigrid method is able to
combine these simple building blocks in such a way as to create a very
flexible and powerful algorithm. In fact, it has been shown that for many
different types of partial differential equations the multigrid method is
optimal.

In this talk I plan to describe the multigrid method and talk about some
of its implementation issues. Specifically its parallel implementation.
The extra data dependencies defined by the multiple layers of grids means
that the parallel implementation has to be done carefully.

I shall refer to a parallel C++ multigrid code I have written as a means
of highlighting some of the issues. The code uses a flexible data
structure which allows us to refine the grid, balance the load, build the
system of equations and solve the system of equations all in parallel.

I also intend to briefly look at the Plasma Ion Immersion Process as an
example application.


--/--

Short Biographical statement:

        I received my PhD in 1996 from the Mathematics Department at
the Australian National University.

        After completing my PhD I started a post-doctoral position in
the Mathematics Department at Universitaet Augsburg, Germany. I stayed
there for one and half years. I then went to England to take up another
post-doctoral position in the Mathematics Department at the University 
of Bath.

        At the end of 1998 I moved here to start a joint project with the
Old Dominion University and ICASE.