Past Applied Topology Seminar

7 May 2021
15:00
Dhananjay Bhaskar
Abstract

Active matter systems, ranging from liquid crystals to populations of cells and animals, exhibit complex collective behavior characterized by pattern formation and dynamic phase transitions. However, quantitative analysis of these systems is challenging, especially for heterogeneous populations of varying sizes, and typically requires expertise in formulating problem-specific order parameters. I will describe an alternative approach, using a combination of topological data analysis and machine learning, to investigate emergent behaviors in self-organizing populations of interacting discrete agents.

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
30 April 2021
15:00
Don Sheehy

Further Information: 

Don Sheehy is an Associate Professor of Computer Science at North Carolina State University.  He received his B.S.E. from Princeton University and his Ph.D. in Computer Science from Carnegie Mellon University.   He spent two years as a postdoc at Inria Saclay in France.  His research is in algorithms and data structures in computational geometry and topological data analysis.  

Abstract

Given a persistence diagram with n points, we give an algorithm that produces a sequence of n persistence diagrams converging in bottleneck distance to the input diagram, the ith of which has i distinct (weighted) points and is a 2-approximation to the closest persistence diagram with that many distinct points. For each approximation, we precompute the optimal matching between the ith and the (i+1)st. Perhaps surprisingly, the entire sequence of diagrams as well as the sequence of matchings can be represented in O(n) space. The main approach is to use a variation of the greedy permutation of the persistence diagram to give good Hausdorff approximations and assign weights to these subsets. We give a new algorithm to efficiently compute this permutation, despite the high implicit dimension of points in a persistence diagram due to the effect of the diagonal. The sketches are also structured to permit fast (linear time) approximations to the Hausdorff distance between diagrams -- a lower bound on the bottleneck distance. For approximating the bottleneck distance, sketches can also be used to compute a linear-size neighborhood graph directly, obviating the need for geometric data structures used in state-of-the-art methods for bottleneck computation.

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
12 March 2021
15:00
Abstract

Reducing a chain complex (whilst preserving its homotopy-type) using algebraic Morse theory ([1, 2, 3]) gives the same end-result as Gaussian elimination, but AMT does it only on certain rows/columns and with several pivots (in all matrices simultaneously). Crucially, instead of doing costly row/column operations on a sparse matrix, it computes traversals of a bipartite digraph. This significantly reduces the running time and memory load (smaller fill-in and coefficient growth of the matrices). However, computing with AMT requires the construction of a valid set of pivots (called a Morse matching).

In [4], we discover a family of Morse matchings on any chain complex of free modules of finite rank. We show that every acyclic matching is a subset of some member of our family, so all maximal Morse matchings are of this type.

Both the input and output of AMT are chain complexes, so the procedure can be used iteratively. When working over a field or a local PID, this process ends in a chain complex with zero matrices, which produces homology. However, even over more general rings, the process often reveals homology, or at least reduces the complex so much that other algorithms can finish the job. Moreover, it also returns homotopy equivalences to the reduced complexes, which reveal the generators of homology and the induced maps $H_{*}(\varphi)$. 

We design a new algorithm for reducing a chain complex and implement it in MATHEMATICA. We test that it outperforms other CASs. As a special case, given a sparse matrix over any field, the algorithm offers a new way of computing the rank and a sparse basis of the kernel (or null space), cokernel (or quotient space, or complementary subspace), image, preimage, sum and intersection subspace. It outperforms built-in algorithms in other CASs.

References

[1]  M. Jöllenbeck, Algebraic Discrete Morse Theory and Applications to Commutative Algebra, Thesis, (2005).

[2]  D.N. Kozlov, Discrete Morse theory for free chain complexes, C. R. Math. 340 (2005), no. 12, 867–872.

[3]  E. Sköldberg, Morse theory from an algebraic viewpoint, Trans. Amer. Math. Soc. 358 (2006), no. 1, 115–129.

[4]  L. Lampret, Chain complex reduction via fast digraph traversal, arXiv:1903.00783.

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
26 February 2021
15:00
Abstract

The well known node2vec algorithm has been used to explore network structures and represent the nodes of a graph in a vector space in a way that reflects the structure of the graph. Random walks in node2vec have been used to study the local structure through pairwise interactions. Our motivation for this project comes from a desire to understand higher-order relationships by a similar approach. To this end, we propose an extension of node2vec to a method for representing the k-simplices of a simplicial complex into Euclidean space. 

In this talk I outline a way to do this by performing random walks on simplicial complexes, which have a greater variety of adjacency relations to take into account than in the case of graphs. The walks on simplices are then used to obtain a representation of the simplices. We will show cases in which this method can uncover the roles of higher order simplices in a network and help understand structures in graphs that cannot be seen by using just the random walks on the nodes. 

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
12 February 2021
15:00
Abstract

Crystal Structure Prediction aims to reveal the properties that stable crystalline arrangements of a molecule have without stepping foot in a laboratory, consequently speeding up the discovery of new functional materials. Since it involves producing large datasets that themselves have little structure, an appropriate classification of crystals could add structure to these datasets and further streamline the process. We focus on geometric invariants, in particular introducing the density fingerprint of a crystal. After exploring its computations via Brillouin zones, we go on to show how it is invariant under isometries, stable under perturbations and complete at least for an open and dense space of crystal structures.

 

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
29 January 2021
15:00
Abstract

Ollivier Ricci curvature is a notion originated from Riemannian Geometry and suitable for applying on different settings from smooth manifolds to discrete structures such as (directed) hypergraphs. In the past few years, alongside Forman Ricci curvature, this curvature as an edge based measure, has become a popular and powerful tool for network analysis. This notion is defined based on optimal transport problem (Wasserstein distance) between sets of probability measures supported on data points and can nicely detect some important features such as clustering and sparsity in their structures. After introducing this notion for (directed) hypergraphs and mentioning some of its properties, as one of the main recent applications, I will present the result of implementation of this tool for the analysis of chemical reaction networks. 

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
14 January 2021
10:00
to
12:00
Greg Henselman-Petrusek

Further Information: 

Zoom passcode: Basis

Abstract

Giancarlo Rota once wrote of matroids that "It is as if one were to
condense all trends of present day mathematics onto a single
structure, a feat that anyone would a priori deem impossible, were it
not for the fact that matroids do exist" (Indiscrete Thoughts, 1997).
This makes matroid theory a natural hub through which ideas flow from
one field of mathematics to the next. At the end of our three-day
workshop, participants will understand the most common objects and
constructions in matroid theory to the depth suitable for exploring
many of these interesting connections. We will also pick up some
highly practical matroid tools for working through problems in
persistent homology, (optimal) cycle representatives, and other
objects of interest in TDA.

 

Day 3, Lecture 1

Circuits in persistent homology


Day 3, Lecture 2

Exercise: write your own persistent homology algorithm!
 

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
12 January 2021
10:00
to
12:00
Greg Henselman-Petrusek

Further Information: 

Zoom Passcode: Basis

Abstract

Giancarlo Rota once wrote of matroids that "It is as if one were to
condense all trends of present day mathematics onto a single
structure, a feat that anyone would a priori deem impossible, were it
not for the fact that matroids do exist" (Indiscrete Thoughts, 1997).
This makes matroid theory a natural hub through which ideas flow from
one field of mathematics to the next. At the end of our three-day
workshop, participants will understand the most common objects and
constructions in matroid theory to the depth suitable for exploring
many of these interesting connections. We will also pick up some
highly practical matroid tools for working through problems in
persistent homology, (optimal) cycle representatives, and other
objects of interest in TDA.

Day 2, Lecture 1, 10-10.45am

Matroid representations, continued


Day 2, Lecture 2, 11-11.45am

Matroids in homological algebra

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar
11 January 2021
10:00
Greg Henselman-Petrusek

Further Information: 

Zoom Passcode: Basis

PDF icon Matroids.pdf

Abstract

Giancarlo Rota once wrote of matroids that "It is as if one were to
condense all trends of present day mathematics onto a single
structure, a feat that anyone would a priori deem impossible, were it
not for the fact that matroids do exist" (Indiscrete Thoughts, 1997).
This makes matroid theory a natural hub through which ideas flow from
one field of mathematics to the next. At the end of our three-day
workshop, participants will understand the most common objects and
constructions in matroid theory to the depth suitable for exploring
many of these interesting connections. We will also pick up some
highly practical matroid tools for working through problems in
persistent homology, (optimal) cycle representatives, and other
objects of interest in TDA.

Condensed outline

Day 1, Lecture 1, 10-10.45am

Definitions There are many definitions of matroids. Here's how to organize them.
Examples We work with matroids every day. Here are a few you have seen.
Important properties What's so great about a matroid?

Day 1, Lecture 2, 11-11.45am

The essential operations: deletion, contraction, and dualization
Working with matroids: matrix representations

The join button will be published on the right (Above the view all button) 30 minutes before the seminar starts (login required).

  • Applied Topology Seminar

Pages