Problem

For this homework, we are to solve Laplace's equation using SOR in an HPF implementation. SOR is basically Gauss-Seidel with a twist. To implement Gauss-Seidel in parallel, I employ the Even-Odd, or ``checkerboard'' algorithm. This involves splitting the 2-d discrete grid into two classes of points, determined by the common 4-point stencil used in finite differencing the operator. First, the ``even points'' are updated, then the ``odd points'' are updated, using the values obtained from the even-point updates (thus, a Gauss-Seidel type implementation). The code for the updates is thus:

!  Calculate Gauss-Seidel update for even points

      Forall(i=2:nx-2:2,j=2:ny-2:2) grid(i,j) =
     c   (grid(i+1,j) + grid(i-1,j) + grid(i,j+1) + grid(i,j-1))/4.0
      Forall(i=3:nx-1:2,j=3:ny-1:2) grid(i,j) =
     c   (grid(i+1,j) + grid(i-1,j) + grid(i,j+1) + grid(i,j-1))/4.0

!  Calculate Gauss-Seidel update for odd points

      Forall(i=3:nx-1:2,j=2:ny-2:2) grid(i,j) =
     c   (grid(i+1,j) + grid(i-1,j) + grid(i,j+1) + grid(i,j-1))/4.0
      Forall(i=2:nx-2:2,j=3:ny-1:2) grid(i,j) =
     c   (grid(i+1,j) + grid(i-1,j) + grid(i,j+1) + grid(i,j-1))/4.0

The actual SOR update is a linear combination of the new, Gauss-Seidel update, and the previous values:

where is the overrelaxation parameter. Spectral analysis shows that convergence only occurs for . Note that is just the Even-Odd Gauss-Seidel method.

The convergence criteria that I imposed for the relaxation method is that the maximum absolute value between the k and the k+1 iteration must be below some specified tolerance. In these runs, I set that tolerance to be 1.0d-06.

The grid extent used here is 100 x 100. The boundary values are given by the analytic function used in homework 4, namely,