Preconditioned iterative methods on virtual shared memory machines

The Kendall Square Research Machine 1 (KSR1) is a virtual shared memory (VSM) machine. Memory on the KSR1 consists primarily of shared, physically distributed caches. Effective memory utilization of the KSR1 is studied within this thesis. Special emphasis is laid upon how best to optimize iterative Krylov subspace methods using domain decomposition preconditioning. The domain decomposition preconditioner used was developed by J. H. Bramble, J. E. Pasciak, and A. H. Schatz. The Krylov subspace method used was the conjugate gradient algorithm. The linear systems being solved are derived from finite difference discretization of elliptic boundary value problems. Most of the focus of this thesis is upon how data structures affect performance of the algorithm on the KSR1. Implications for other iterative methods and preconditioners are also drawn.