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 |uhttp://pqdd.sinica.edu.tw/twdaoapp/servlet/
advanced?query=3399605