Caching in with Multigrid Algorithms: Problems in Two Dimensions

Craig C. Douglas
IBM T. J. Watson Research Center
Yorktown Heights, NY, USA and
Computer Science Department
Yale University
New Haven, CT, USA


Multigrid methods combine a number of standard sparse matrix techniques. Usual implementations separate the individual components (e.g., an iterative methods, residual computation, and interpolation between grids) into nicely structured routines. However, many computers today employ quite sophisticated and potentially large caches whose correct use are instrumental in gaining much of the peak performance of the processors.

We investigate when it makes sense to combine several of the multigrid components into one, using block oriented algorithms. We determine how large (or small) the blocks must be in order for the data in the block to just fit into the processor's primary cache. By re-using the data in cache several times, a potential savings in run time can be predicted. This is analyzed for a set of examples.

Key words: multigrid, cache, sparse matrix, iterative methods, domain decomposition.

Contributed May 31, 1995.