HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/4245
Title: Out-of-core construction and simplification of Morse-Smale complexes
Authors: Zhu, Wenqi
Issue Date: 2008
Abstract: The Morse-Smale complex is a frequently used structure to represent the topology of a scalar field, which is used in many scientific applications. It captures the topological characteristics by segmenting the field by the integral lines based on the gradients. Topological persistence is defined on each critical point in the Morse-Smale complex to measure its importance. Sometimes, it is also necessary to simplify the Morse-Smale complex based on persistence so that the main topological features of the complex are preserved while the minor ones are removed. When data sets become larger and larger, it will expose the scalability problem for the existing algorithms in the framework of the RAM model. In the RAM model, all the data units can be accessed in constant time. However, when the data can not be loaded into the main memory at once, there will be additional swapping cost (I/O) between the main memory and the secondary memory. The I/O cost is usually much larger than the computation in the main memory and becomes the bottleneck. Thus the existing algorithms become far slower than what we would like when there are lots of I/Os. This thesis mainly focuses on out-of-core algorithms to construct and simplify Morse-Smale complexes, while minimizing the I/O costs. We prove theoretical bounds on the I/O complexity for both algorithms. Experiments are conducted and show that the out-of-core algorithms are order-of-magnitude faster than their internal memory counterparts when the data set exceeds the physical memory limit.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2008
ix, 57 leaves : ill. ; 30 cm
HKUST Call Number: Thesis CSED 2008 ZhuW
URI: http://hdl.handle.net/1783.1/4245
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.