TR-2010-03
An Analysis of Parallel U-cycle Multigrid Method
Dexuan Xie; L. Ridgway Scott. 20 April, 2010.
Communicated by L. Ridgway Scott.
Abstract
Standard parallel versions of the traditional V-cycle multigrid method
often leave processors idle for significant periods of time.
One simple solution to this problem is to define an intermediate grid
to be the new ``coarsest'' grid, one that
is fine enough to keep all processors busy during the calculations.
For clarity, the V-cycle method using this strategy is called the U-cycle
multigrid method due to a ``U'' shape of its grid schedule in comparison to
the grid schedule of the original V-cycle method.
The purpose of this paper is to give this U-cycle approach a mathematical
justification and to show by experiments that it works in practice.
In particular, it is proved that the convergence rate of the U-cycle method
actually improves gradually with the decrease of the number of grid levels.
Further, the coarsest grid equations can be solved approximately without
increasing the total number of iterations as required to satisfy a
convergence criterion.
The time complexity analysis shows that the parallel U-cycle multigrid
method can be fully scalable.
In addition, to fairly measure the parallel performance on a large scale
parallel computer, memory constrained efficiency is used in
the scalability analysis of the parallel U-cycle method.
This is also known today as weak scaling.
Finally, numerical results confirm the theoretical results and demonstrate
the performance of the U-cycle method on a large scale parallel computer
(an IBM BlueGene/L system) with up to 1024 processors.
Original Document
The original document is available in PDF (uploaded 20 April, 2010 by
L. Ridgway Scott).
