Multi-Grid Methods

Presentation Script — 15 Minutes Total

Parne Abhinav Reddy · Jalagam Karthikeya · Marskola Krishna
Department of Mathematics and Computing | IIIT Raichur

Karthikeya Abhinav Krishna

Slides 1–6 | ~5 min Slides 7–11 | ~6 min Slides 12–14 | ~4 min

🎤 Jalagam Karthikeya | Slides 1–6 (approx. 5 minutes)

⏱ 0:00 – 0:30 | Slide 1: Title

Slide 1: Multi-Grid Methods — Title Slide

Good morning / afternoon, everyone. My name is Karthikeya, and along with my teammates
Abhinav and Krishna, we will be presenting our work on Multi-Grid Methods — a powerful family
of algorithms for solving very large systems of linear equations that arise in real-world
simulations.
We will walk you through why classical methods fall short, how the multigrid idea elegantly
solves that problem, and then dive into both Geometric and Algebraic variants. Let us begin.

⏱ 0:30 – 1:00 | Slide 2: Outline

Slide 2: What We Will Cover

Here is a quick roadmap of what you will see today. The presentation is structured in three
logical blocks:
First, I will cover the motivation and core intuition — why we need multigrid, why classical
iterative solvers fail, and how the two-grid scheme and geometric multigrid address the problem.
That takes us through Slide 6.
Then Abhinav will take over and explain the key operators — prolongation, restriction, and
smoothers — and extend everything into Algebraic Multigrid, including how AMG handles the
challenge of convection-dominated problems.
Finally, Krishna will bring it all together with Physics-Aware AMG, cycling strategies, and our
summary.

⏱ 1:00 – 2:15 | Slide 3: The Problem

Slide 3: Why Do We Need Multigrid?

So why do we even need a special method like multigrid? The answer starts with PDEs —
Partial Differential Equations.
Real-world physical phenomena — heat conduction, fluid flow, structural stress — are all
governed by PDEs. To solve them numerically, we discretize the domain into a mesh: we
replace the continuous domain with a grid of tiny cells, and each cell gives us one equation. For
a three-dimensional engineering problem, this can mean anywhere from one million to one
billion unknowns.
Now, how do classical methods scale? Gaussian elimination costs O(n³) — completely
infeasible for n = 10⁶. Even iterative methods like Jacobi or Gauss-Seidel cost O(n²). Still far too
slow.
Multigrid, on the other hand, achieves O(n) — near-optimal, and the only approach practical at
this scale. That is the fundamental motivation.
💡 Tip: Point at the method comparison table on the slide as you say each complexity.

⏱ 2:15 – 3:15 | Slide 4: Classical Methods

Slide 4: Why Jacobi & Gauss-Seidel Are Slow

The key to understanding multigrid is understanding why Jacobi and Gauss-Seidel slow down.
Let us think about the error in our current solution.
Error components can be classified by their frequency. High-frequency error — also called
oscillatory or rough error — looks like a zigzag pattern, changing rapidly from point to point.
Jacobi and Gauss-Seidel are excellent at removing this: just five to ten iterations and it is
essentially gone.
But then there is low-frequency error — smooth error — which looks like a long, gentle wave
across the entire grid. And this is where classical methods fail. To reduce smooth error by a
constant factor, you need O(1/h²) iterations. For a fine grid, that could be a million iterations.
That is simply not acceptable.
Here is the crucial insight that motivates multigrid: smooth error on a fine grid looks oscillatory
on a coarser grid. And oscillatory error is exactly what iterative smoothers eliminate cheaply. So,
if we could move to a coarser grid, we could fix the smooth error there — quickly and cheaply.
💡 Tip: Use a hand gesture showing 'waves getting larger' when discussing smooth error on the
coarser grid.

⏱ 3:15 – 4:00 | Slide 5: The Multigrid Idea

Slide 5: The Multigrid Idea

And that is exactly what multigrid does. The idea is beautifully simple.
We maintain a hierarchy of grids — fine, medium, coarse — each with half the resolution of the
previous. On the fine grid with spacing h, we have 16 points. On the medium grid at 2h, we have
8. On the coarsest at 4h, just 4. Each level is cheaper to compute on.
The three-step process is: First, smooth on the fine grid to kill rough error fast. Second, take the
remaining smooth error — which looks rough on the coarser grid — restrict it down, and remove
it cheaply there. Third, bring that correction back up to the fine grid, add it in, and smooth again
to clean up any interpolation noise.
The total cost across all grid levels is O(n), because the coarser levels do exponentially less
work. This is the elegant mathematical core of the entire multigrid family.

⏱ 4:00 – 5:00 | Slide 6: Two-Grid Scheme

Slide 6: The 7-Step Correction Cycle

Let us make the multigrid idea concrete with the Two-Grid Scheme — the fundamental
algorithm from which everything else is derived.
Step 1: Pre-smooth. Run the smoother a few times on the fine grid to kill rough, oscillatory error.
Step 2: Compute the residual. The residual r = f minus A times u tells us exactly how wrong our
current solution is.
Step 3: Restrict. We use the restriction operator to send the residual down to the coarse grid.
This is a downsampling operation.
Step 4: Coarse-grid solve. On the coarse grid, we solve the error equation. Because there are
far fewer points, this is cheap — and the smooth error looks rough here, so smoothers handle it
quickly.
Step 5: Prolongate. We bring the coarse-grid correction back up to the fine grid using
interpolation — the prolongation operator.
Step 6: Correct. We add the coarse-grid correction to our fine-grid solution. This is where the
magic happens.
Step 7: Post-smooth. We run the smoother one more time to clean up any high-frequency noise
introduced by the interpolation step.
This seven-step cycle is the engine of all multigrid methods. I will now hand over to Abhinav,
who will explain the specific operators involved and then take us into Algebraic Multigrid.
💡 Tip: Pause here to let Abhinav come forward before the next slide.

🎤 Parne Abhinav Reddy | Slides 7–11 (approx. 6 minutes)

⏱ 5:00 – 5:45 | Slide 7: Geometric Multigrid

Slide 7: GMG — Using the Physical Mesh

Thank you, Karthikeya. I will now cover Geometric Multigrid, the key operators, and then
Algebraic Multigrid.
In Geometric Multigrid, or GMG, we exploit the fact that we know the shape of the physical
domain. We construct the grid hierarchy by hand — directly from the geometry.
The hierarchy is written as Ω_h ⊂ Ω_{2h} ⊂ Ω_{4h} ⊂ ... ⊂ Ω_{2^L h}. Each coarser level
doubles the mesh spacing h. In two dimensions, this reduces the number of grid points by a
factor of four per level. In three dimensions, by a factor of eight.
A key practical advantage: the total memory across all grid levels is only about 33% more than
the fine grid alone. This is because the geometric series 1 + 1/4 + 1/16 + ... converges to 4/3.
Think of it like zooming out on a photograph: each coarser level is a lower-resolution version of
the fine grid, capturing the overall shape with less detail. GMG works beautifully for regular
square or cubic domains. But for irregular unstructured meshes, building that hierarchy by hand
becomes very difficult — and that is where Algebraic Multigrid steps in.

⏱ 5:45 – 7:00 | Slide 8: Key Operators

Slide 8: Prolongation, Restriction & Smoothers

Before we go further, let us understand the three core building blocks used inside the multigrid
cycle.
Prolongation, also called interpolation, transfers information from the coarse grid up to the fine
grid. It copies coarse-grid values to matching fine-grid points. For points in between — the ones
that exist only on the fine grid — it computes values by bilinear interpolation: averaging nearby
coarse-grid neighbors. This is how we bring the coarse-grid correction back to the fine level.
Restriction is the reverse: it takes the fine-grid residual and condenses it down to the coarse
grid. The standard approach is full-weighting, where the central node gets weight one-half and
each of its four neighbors in 2D gets weight one-quarter. An important mathematical fact:
restriction is exactly the transpose of prolongation. This relationship preserves the variational
structure and is key to multigrid's theoretical guarantees.
Now, the smoothers. We have four main choices:
Weighted Jacobi updates all nodes simultaneously using old values. It is easy to parallelize. The
optimal damping weight is two-thirds for Poisson problems.
Gauss-Seidel uses freshly updated neighbor values immediately, giving roughly twice the
convergence rate of Jacobi. The trade-off is that it is harder to parallelize.
Red-Black Gauss-Seidel colors the grid like a chessboard and updates all red nodes in parallel,
then all black nodes. This achieves the same convergence as standard Gauss-Seidel while
being fully parallel.
ILU(0) — Incomplete LU factorization — is the strongest smoother here, very effective on tough
anisotropic problems. It computes approximate L and U factors and is used when other
smoothers struggle, though it is harder to parallelize.

⏱ 7:00 – 8:00 | Slide 9: Algebraic Multigrid

Slide 9: AMG — No Mesh Needed

Now we come to Algebraic Multigrid, or AMG — the method that generalizes multigrid beyond
structured meshes.
The key difference from GMG is that AMG requires no geometric information at all. It builds the
entire grid hierarchy purely from the entries of the matrix A.
Let us compare the two side by side. GMG needs explicit mesh geometry; AMG only needs the
matrix. GMG works beautifully on simple square or cube domains; AMG works for any problem
— including graph-structured problems and irregular unstructured meshes. In GMG, coarse
grids are built by hand; in AMG, they are built automatically from matrix entries. And where
GMG uses geometry to define inter-grid operators, AMG uses the matrix couplings.
The core concept in AMG is the strength of connection. We say that node j is strongly
connected to node i if the off-diagonal entry |a_ij| is large relative to all other entries in that row.
Strong connections play the role that physical proximity plays in GMG — they define which
nodes are 'neighbors' for the purpose of building the hierarchy.
💡 Tip: Emphasize: AMG is what makes multigrid applicable to real-world industrial problems.

⏱ 8:00 – 9:15 | Slide 10: AMG C/F Splitting

Slide 10: C/F Splitting — Building the Coarse Grid

The setup phase of AMG involves partitioning all unknowns into two sets: C-points and F-points.
C-points, or coarse-grid points, are kept on the coarse grid and become the coarse-grid
unknowns that will be solved directly. The rule for choosing C-points is that there should be
enough of them to accurately represent the smooth error.
F-points, or fine-grid-only points, are only on the fine grid. Their values will be interpolated from
nearby C-points. The rule for F-points is that every F-point must have at least one strongly
connected C-point neighbor — otherwise we cannot interpolate it accurately.
The standard algorithm for this is the Ruge-Stüben algorithm, which works in two passes. In
Pass 1: find the undecided node with the most strong connections — this node has the most
influence on others — and mark it as a C-point. Then mark all its strongly connected neighbors
as F-points. Repeat until every node is classified as either C or F.
In Pass 2: we check for a quality criterion. If two F-points are strongly connected to each other
but do not share a common C-point neighbor, then one of them must be promoted to a C-point.
This pass ensures that every F-point can be accurately interpolated from the C-grid.
Together, these two passes guarantee that the coarse grid can represent the smooth error well,
which is the theoretical requirement for multigrid convergence.

⏱ 9:15 – 11:00 | Slide 11: Péclet Number Challenge

Slide 11: The Péclet Number Challenge

Now we come to a critical real-world challenge: what happens when we apply AMG to
convection-diffusion problems?
The governing equation is: negative epsilon times the Laplacian of u, plus b dot the gradient of
u, equals f. Here epsilon is the diffusion coefficient, b is the convective velocity, and f is the
source term.
The Mesh Péclet Number Pe is defined as the convective velocity magnitude times the cell size
h, divided by twice epsilon. It is a dimensionless ratio that measures whether diffusion or
convection dominates.
When Pe is much less than one, diffusion dominates. The solution is smooth everywhere, the
matrix is symmetric and diagonally dominant, and standard AMG works perfectly.
When Pe is much greater than one, convection dominates. Sharp boundary layers form in the
solution — regions where the solution changes very rapidly over a very thin strip. The matrix
becomes non-symmetric because the upwind coupling creates one-directional dependencies.
And standard AMG fails badly.
There are four specific ways AMG breaks down at high Péclet number. First, the coarse points
are selected wrong, because upwind coupling creates one-directional connections that AMG's
symmetric strength criterion does not capture. Second, the matrix is no longer an M-matrix — it
has positive off-diagonal entries — and this breaks classical AMG theory. Third, the error is only
smooth along the flow direction, not across it, so the coarse grid needs to be aligned with the
flow. Fourth, the boundary layers are too sharp to represent on coarser grids, causing the
coarse-grid correction to be inaccurate.
I will now hand over to Krishna, who will present the solution to this challenge: Physics-Aware
AMG.
💡 Tip: Pause and hand over to Krishna clearly.

🎤 Marskola Krishna | Slides 12–14 (approx. 4 minutes)

⏱ 11:00 – 12:30 | Slide 12: Physics-Aware AMG

Slide 12: PA-AMG — Fixing AMG for Convection Problems

Thank you, Abhinav. I will now cover the solution to the high-Péclet-number challenge, cycling
strategies, and our final summary.
Physics-Aware AMG, or PA-AMG, addresses each of the four failure modes Abhinav identified
— one fix per problem.
Problem one was wrong coarse-point selection due to one-directional upwind coupling. The fix
is a directional strength criterion: instead of measuring strength of connection symmetrically in
all directions, we define it specifically along the flow direction b. This means the C-points and F-
points are selected in a way that respects the physics of the flow.
Problem two was the non-symmetric matrix caused by convection. The fix is Streamline Gauss-
Seidel: instead of sweeping through nodes in a standard ordering, we sweep in the direction of
flow. This ensures upstream information propagates correctly before downstream nodes are
updated — exactly matching the physics.
Problem three was that smooth error is aligned with the flow streamlines, not isotropic. The fix is
adaptive prolongation: interpolation weights are adapted so that corrections are carried along
the flow streamlines rather than spread uniformly in all directions.
Problem four was sharp boundary layers that coarser grids cannot represent. The fix is layer-
aware coarsening: we detect regions where the solution changes rapidly — the boundary layers
— and prevent coarsening across them. The grid spacing is kept fine in those regions, even on
coarser levels.
Together, these four modifications restore optimal convergence for convection-dominated flows.
PA-AMG is an example of how physical insight can be embedded directly into the numerical
algorithm.

⏱ 12:30 – 13:45 | Slide 13: Cycling Strategies

Slide 13: V-Cycle, W-Cycle & Full Multigrid

Now let us talk about how the multigrid levels are actually traversed. There are three main
cycling strategies.
The V-Cycle is the simplest and most commonly used. Starting from the fine grid, we go down
through each level — smoothing and restricting — and then come back up — prolongating and
smoothing — visiting each level exactly once. The path traced looks like the letter V. The cost is
O(n), and this is the default choice for most problems.
The W-Cycle provides a more accurate coarse-grid correction by solving the coarse-grid
problem twice per descent. Think of it as a V-cycle nested inside another V-cycle — the path
looks like the letter W. The cost is O(n log n), and it is preferred when the V-cycle converges too
slowly or when the problem has significant non-symmetry.
Full Multigrid, or FMG, is the most powerful strategy — and also O(n) like the V-cycle, making it
theoretically optimal. The idea is different: instead of starting from a random initial guess on the
fine grid, we begin by solving on the coarsest grid, then use that coarse solution as a high-
quality initial guess on the next finer level, and so on. Each level gets one V-cycle. By the time
we reach the fine grid, we already have an excellent starting point, and typically just one V-cycle
suffices to reach discretization-level accuracy. FMG is the best choice when it can be applied.
💡 Tip: Draw the V, W, and FMG shapes in the air as you describe each one.
⏱ 13:45 – 15:00 | Slide 14: Summary

Slide 14: Summary & Key Takeaways

Let us close with the key takeaways from today's presentation.
First: why multigrid? Classical smoothers kill rough error fast but cannot touch smooth error.
Multigrid solves this by using a hierarchy of grids — each level fixes what the others cannot.
Second: GMG versus AMG. Geometric Multigrid uses known mesh geometry and is ideal for
structured domains. Algebraic Multigrid builds the hierarchy from the matrix alone, making it
universally applicable — even for graph problems and unstructured meshes.
Third: the two-grid core cycle — Pre-smooth, Restrict, Coarse solve, Prolongate, Correct, Post-
smooth. This seven-step pattern is the engine behind every multigrid method.
Fourth: the Péclet challenge. At high Péclet numbers, convection dominates, sharp layers form,
and standard AMG fails. Physics-Aware AMG fixes this by incorporating flow direction into every
algorithmic choice.
Fifth: Full Multigrid is optimal. By starting from the coarsest grid and working up, FMG achieves
discretization-level accuracy in O(n) work — theoretically the best possible algorithm.
Sixth: open challenges. Active research areas include extending AMG theory to non-symmetric
systems, accelerating multigrid on GPUs, and using Graph Neural Networks to speed up the
computationally expensive setup phase.
Thank you very much for your attention. We are happy to take any questions.

Quick Reference: Timing Summary

Speaker Slides Time Duration
Karthikeya 1–6: Title, Outline, Problem, 0:00–5:00 ~5 min
Classical, Multigrid Idea, Two-
Grid
Abhinav 7–11: GMG, Operators, AMG, 5:00–11:00 ~6 min
C/F Split, Péclet
Krishna 12–14: PA-AMG, Cycling, 11:00–15:00 ~4 min
Summary