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....[ Read more ]

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.