The development of sparse linear solvers for high performance computing is largely concerned with parallelism, rapid convergence, and low data access cost.  We propose efficient variations on the little-known Southwell iterative method, which may be used as a preconditioner or multigrid smoother.  The Southwell iterative method is similar to the Gauss-Seidel method, but instead of relaxing rows of the system of equations in a specific order, at each step we relax the row with the largest residual.  We propose a parallel version of this method and a distributed version that can be used efficiently on distributed memory computers.  Asynchronous operation of these methods is also envisaged.  A surprising result is that the new parallel Southwell method can reach a desired accuracy in fewer parallel steps than the Jacobi method while also performing fewer computations and communications per parallel step.

This is joint work with Jordi Wolfson-Pou and Fan Zhou.