Please use this identifier to cite or link to this item:

Out-of-core construction and simplification of Morse-Smale complexes

Authors Zhu, Wenqi
Issue Date 2008
Summary 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.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2008
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 341 B HTML
Copyrighted to the author. Reproduction is prohibited without the author’s prior written consent.