Jacobi Method

A discussion of the Jacobi method is presented in Chapter 8 of the text. Here we will merely outline some of the points that were made in class:

We are attempting to solve a system of the form ${\bf A} x = b$. For the Jacobi method, this reduces to iterating the following:

$$x_i^{k+1} = \frac{1}{a_{ii}}\left( b_i - \sum_{j\neq i} a_{ij} x_j^k \right)$$

where the subscript denotes the component of the vector, and the superscript denotes the iterate.

In class, we noted the following:

• To solve for the next iterate x_i^k+1, we need the i^th row of A, the entire vector x^k and the i^thentry of b (as shown in figure ).

  
  

    

  Figure: Decomposition of the system for the Jacobi Method

  
  
  

• This leads to a natural parallelization as shown in figure .

  
  

    

  Figure: Distribution of A and b for parallel Jacobi.

  
  
  

  Rows of A and entries of b are partitioned across processors. All processors need the entire vector x^k.

• To collect/distribute the newly formed x^k+1 vector, MPI_Allgather/MPI_Allgatherv should be used.

• A stopping criterion should be implemented. This should require the use of MPI_Allreduce.