Gauss-Seidel is an iterative computation used for solving a set of simultaneous linear equations, $A\vec{u}=\vec{f}$. If the matrix $A$ uses a sparse matrix representation, storing only nonzeros, then the data dependences in the computation arise from $A$'s nonzero structure. We use this structure to schedule the computation at runtime using a technique called full sparse tiling. The sparse tiled computation exhibits better data locality and therefore improved performance. This paper gives a complete proof that a serial schedule for full sparse tiled Gauss-Seidel generates results equivalent to those that a typical Gauss-Seidel computation produces. We also provide implementation and correctness details for full sparse tiling with reduced worst-case complexity.

Pre-2018 CSE ID: CS2003-0741

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.

Pre-2018 CSE ID: CS2001-0690