OUT-OF-CORE CONSTRUCTION AND SIMPLIFICATION OF MORSE-SMALE COMPLEXES

MPhil Thesis Defence


Title: "OUT-OF-CORE CONSTRUCTION AND
SIMPLIFICATION OF MORSE-SMALE COMPLEXES"

By

Mr. Wenqi Zhu


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 based
on gradients. Topological persistence is defined on each of the critical
points in the Morse-Smale Complex to measure its importance. Sometimes, it
is also necessary to simplify the Morse-Smale Complexes based on
persistence so that the main topological characteristics of the complex
are preserved.

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
secondary memory. The I/O cost is usually much larger than the computation
in 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.

My work 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.


Date:				Monday, 4 August 2008

Time:				10:00a.m.-12:00noon

Venue:				Room 3402
				Lifts 17-18

Committee Members:		Dr. Ke Yi (Supervisor)
				Dr. Sunil Arya (Chairperson)
				Dr. Pedro Sander


**** ALL are Welcome ****