Conventional implementations of iterative numerical algorithms, especially multigrid methods, merely reach a disappointing small percentage of the theoretically available CPU performance when applied to representative large problems. One of the most important reasons for this phenomenon is that the current DRAM technology is not able to provide the data fast enougth to keep the CPU busy. Although the fundamentals of cache optimizations are quite simple, current compilers are not able to optimize even simple iterative methods.

We analyse the memory and cache behavior of iterative methods with extensive profiling and describe program transformation techniques to improve the cache performance of two and three dimensional multigrid algorithms. Examples are provided for both structured and unstructured grid problems.