Department of Applied Mathematics and Theoretical Physics

Numerical Analysis Course

Multigrid methods

One of the difficulties when talking about relative speeds of numerical methods is trying to get a hand on the speed up for various methods. This demonstration of the multigrid method shows how much better than Jacobi and Gauss-Seidel are for solving linear systems.


The theory

The general idea of multigrid is that convergence for Gauss-Seidel depends on the frequency of the solution relative to the grid size. By applying Gauss-Seidel on a variety of different grid sizes this effect can be used to great effect. The most basic form of multigrid inolves solving the Poisson equation by finite differences on a grid. This reduces to a matrix equation $A \mathbf{x} = \mathbf{v}$. In order to solve this equation we apply Gauss-Seidel a few times on a full size grid, before restricting the problem to a smaller grid and repeating the process. Once we've solve reduce the grid sufficiently many times we can solve the linear system and prolongate the solution to larger grid sizes.


The GUI solves the 1D Poisson equation $u'' = f$ on a grid size of $2048$ with zero boundary conditions. We've picked the function $f = -x + 100 \cos (24 \pi x) + 50000 \cos( 1000 \pi x)$ to ensure a range of frequencies.


You can alter the method used to solve this system: relaxed Jacobi, Gauss-Seidel or multigrid and can see just how much quicker multigrid is than these two other methods.


The code for this project is based on Professor Demanet's code found on his course page


All files as .zip archive: