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

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?

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.