next up previous
Next: Full Approximation Scheme (FAS) Up: Advanced Relaxation Methods Previous: Elements of the Multigrid

Why Does it Work?

There has been considerable mathematical research on the convergence properties of multigrid [24]. Formal proofs have generally been too conservative in estimating the efficiency of the method, and the original reasoning was given by a local mode analysis [21]. We have shown above how the convergence properties of the solution degrade on fine scales or large grids. The reason is that the eigenvalues of the propagator matrix for the long wavelength modes are very close to one in magnitude. The multigrid CGC cycle gets around this problem in a clever way. By going to the coarser scale, now the eigenvalues of the longest wavelength modes in the propagator decrease in magnitude. Iterations there damp out the longer wavelength portions of the error. When the corrections are applied to the fine scale solution, large improvements are thus made in that part of the problem. Something is not gotten completely for nothing, though, because some additional short wavelength error components are also introduced during CGC. Therefore, new iterations are required again on the fine scale to damp out those modes. Both parts, fine grid iteration and CGC, conspire together to eliminate modes of the error on all scales, as long as the CGC corrections are extended to coarser and coarser grids in a repeated process. The CGC cycles cost very little since they are carried out on grids with many fewer sample points; the major part of the computational cost of the algorithm is the set of fine grid iterations. Typically an MG solver converges to within the errors caused by placing the problem on the grid with on the order of ten or fewer fine grid iterations. Using these MG correction cycles (described in clear detail by Briggs [18]), we can solve problems involving long ranged Coulomb interactions with scaling of computer time that grows linearly with lattice size (hence, essentially, with system size).


next up previous
Next: Full Approximation Scheme (FAS) Up: Advanced Relaxation Methods Previous: Elements of the Multigrid
root
7/28/1997