COMP 230 · Multigrid Methods in Fortran

Led by Molerian Matrix Computation Simulacrum

About this course

Multigrid techniques are used in most commercial computational fluid dynamics codes. They accelerate convergence of basic iterative methods by using multiple grid levels — turning thousands of iterations into a dozen.

This short course applies multigrid to one- and two-dimensional elliptic problems in Fortran 90. You will implement Jacobi and Gauss-Seidel, understand why they stall, learn the multigrid insight that fixes them, and work through complete 1D and 2D Fortran codes.

Taught by Cleve Moler (numerical linear algebra) with William Kahan (convergence analysis) and John Backus (the Fortran code). Prerequisite: COMP 210 or equivalent. Background in numerical methods for linear systems assumed.

1. Module 1

   Iterative Methods and Multigrid Theory

   Led by Molerian Matrix Computation Simulacrum, with Kahanian Numerical Precision Simulacrum (guest)

   The question

   Jacobi and Gauss-Seidel kill high-frequency error fast but low-frequency error barely at all. What if you could make low-frequency error look high-frequency? That is the multigrid insight.

   Outcome

   The student can implement basic iterative methods, explain the multigrid insight, and describe V-cycle and W-cycle structures with their parameter choices. (Analytical)

   Sub-units

   1. ○ 1.1 Jacobi, Gauss-Seidel and Why They Stall Open this unit → ✓ ↻
   2. ○ 1.2 The Multigrid Idea Open this unit → ✓ ↻
   Begin the course → Print certificate of completion
2. Module 2

   The One-Dimensional Code

   Led by Molerian Matrix Computation Simulacrum, with John Backus Simulacrum (guest)

   The question

   The 1D multigrid code is short enough to understand completely. Every subroutine implements a mathematical operation. Can you trace the V-cycle through the code?

   Outcome

   The student can read, compile, run and modify a 1D multigrid Fortran code and has measured the convergence acceleration over single-grid methods. (Practical)

   Sub-units

   1. ○ 2.1 Subroutines: Smoothing, Restriction, Prolongation Open this unit → ✓ ↻
   2. ○ 2.2 Main Program and Experimentation Open this unit → ✓ ↻
   Open this module → Print certificate of completion
3. Module 3

   The Two-Dimensional Code

   Led by Molerian Matrix Computation Simulacrum

   The question

   Everything extends from 1D to 2D. The V-cycle is the same. The data structures change. And the payoff is even larger. Does the iteration count stay constant as you refine the grid?

   Outcome

   The student can work with a 2D multigrid code, verify grid-independent convergence, and articulate why multigrid is essential for large-scale scientific computation. (Project)

   Sub-units

   1. ○ 3.1 Two-Dimensional Extension Open this unit → ✓ ↻
   2. ○ 3.2 Running the 2D Code and Next Steps Open this unit → ✓ ↻
   Open this module → Print certificate of completion