From a computer science point of view, the performance evaluation of iterative solvers for large systems of equations does not only include numerical efficiency but also parallel scalability. Whereas multigrid methods are clearly superior from a pure numerical point of view, the majority of parallel solvers available in software packages are based on cg-like methods. These solvers achieve very good scalability on high performance computing platforms even for large processors numbers. In contrast, multigrid methods seem to perform much worse in the parallel context. This arises the question whether they are only a nice theoretical concept but not applicable in an efficient way in supercomputing practice.
Considerations that might lead to such a conclusion often only include so-called strong-scalability results -- constant problem size and growing number of processors. This point of view does not take into account the advantage of multigrid methods -- the constant number of iterations with increasing problem size. Thus, the correct setting must be to consider weak-scalability, that is problem sizes growing according to the processor number, and, in addition, time until convergence instead of only single solver iterations.
This approach leads to a new definition of an optimal solver. Whereas an optimal sequential solver computes the solution of a system in a computational time growing proportional to the number of unknowns, parallelisation even allows to look for solvers with constant computational time. So the question is: Is it possible to implement a solver that solves a system of equations in constant time independent from the size of the system or the mesh resolution, respectively, by suitably increasing the number of processors? In the optimal case, the number of processors increaes only proportional to the problem size.
We will present first a theoretical comparison of cg-like and multigrid methods for parallel computations under simplifying assumptions showing the general potential of multigrid and cg-like solvers on supercomputers and also answering the question on the possibility to develop an optimal parallel solver. In addition, we will relate various parallel multigrid approaches from literature (see for example [1, 2, 3, 4, 6, 7]) to this theoretical analysis and, finally, present results from an own parallel multigrid implementation on adaptive Cartesian grids with tree-structure (see [5] for a decription of the corresponding sequential code). In contrast to the purely theoretical analysis that only takes into account computational and communication costs, this will also give hints on ways to improve other performance aspects such as cache-efficiency that can be an additional stumbling block for high performance multigrid implementations due to the more complex data dependencies compared to cg-like solvers.