University of Tripoli

Mechanical & Industrial Engineering Department

www.me.uot.edu.ly

ME626 Advance Numerical Analysis

Lecture 9:
Multi-grid Methods
Instructor: Samah Alghoul
Outlines: Multi-grid Methods

➢Geometric Multigrid (GMG) Method

➢Two Grid Idea

➢MG Scheduling

➢Algebraic Multigrid (AMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 2

Introduction

› Based on previous findings, it is fair to conclude that any method

that specifically targets and reduces the large wavelength
components of the error will exhibit faster rates of convergence.
› Multigrid methods are designed to do just that.
› One of the important findings is that the largest eigenvalue is
lowered as the mesh is coarsened.
› This implies that a coarse mesh will result in faster convergence, as
evident in previous lectures.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 3

Introduction

› The multigrid method capitalizes upon the idea of selectively

smoothing (reducing) large wavelength errors on a coarse mesh
rather than on the original fine mesh because it is more effectively
done.
› The idea led to the so-called Geometric Multigrid (GMG) method,
in which multiple meshes are employed to reduce the errors rapidly.
› In more recent times, with an increase in geometric complexity of
scientific and engineering computations of PDEs, and the increase
in the use of unstructured grids, it has become increasingly difficult
to use multiple grids.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 4

Introduction

› This has led to the development of the so-called algebraic multigrid

(AMG) method, in which the general multigrid idea is applied at the
linear algebraic equation level without resorting to multiple grids.
› This is done by developing equivalent coarse-grid approximations
from the discrete fine grid equations.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 5

Geometric Multigrid (GMG)
Method
Geometric Multigrid (GMG) Method

› Consider only two grids – “coarse” and “fine” – are used.

› The two-grid algorithm serves as the core framework for a general
multigrid algorithm.
› The accuracy of final solution must be that of fine mesh.
› The coarse mesh can only be used to accelerate the convergence;
not to compute the final solution.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 7

Geometric Multigrid (GMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 8

Geometric Multigrid (GMG) Method

Step 1: Generating and Storing meshes and their relationships.

› Every coarse-grid node, defined by the pair (I,J), has a corresponding fine-grid
node sitting atop it, and is defined by the pair (i,j).

› If the total number of fine-grid and coarse-grid nodes in the i (or j) direction are
denoted by NF (or MF) and NC (or MC), respectively,

› It follows that the grid spacings for the coarse and fine grids are given by

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 9

Geometric Multigrid (GMG) Method

› The corresponding nodal equations on the coarse and fine grids are written as

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 10

Geometric Multigrid (GMG) Method

Step 2: Set initial guess

› The next step in the algorithm is to initialize the dependent variable on the fine
grid.
› Since the fine-grid solution is what we are ultimately interested in, it is
sufficient to initialize the solution at the fine-grid nodes.
› Let this solution be denoted by φi,jF(0).
› If Dirichlet boundary conditions are used, the initial guess at the boundary
nodes should be set equal to the prescribed boundary value.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 11

Geometric Multigrid (GMG) Method

Step 3: Smoothing on fine grid

› Next, the algebraic equations on the fine grid are solved using a solver of
choice, but only to partial convergence.
› The solver to be used is also known as the smoother, and the operation of
solving the fine-grid equations to partial convergence is known as smoothing.
› The Gauss–Seidel method is a popular choice as the smoother for multigrid
algorithms, primarily because
– of its extremely low workload per iteration,
– its ease of implementation,
– it can be used for both structured and unstructured mesh topologies.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 12

Geometric Multigrid (GMG) Method

› Generally, iterations are continued until the R2F decreases by a factor of about
two.
› Often, calculation and monitoring of the scaled residual, as would be required
if the residual were to be decreased by a factor two, is completely bypassed,
and one or two sweeps of Gauss–Seidel is executed instead.
› This makes the implementation even easier.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 13

Geometric Multigrid (GMG) Method

› At this point in the algorithm, the solution on the fine grid, φi,jF contains errors
due to partial convergence.
› This error (equal to the difference between the exact numerical solution and the
solution at the current iteration) has several different wavelength components.
› The components that have large wavelengths are the most difficult to damp out
(or have their amplitudes reduced).
› Therefore, instead of continuing with regular smoothing (Gauss–Seidel
iterations on the fine grid, for example), which would not specifically target the
large wavelength components, we transfer this error to a coarse grid and then
smooth it on the coarse grid so that they are reduced rapidly.
› In preparation for these actions, the following step is executed next.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 14

Geometric Multigrid (GMG) Method

Step 4: Computation of residual on fine grid

› The residual and L2Norm are computed on the fine grid using

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 15

Geometric Multigrid (GMG) Method

Step 5: Transfer of fine-grid residual to coarse grid (restriction)

› The residual computed on the fine grid in Step 4 is next transferred to the
coarse grid, this process is known as restriction.
› The loops used to perform this transfer should run over the indices of the
coarse grid

› The residual transferred from the fine to the coarse grid will be denoted by
[R]C←F.
› For a more complex grid structure, the coarse- and fine-grid nodes may not
always overlap, therefore, interpolation will be necessary to execute the
transfer process.
ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 16
Geometric Multigrid (GMG) Method

Step 6: Smoothing on coarse grid

› The transferred residuals are next smoothed on the coarse grid with the specific
intent to damp out the large wavelength components of the error rapidly.
› This operation entails solution of the governing equation (correction form) to
partial convergence,

[A]C[φ′]C = [R]C←F
– where [A]C is the coefficient matrix computed on the coarse mesh
– [φ′]C is the predicted correction on the coarse mesh.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 17

Geometric Multigrid (GMG) Method

› As in Step 3, a solver with a low computational workload and one that is easy
to implement must be used.
› Generally, tighter tolerance or more sweeps (typically two or three, as opposed
to one) is needed in this step than in Step 3 to obtain an accurate enough
prediction of the correction.
› The Gauss–Seidel method is also a commonly used method for this step.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 18

Geometric Multigrid (GMG) Method

Step 7: Transfer of coarse-grid correction to fine grid (prolongation)

› Correction obtained on coarse grid, [φ′]C , is next transferred to the fine grid.
› The transfer of [φ′]C can be classified into three categories.
▪ 1. Fine-grid nodes that have coarse grid-nodes sitting atop them, the
correction is transferred directly.
1
▪ 2. fine-grid nodes placed along coarse-grid lines

▪ 3. fine-grid nodes offset from coarse-grid lines 2 3

> The transferred correction is denoted by [φ′]F ←C .

ME 626 ADVANCED NUMERICAL METHODS 7/27/2019 19

Geometric Multigrid (GMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 20

Geometric Multigrid (GMG) Method

Step 8: Update of fine-grid solution

› The fine-grid solution, obtained in Step 3, is next updated by adding to it the
correction obtained in Step 7:

[φ]F = [φ]F + [φ′]F←C

› At this juncture, one complete cycle of the multigrid (two-grid) algorithm has
been completed.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 21

Geometric Multigrid (GMG) Method

Step 9: Check for convergence

› Convergence is checked by monitoring the residual computed at Step 4,

R2F < εtol ?

› Although the residual computed in Step 4 is lagging behind by one iteration, it
is preferable to use it to monitor convergence to avoid computation of the
residual twice within the same iteration.
› If the convergence criterion has not been satisfied, Steps 3–9 must be repeated.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 22

Geometric Multigrid (GMG) Method
› Step 1: Generating and storing meshes and their relationships.
› Step 2: Set initial guess
› Step 3: Smoothing on fine grid
› Step 4: Computation of residual on fine grid
› Step 5: Transfer of fine-grid residual to coarse grid (restriction)
› Step 6: Smoothing on coarse grid
› Step 7: Transfer of coarse-grid correction to fine grid (prolongation)
› Step 8: Update of fine-grid solution
› Step 9: Check for convergence
ME 626 ADVANCED NUMERICAL METHODS 7/27/2019 23
Geometric Multigrid (GMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 24

Geometric Multigrid (GMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 25

Geometric Multigrid (GMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/27/2019 26

Geometric Multigrid (GMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 27

Geometric Multigrid (GMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 28

Geometric Multigrid (GMG) Method – MG scheduling

› The sequence of smoothing–restriction–correction–prolongation

steps that are followed is referred to as multigrid scheduling.
› While a large variety of multigrid scheduling algorithms are
available, the three most commonly used ones are
▪ V-cycle,
▪ W-cycle,
▪ Full multigrid (FMG) cycle.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 29

Geometric Multigrid (GMG) Method – MG scheduling

V-cycle multigrid algorithm

› The V-cycle multigrid algorithm commences with iterative solution of the
linear system to partial convergence on the finest grid (Grid 1).
› The residual is then transferred to the next finest grid (Grid 2) and smoothed
using an iterative solver.

“S” refers to the smoothing operation

“C” refers to the error correction operation
“U” refers to the final solution update

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 30

Geometric Multigrid (GMG) Method – MG scheduling
“S” refers to the smoothing operation
V-cycle multigrid algorithm “C” refers to the error correction operation
“U” refers to the final solution update

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 31

MG scheduling

ME 626 ADVANCED NUMERICAL METHODS 7/27/2019 32

Geometric Multigrid (GMG) Method – MG scheduling

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 33

Geometric Multigrid (GMG) Method – MG scheduling

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 34

Geometric Multigrid (GMG) Method – MG scheduling

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 35

Algebraic Multigrid
(AMG) Method
Algebraic Multigrid (AMG) Method

› While the GMG method is not a plugin-type method.

› The formulation and execution of the GMG method is inherently
tied to a grid, thereby significantly hampering its generality as a
linear system solver.
› For example, it cannot be used to solve a general system of linear
algebraic equations that did not arise out of discretization of a PDE
on a grid.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 37

Algebraic Multigrid (AMG) Method

› The AMG method was designed with the goal to

▪ capitalize upon the powerful multigrid idea of targeted reduction
of large-wavelength errors
▪ Removing any connection of the method to an underlying grid so
that the method can be used as a plugin-type solver.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 38

Algebraic Multigrid (AMG) Method

› The development of the AMG method was prompted by the

increasing popularity of unstructured meshes, in which generating a
large number of interconnected grid levels is all but impossible.
› The Gauss–Seidel method, which is the most commonly used
smoother in multigrid methods, can be used to solve any linear
system, and does not require any geometric information if the
matrix coefficients are known.
› Thus, it can be used equally effectively as a smoother in the context
of the AMG method, and is, in fact, used as the default smoother in
AMG methods.

ME 626 ADVANCED NUMERICAL METHODS 7/27/2019 39

Algebraic Multigrid (AMG) Method

› Computation of the matrix coefficients requires coarse- and fine-grid

information.
› In AMG, the coarse-grid equivalent equations are constructed from the fine-
grid equations at the algebraic equation level by combining fine-grid equations
in some fashion – a process known as agglomeration*.
› The exact algorithm used to combine the fine-grid equations to form equivalent
coarse grid equations results in variations of the AMG method.
› Another aspect that differs between various AMG methods is the interpolation
scheme used in the restriction and prolongation steps.
› Since there is no grid any more, the interpolation functions between two
equivalent grid levels must be constructed without resorting to a grid.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 40

Algebraic Multigrid (AMG) Method

› Let us consider the following set of algebraic equations arising out of finite
difference discretization of a 2D PDE on a structured mesh:
F = finest grid

› Equation may also be rewritten for the surrounding nodes, as follows:

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 41

Algebraic Multigrid (AMG) Method

› In order to construct a coarse-grid equivalent equation, fine-grid equation may

be agglomerated (added) with any of the four equations for the surrounding
nodes*.
› When two equations are agglomerated, the physical interpretation is that two
nodes have been agglomerated.
› If the two nodes happen to have the same value of φ, this makes logical sense.
› If we consider the set of nodes O, E, W, N, and S, the two nodes that will have
the closest value of φ are the two that have the largest link coefficients
connecting any two given pairs.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 42

Algebraic Multigrid (AMG) Method

› Having large link coefficients between a pair of nodes is tantamount to a strong

information exchange (or transport) between the pair.
› For example, if we are solving the heat conduction equation

› on a nonuniform structured mesh, the link coefficients will be proportional to

κ/δ2 where k is the thermal conductivity, and δ is the distance between any two
nodes.
› Thus, any pair of nodes that has the largest value of κ/δ2 is the best candidate
for agglomeration.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 43

Algebraic Multigrid (AMG) Method

› In the case of Poisson equation on a uniform mesh, since all four link
coefficients have the same value, all four nodes (E, W, N, and S) are equally
good candidates for agglomeration with O.
› Let us assume that we agglomerate O with E.

› Assuming that , where j is the index of the newly formed

coarse-grid node ( j ∈ C ),

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 44

Algebraic Multigrid (AMG) Method

› Further, if we assume that none of the other fine-grid nodal equations are
combined, the fine-grid index, k, can be replaced by the coarse-grid index, j,
resulting in

› Quantity within brackets premultiplying φCj is the new diagonal of the “coarse
node” that was formed by agglomerating the governing nodal equations for k
and k+ 1.
› Then, general relations for the agglomeration process:

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 45

Algebraic Multigrid (AMG) Method

› First equation states the diagonal element of the new “coarse” level equation is
the sum of the diagonal elements of the old “fine” level equations and the sum
of the link coefficients that connected the two agglomerated equations or nodes
› Second equation states that the right-hand side of the new “coarse” equation is
the sum of the right-hand sides of the two agglomerated fine equations.
› The preceding two rules, are universal no matter how many equations (nodes)
are agglomerated. All of the other link coefficients remain unchanged in this
case because no other equations were agglomerated.
› It should be emphasized that the two equations were derived without resorting
to any geometric information. Only the link coefficients were made use of.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 46

Algebraic Multigrid (AMG) Method

› If other equations are now agglomerated in addition, the same procedure and
rules, must be followed.
› This makes the process of agglomeration inherently sequential, and the
computational algorithm must obey this protocol.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 47

Algebraic Multigrid (AMG) Method

› Although the “coarse” equation was derived without resorting to geometric

information, the agglomeration process does have geometric implications as
illustrated in the Fig.
› The agglomeration process has the potential to destroy the structured property
of the original fine mesh.
› If Gauss–Seidel is used as the smoother, the fact that the coarse equations
correspond to a virtual unstructured mesh in physical space has no downside,
since the method is a point-wise iterative method.
› This is one of the main reasons why Gauss–Seidel is the preferred smoother in
AMG methods.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 48

Algebraic Multigrid (AMG) Method

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 49

Algebraic Multigrid (AMG) Method

› The construction of coarse-grid equivalent equations from the fine-grid

equations is one important step in the development of the AMG method.
› Another important step is the development of interpolation functions that will
allow transfer of information between the fine and coarse levels, as required in
the restriction and prolongation steps.
› Since the coarse level is now only virtual, geometry-based interpolation can no
longer be used, and a different approach must be resorted to.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 50

Algebraic Multigrid (AMG) Method
› the same procedure is followed and applied to the correction form of the equations,
rather than to the original equations, the following equation would result:

› This represents the coarse-grid correction equation that would have to be solved (using
Gauss–Seidel) right after the restriction step to obtain the coarse grid correction.
› It is worth noting that the right-hand side of this equation contains the residuals of two
fine-grid nodes.
› In essence, rather than compute the residuals on the fine mesh and then transfer it
explicitly to the coarse mesh via geometric interpolation, in this case, the coarse-grid
correction equations have been derived directly since geometric interpolation can no
longer be employed.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 51

Algebraic Multigrid (AMG) Method

› Once the coarse-grid correction, φ′Cj has been computed, it has to be passed
back to the fine grid (prolongation) so that the fine-grid solution can be
updated.
› Since the assumption was made in the first place
to derive the coarse-grid equation from the fine-grid equations, the
prolongation step essentially involves transferring the same correction to both
(or more) the agglomerated nodes (or equations).

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 52

Algebraic Multigrid (AMG) Method

› The preceding discussion provides a high-level outline of the main steps in the
AMG method.
› There are many variations of the method – each differing in the way the coarse-
grid correction equations are constructed, as well as the way the coarse grid
correction is transferred back to the fine grid. For a more comprehensive
discussion of the AMG method, the reader is referred to journal articles and
advanced texts [5–7] on this subject.

ME 626 ADVANCED NUMERICAL METHODS 7/26/2019 53

54