Polynomial Acceleration of Optimised Multi-grid Smoothers; Basic Theory
Victor L. Eijkhout · 2002
Introduction It is possible to implement multi-grid smoothers such as the Gauss-Seidel and SOR method in such a way that there is considerable cache-reuse [2]. The resulting code can have a performance several times higher than that of a naive implementation. The crux to this optimisation is the out-of-order execution of several iterations at one time: the part of the residual in cache is subjected to several smoothing steps before the same iterations are applied to another part of the vector. Such a reordering of the operations does not change the semantics of the floating point numbers produced in any way. While from a numerical point of view one might want to accelerate the smoother by a polynomial method such as CG or GMRES, in practice this cache-aware performance optimisation precludes such a numerical optimisation, since the inner products make out-of-order iterating impossible. However, it is possible to store several iterations worth of the Stationary Iteration (SI) vectors,