# Multigrid

In mathematics, more specifically in numerical analysis, multigrid methods are a group of algorithms for solving differential equations using a hierarchy of discretizations. This approach has the advantage over other methods that it scales linearly with the number of discrete nodes used.

In order for the multigrid methods to be applicable, one needs to make several assumptions. Assume that one has a differential equation which can be solved approximately (with a given accuracy) on a grid [itex]i[itex] with a given grid point density [itex]N_i[itex]. Assume furthermore that a solution on any grid [itex]N_i[itex] may be obtained with a given effort [itex]W_i = \rho K N_i[itex] from a solution on a coarser grid [itex]i+1[itex] with grid point density [itex]N_{i+1} = \rho N_i[itex] (that is, [itex]K[itex] is not dependent on [itex]i[itex]).

Then, using the geometric series, we then find for the effort involved in finding the solution on the finest grid [itex]N_1[itex]

[itex]W_1 = W_2 + \rho K N_1[itex]
[itex]W_1 = W_3 + \rho^2 K N_1 + \rho K N_1[itex]
[itex]W_1 / (K N_1) + 1 = 1 + \sum_p \rho^p [itex]
[itex]W_1 / (K N_1) + 1 = 1 / (1 - \rho)[itex]
[itex]W_1 = (K N_1) (1 / (1 - \rho) - 1),[itex]

that is, a solution may be obtained in [itex]O(N)[itex] time.

• Art and Cultures
• Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
• Space and Astronomy