MARC 主機 00000nam  2200337   4500 
001    AAI3399605 
005    20110119094954.5 
008    110119s2010    ||||||||||||||||| ||eng d 
020    9781109653731 
035    (UMI)AAI3399605 
040    UMI|cUMI 
100 1  Wang, Kebin 
245 10 Cache-oblivious scientific computing 
300    99 p 
500    Source: Dissertation Abstracts International, Volume: 71-
       03, Section: B, page: 1826 
500    Adviser:  Shang-Hua Teng 
502    Thesis (Ph.D.)--Boston University, 2010 
520    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 
520    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 
520    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 
520    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 
590    School code: 0017 
650  4 Computer Science 
690    0984 
710 2  Boston University 
773 0  |tDissertation Abstracts International|g71-03B 
856 40 |u