Record:   Prev Next
作者 Wang, Kebin
書名 Cache-oblivious scientific computing
國際標準書號 9781109653731
book jacket
說明 99 p
附註 Source: Dissertation Abstracts International, Volume: 71-03, Section: B, page: 1826
Adviser: Shang-Hua Teng
Thesis (Ph.D.)--Boston University, 2010
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
School code: 0017
Host Item Dissertation Abstracts International 71-03B
主題 Computer Science
Alt Author Boston University
Record:   Prev Next