6. Homology and cohomology algorithms with
applications
|
Polish supervisor:
|
Marian Mrozek
|
|
Cooperating partners:
|
Graham Ellis (National University of Ireland, Galway)
Martin Raussen (Aalborg University, Denmark)
|
The goal of this project is to develop and apply fast and
efficient homology algorithms. Although the task of computing
homology may be easily reduced to finding the Smith
diagonalization of the matrices of the boundary maps, the super
cubical complexity of the Smith diagonalization causes that this
approach fails in the presence of large input. This causes the
demand for specialized, fast homology algorithms. Fast homology
algorithms are in particular needed in topological methods in:
data and image analysis, rigorous numerics of dynamical systems,
electromagnetic engineering, material science, robotics, the
design of concurrent algorithms. In these fields the size of input
is often measured in millions of elements and more. The problem is
complicated by the range of the required output, which varies from
Betti numbers, through homology generators, particularly homology
generators of minimal size, to matrices of homology maps. Of
special interest is persistent homology indicating the life span
of homology generators under a filtration.
In the project the student may focus either on the theoretical
aspects of efficient homology computations or on the design and
implementation of homology algorithms, according to his or her
preferences. She/he is expected to work on one or more topics from
the following list
-
Better understanding of the settings in which reduction
algorithms, particularly the coreduction algorithm, work fast.
Numerical evidence gathered so far indicates that in the class of
homeomorphic inputs the optimal homology algorithm should work in
almost linear time.
-
Extending the available reduction algorithms to the setting of
a class of CW-complexes with a good memory representation
allowing for quick evaluation of coincidence coefficients. This is
particularly important for geometric inputs with non-uniform
fractal structure, because then the size of input may be reduced
drastically.
-
Extending the available homology reduction algorithms to
cohomology. They are particularly important in applications to
electromagnetic engineering.
-
Adaptation of the coreduction homology algorithm to the
computation of persistent homology, in particular to the so called
two-sided persistent homology, important in material science.
-
Parallelization of at least some of the available homology
algorithms. Reduction algorithms seem to be perfect for this task.
-
Finding the relations between the reduction algorithms and the
discrete Morse theory. This may result in better understanding of
the complexity of homology algorithms.
|
|
|
