說明 
99 p 
附註 
Source: Dissertation Abstracts International, Volume: 7103, Section: B, page: 1826 

Adviser: ShangHua 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 cacheoblivious paradigm is a novel technique for designing algorithms and analyzing algorithm efficiencies. One advantage of cacheoblivious 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 cacheoblivious iterative linear solvers, cacheoblivious mesh generation algorithms, and cacheoblivious particle simulation algorithms. To our knowledge, our work is the first attempt to adapt the cacheoblivious paradigm to scientific computing 

We describe our cacheoblivious mesh layout algorithms and cacheoblivious linear solver. We present a new algorithm for generating decomposition trees. We then show that our mesh layout algorithmswhich run in near optimal time and nearest optimal memory transfersenable optimal mesh update algorithms. We demonstrate an optimal cacheoblivious 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 cacheoblivious 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 7103B

主題 
Computer Science


0984

Alt Author 
Boston University

