Solving linear equations:

next up previous
Next: What you need Up: Simulating air flow Previous: Setting up the

Solving linear equations:

We now consider how to solve a linear system of the form for a sparse matrix . There are two classes of methods for solving linear systems: direct and iterative methods. Gaussian elimination is a direct method, but in this assignment we are going to use an iterative method. This is because iterative methods work well with sparse matrices and are easy to parallelize. The basic idea of an iterative method is that we repeat a set of steps and each step generates a better approximation of the final answer.

The particular iterative technique we want you to use in the assignment is called Jacobi iteration. The basic idea is that we can first guess at a solution for the values (the in our application). We can then determine how bad the guess is by calculating and seeing how far from 0 it is at each point. This difference is called the residual. The idea of the iterative technique is that we use this residual to improve our next guess of . In particular we use the iteration:

We keep repeating this step deriving new s until our error is small.

To make this work well we first need to adjust each row of the matrix so that the diagonal is . We can do this by multiplying each row and value by .

Guy Blelloch
Thu Jun 15 17:00:37 EDT 1995