Proof of Correctness for Sparse Tiling of Gauss-Seidel

Michelle Mills Strout, Larry Carter and Jeanne Ferrante
CS2001-0690
December 4, 2001

Gauss-Seidel is an iterative computation used for solving sets of simulataneous linear equations, $Au=f$. When these unknowns are associated with nodes in an irregular mesh, then the Gauss-Seidel computation structure is related to the mesh structure. We use this structure to subdivide the computation at runtime using a technique called {\em sparse tiling}. The rescheduled computation exhibits better data locality and therefore improved performance. This paper gives a complete proof that a serial schedule based on sparse tiling generates results equivalent to those that a standard Gauss-Seidel computation produces.

How to view this document

• Display an overview of the document in one of the following formats.

• Display a selected page in one of the following formats (document has 23 pages).
• Display the whole document in one of the following formats.