Cache-oblivious scientific computing.

摘要

Scientific computing is the field of constructing mathematical models from science and engineering problems and providing numerical solution techniques. The cache-oblivious paradigm is a novel technique for designing algorithms and analyzing algorithm efficiencies. One advantage of cache-oblivious analysis over the traditional RAM (Random Access Model) lies in the consideration of hierarchical structures of modern computers. In this dissertation, we develop new algorithms and data layouts for scientific computing with better cache performances. We construct cache-oblivious iterative linear solvers, cache-oblivious mesh generation algorithms, and cache-oblivious particle simulation algorithms. To our knowledge, our work is the first attempt to adapt the cache-oblivious paradigm to scientific computing.We describe our cache-oblivious mesh layout algorithms and cache-oblivious linear solver. We present a new algorithm for generating decomposition trees. We then show that our mesh layout algorithms---which run in near optimal time and nearest optimal memory transfers---enable optimal mesh update algorithms. We demonstrate an optimal cache-oblivious linear solver using our mesh update algorithm.We present two quadtree generation algorithms. These algorithms perform nearly optimally in both the time complexity and cache complexity. We then show how to generate meshes from point sets with near optimal cache complexity and optimal time complexity.We construct cache-oblivious particle simulation algorithms. We study methods of laying out input data for the Fast Multipole Method (FMM) on uniformly distributed particles and give an optimal algorithm solving FMM on such layout.