project 3

Multigrid methods

The purpose of this project to write a multigrid solver and multilevel preconditioners (including HB and BPX) for solving the Poisson equation with homogeneous Dirichlet boundary condition discretized by piecewise linear finite elements on a uniform grid on unit square.

The project will be divided into several steps.

Step 1: Smoothing property

• load the mesh 1089mesh.mat in MATLAB
• obtain the algebraic equation for solving the following Poisson equation on the unit square (0,1)^2 using linear finite element methods on that mesh
• Use Gauss-Seidal method (starting with zero initial guess) to solve the algebraic equation to the tolerence 1e-6.
• Plot the convergence history and the error in the first 5 steps (similar to Figure 11.2 and 11.3)
• boundary condition: leave the boundary nodes in the big vector and use the following code to identify the index of boundary nodes

  bdNode = unique(Dirichlet);
  freeNode = setdiff(1:N,bdNode);
  

  and access the matrix/vector corresponding to the interior nodes in this way

  A(freeNode, freeNode), u(freeNode), f(freeNode)
  

Step 2: Prolongation and restriction between two levels

In this step, we code a two level method on the following two meshes.

the data for the fine mesh can be downloaded here 16mesh.mat

• design the data structure hb
• construct the prolongation and restriction matrix
• code the two grid SSC to solve the Poisson equation in Step 1 (see Prof. Xu's notes on the description of this two grid method)
• boundary conditions: be careful on the boundary nodes. Restrict the operation on the freenode only

Step 3: V-cycle multigrid

• Use decomposition.m to decompose the fine grid in 1089mesh.dat to get hb
• code V-cycle multigrid using Gauss-Seidal in pre-smoothing and post-smoothing
• plot the convergence history

Step 4: Multigrid as Preconditioner

• Use multigrid operator B as the preconditioner in the PCG method
• Compare the convergence rate with MG alone