Multigrid method: Difference between revisions

Revision as of 00:43, 11 January 2025

Revision as of 14:57, 18 June 2025

Line 174:

This approach has the advantage over other methods that it often scales linearly with the number of discrete nodes used. In other words, it can solve these problems to a given accuracy in a number of operations that is proportional to the number of unknowns.

Assume that one has a differential equation which can be solved approximately (with a given accuracy) on a grid <math>i</math> with a given grid point density <math>N_i</math>. Assume furthermore that a solution on any grid <math>N_i</math> may be obtained with a given effort <math>W_i = \rho K N_i</math> from a solution on a coarser grid <math>i+1</math>. Here, <math>\rho = N_{i+1} / N_i < 1</math> is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and <math>K</math> is some constant modeling the effort of computing the result for one grid point.

density <math>N_i</math>. Assume furthermore that a solution on any grid <math>N_i</math> may be obtained with a given

effort <math>W_i = \rho K N_i</math> from a solution on a coarser grid <math>i+1</math>. Here, <math>\rho = N_{i+1} / N_i < 1</math> is the ratio of grid points on "neighboring" grids and is assumed to be constant throughout the grid hierarchy, and <math>K</math> is some constant modeling the effort of computing the result for one grid point.

The following recurrence relation is then obtained for the effort of obtaining the solution on grid <math>k</math>:

<math display="block">W_k = W_{k+1} + \rho K N_k</math>

:<math>W_k = W_{k+1} + \rho K N_k</math>[[File:Convergence Rate of Multigrid Cycles.svg|alt=Convergence Rate of Multigrid Cycles in comparison to other smoothing operators. Multigrid converges faster than typical smoothing operators. F-Cycle and W-Cycle perform with near equal robustness.|thumb|438x438px|Example of Convergence Rates of Multigrid Cycles in comparison to other smoothing operators.]]

And in particular, we find for the finest grid <math>N_1</math> that

:<math display="block">W_1 = W_2 + \rho K N_1</math>

Combining these two expressions (and using <math>N_{k}N_k = \rho^{k-1} N_1</math>) gives

:<math display="block">W_1 = K N_1 \sum_{p=0}^n \rho^p </math>

Using the [[geometric series]], we then find (for finite <math>n</math>)

:<math display="block">W_1 < K N_1 \frac{1}{1 - \rho}</math>

that is, a solution may be obtained in <math>O(N)</math> time. It should be mentioned that there is one exception to the <math>O(N)</math> i.e. W-cycle multigrid used on a 1D problem; it would result in <math>O(Nlog(N) \log N)</math> complexity. {{Citation needed|date=September 2021}}

==Multigrid preconditioning==