How can one parallelize a multigrid method for solving a linear system of equations?

Question

As I understand it, the multigrid method solves a linear system by solving a coarser version of the same problem (there by eliminating low frequency error) then projecting back to the fine grid to smoothen out the high frequency errors. For large systems, i can see how an iterative method can be implemented in parallel at each gridlevel. Does this approach scale well in parallel? Is there any other source of concurrency in the algorithm that one can exploit in parallel?

Answer 1

Parallel geometric multigrid is straightforward to implement on structured grids. Algebraic and unstructured multigrid are more technical, see this answer for links to implementations.

In a multiplicative method (e.g. $V$-cycles), only one level can be computed on at a time. Since the number of levels is $\log_{c} N$ where $N$ is the number of degrees of freedom and $c$ is the coarsening factor (usually about $2^d$ or $3^d$ in $d$ dimensions), this logarithmic term is not removable. Additive methods sacrifice some constant factors, but can compute all levels concurrently, thus reducing the logarithmic factor to $\log_2 \log_c N$. I have yet to see an demonstration on real hardware in which the increased concurrency justifies the poorer constants and reduced robustness of additive methods.

Gauss-Seidel is a very popular smoother which is multiplicative and would seem not to parallelize efficiently. For simple discretizations on structured grids, and when memory bandwidth is not a concern, the classical solution of red-black Gauss-Seidel is reasonable. For more complex problems and on modern hardware, Adams (2001) shows a much more efficient algorithm. For many problems, the simple approach of using independent Gauss-Seidel on each subdomain is entirely satisfactory. An alternative to Gauss-Seidel is to use damped Jacobi or polynomial smoothers, see Adams, Brezina, Hu, and Tuminaro (2003) for a comparison. The performance model for these smoothers is similar to any other stencil computation, and thus have optimal weak scalability, $\mathcal O (N/P)$ for subdomains large enough to cover latency.

In practice, coarse grids quickly reach the strong scalability limit (beyond which adding more processes increases run-time), so they should reside on ever smaller MPI communicators. This adds some mild complexity to the implementation. For problems in which the coarse levels have too much structure to continue coarsening, the coarse level solve can become a bottleneck.

For testing various parallel multigrid methods, I recommend using a library like PETSc which allow you to run many different algorithms with very little user code.