Résumé

ED-Stic

Inria

Doctor of Philosophy

Collapses and Persistent Homology by Siddharth Pritam

Dans cette thèse, nous introduisons deux nouvelles approches pour calculer l'homologie persistante (HP) d'une séquence de complexes simpliciaux. L'idée de base est de simplifier les complexes de la séquence d'entrée en utilisant des types spéciaux de collapses (effondrement), les collapses forts et les collapses d'arêtes, et de calculer l'HP d'une séquence réduite de plus petite taille qui a la même HP que la séquence initiale.

Notre première approche utilise les collapses forts introduits par J. Barmak et E. Miniam [DCG (2012)]. Un collapse fort supprime les sommets dits dominés d'un complexe simplicial. Notre approche utilisant les collapses forts a plusieurs caractéristiques qui la distinguent des travaux antérieurs. La méthode n'est pas limitée aux filtrations (c'est-à-dire aux séquences de sous-complexes simpliciaux imbriqués) mais fonctionne pour d'autres types de séquences comme les tours et les zigzags. Par ailleurs, pour implémenter les collapses forts, il suffit de représenter les simplexes maximaux du complexe, et pas l'ensemble de tous ses simplexes, ce qui économise beaucoup d'espace et de temps. De plus, les complexes de la séquence peuvent être collapsés indépendamment et en parallèle.

Dans le cas des complexes en drapeaux (flag complexes), les collapses forts peuvent être réalisés sur le 1-squelette du complexe et le complexe résultat est également un complexe en drapeau. Nous montrons que si l'on restreint la classe des complexes simpliciaux aux complexes en drapeaux, on peut améliorer la complexité en temps et en espace de facon décisive par rapport aux travaux antérieurs. Lorsque les collapses forts sont appliqués aux complexes d'une tour de complexes en drapeau, nous obtenons une séquence réduite qui est aussi une tour de complexes en drapeau que nous appelons le coeur de la tour. Nous convertissons ensuite le coeur de la tour en une filtration équivalente pour calculer son HP. Là encore, nous n'utilisons que les 1-squelettes des complexes. La méthode résultante est simple et extrêmement efficace.

Nous étendons la notion de sommet dominé au cas de simplexes de dimension quelconque. Le concept d'arête dominée apparait très puissant et nous l'étudions dans le cas des complexes en drapeaux de facon plus détaillée. Nous montrons que les collapses d'arêtes (suppression des arêtes dominées) dans un complexe en drapeaux peut être effectué, comme précédemment, en utilisant uniquement le 1-squelette du complexe. En outre, le complexe résiduel est également un complexe de drapeaux. Ensuite, nous montrons que, comme dans le cas des collapses forts, on peut utiliser les collapses d'arêtes pour réduire une filtration de complexes en drapeaux en une filtration de complexes en drapeaux plus petite qui a la même HP. Là encore, nous utilisons uniquement le 1-squelettes des complexes.

Comme l'ont démontré de nombreuses expériences sur des données publiques, les approches développées sont extrêmement rapides et efficaces en mémoire. En particulier, la méthode utilisant les collapses d'arêtes offre de meilleures performances que toutes les méthodes connues, y compris l'approche par collapses forts. Enfin, nous pouvons faire des compromis entre précision et temps de calcul en choisissant le nombre de complexes simpliciaux de la séquence à collapser. In this thesis, we introduce two new approaches to compute the Persistent Homology (PH) of a sequence of simplicial complexes. The basic idea is to simplify the complexes of the input sequence by using special types of collapses (strong and edge collapse) and to compute the PH of an induced sequence of smaller size that has the same PH as the initial one.

Our first approach uses strong collapse which is introduced by J. Barmak and E. Miniam [DCG (2012)]. Strong collapse comprises of removal of special vertices called dominated vertices from a simplicial complex. Our approach with strong collapse has several salient features that distinguishes it from previous work. It is not limited to filtrations (i.e. sequences of nested simplicial subcomplexes) but works for other types of sequences like towers and zigzags. To strong collapse a simplicial complex, we only need to store the maximal simplices of the complex, not the full set of all its simplices, which saves a lot of space and time. Moreover, the complexes in the sequence can be strong collapsed independently and in parallel.

In the case of flag complexes strong collapse can be performed over the 1-skeleton of the complex and the resulting complex is also a flag complex. We show that if we restrict the class of simplicial complexes to flag complexes, we can achieve decisive improvement in terms of time and space complexities with respect to previous work. When we strong collapse the complexes in a flag tower, we obtain a reduced sequence that is also a flag tower we call the core flag tower. We then convert the core flag tower to an equivalent filtration to compute its PH. Here again, we only use the 1-skeletons of the complexes. The resulting method is simple and extremely efficient.

We extend the notions of dominated vertex to a simplex of any dimension. Domination of edges appear to be very powerful and we study it in the case of flag complexes in more detail. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex as well. Furthermore, the residual complex is a flag complex as well. Next we show that, similar to the case of strong collapses, we can use edge collapses to reduce a flag filtration F to a smaller flag filtration F c with the same persistence. Here again, we only use the 1-skeletons of the complexes.

As a result and as demonstrated by numerous experiments on publicly available data sets, our approaches are extremely fast and memory efficient in practice. In particular the method using edge collapse performs the best among all known methods including the strong collapse approach. Finally, we can compromize between precision and time by choosing the number of simplicial complexes of the sequence we strong collapse.

Declaration of Authorship

I, Siddharth Pritam, declare that this thesis titled, "Collapses and Persistent Homology" and the work presented in it are my own. I confirm that:

• This work was done wholly or mainly while in candidature for a research degree at this University.

• Where any part of this thesis has previously been submitted for a degree or any other qualification at this University or any other institution, this has been clearly stated.

• Where I have consulted the published work of others, this is always clearly attributed.

• Where I have quoted from the work of others, the source is always given. With the exception of such quotations, this thesis is entirely my own work.

• I have acknowledged all main sources of help.

• Various pictures used in this thesis specially in Chapter 1 and Chapter 2 has been retrieved with free access from internet.

• Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed myself.

Signed:

Date: 01/07/2020 ix "Arise awake and stop not until the goal is achieved "

Swami Vivekanand

First and foremost, I would like to thank Jean-Daniel for giving me the opportunity to be his PhD student. His unique mentorship has effortlessly nurtured the essential qualities in me that are required to be a researcher. His vision has helped me develop a taste for algorithmic mathematics with an emphasis on simplicity and efficiency. He also gave me a complete freedom and let me wonder scientifically and geographically.

Apart from teaching me the technical skills, his encouragement and support has always helped me navigate through the tough times. Despite his busy schedule, he always had time for his students and was always available to provide his valuable inputs. I also thank him for his amiable personality and sense of humor which made the whole journey way more smoother than it should be.

I thank Michael Kerber who introduced me to Persistent Homology during my internship at MPI Saarbruecken. That internship turned out to be very useful in the end. I also thank him for writing the report of my thesis and being part of the jury.

I would not have met Jean-Daniel, if it wasn't for Arijit Ghosh, whom I met at MPI Saarbruecken. Being a senior from IIT Kharagpur, Arijit has always supported me like a big brother and I am very grateful for that.

I want to thank the members of my thesis committee: Dominique Attali, Frédéric Cazal, Tamal Dey, Marc Glisse, Kathryn Hess and André Lieutier. Their feedback, and insights have been very helpful, specially Dominique Atalli for a thorough examination of the manuscript and identifying many crucial mistakes.

It's been a privilege to do my graduate studies at DataShape, one of the world's leading research team in Computational Topology. I thank Marc Glisse for taking interest in my research and providing many valuable inputs during numerous discussions we had. I thank Vincent Rouvreau for his help with implementations of all the codes in GUDHI. I thank Mathijs Wintraecken for reading initial drafts of some of my papers and his peculiar way of helping me maintain some mental sanity during the initial years of my PhD studies. I thank Kunal Dutta for not letting me miss India too much. I would like to thank Owen Rouille for organizing the online defense during the Covid-19 pandemic. And I thank David-Cohen Steiner and Clément Maria for their many academic and non-academic discussions. I would also like to thank Florence Barbara and Sophie Honnorat for their efficient and sincere support in administrative matters.

Working on a doctoral thesis can lead to obnoxious behavior, I thank all my friends at Inria who kept me socially acceptable, specially Romain Tetley and Ivana Kojcic.

I thank my brother Shashank and my sister Shristi for their consistent support and making me feel that I am doing something worthwhile. I thank my deerest friend Kritiva for her love and encouragement and being part of the journey since the very beginning of the search for doctoral position.

I finally end with thanking my parents and my uncle for their immense contribution, support, encouragement, hardships and sacrifices they made to make me achieve whatever little I could do in this world.

2.4

The edge [u, v] satisfies the link condition. The complex (in the right) which is the image of an edge contraction may not be a subcomplex of the original complex K. As the triangle [p, q, u] doesn't exist in K. . . .

2.5

At no scale the union of balls can capture both the loops. . . . . . . . .

2.6

A sequence of simplicial complexes connected through inclusions. . .

3.1

Illustration of an elementary strong collapse. In the complex on the left, v is dominated by v . The link of v is highlighted in red. Removing v leads to the complex on the right. . . . . . . . . . . . . . . . . . . . . . .

3.2

Left: K (in grey), Right: N (K) (in grey) and N 2 (K) (in red). N 2 (K) is isomorphic to a full-subcomplex of K highlighted in red on the left. . .

5.1

The above complex does not have any dominated vertex and thus cannot be 0-collapsed. However, by proceeding from the boundary edges, one can edge collapse this complex to a 1-dimensional complex. The 1-core obtained in this way is collapsible to a point using 0-collapse.

5.2

The complex on the left has two different 1-cores, the one in the middle is obtained after removing the inner edges [START_REF] Adamaszek | Complexity of simplicial homology and independence complexes of chordal graphs[END_REF][START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF] and [START_REF] Bauer | Ripser[END_REF][START_REF] Bauer | Clear and compress: Computing persistent homology in chunks[END_REF], and the one in the right by removing the outer edges [START_REF] Adamaszek | Complexity of simplicial homology and independence complexes of chordal graphs[END_REF][START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF] and [START_REF] Bauer | Ripser[END_REF][START_REF] Bauer | PHAT -persistent homology algorithms toolbox[END_REF]. Note that the one in the right can be further strong collapsed. . . . . . . . . . . . . . . Chapter 1

List of Tables

Introduction

Topological Data Analysis

Empirical verification is at the heart of scientific investigation and data is the main object which facilitates the verification. There are many different ways one can possibly extract information out of data. Mathematics is the language that provides different tools through which we can interact with data. Each tool reveals a different nature of the data and often their combinations provides a more broader understanding. In this thesis we focus on one specific mathematical tool, Topology along with Geometry.

Topology is the branch of mathematics which studies the characterization of invariants of a space under 'continuous deformations'. These invariants can be the number of connected components, loops, voids, holes, tunnels and their higher-dimensional analogs. They can also be purely algebraic or combinatorial in nature, like the Euler characteristic.

In most cases data comes with a notion of similarity between its constituent elements (points) which leads to the notion of distance between them. The notion of distance allows us to talk about geometry and topology. Therefore data has shape and using geometric and topological methods one could extract the information about its shape. Metric space is the formalism of the concept of similarity and often in practice data is presented as a point set in a metric space. Given a point set P in a metric space, we assume that it is a finite sample of some underlying space X and we want to infer the topology of X using P. Below is a simple example, a point set sampled from a torus. The idea of topological inference is not entirely new and it has been done in rather simplistic forms. For example given a point set as in Figure 1.2, we would like to classify or to cluster them into similar groups. The topological interpretation of clustering would be to understand the nature and the number of connected components of the point set. Traditionally there are algorithms like K-means and PCA (Principle Component Analysis) to perform such tasks. Another example is regression where one starts with certain hypothesis about the shape of the data like being linear and wants to compute the line that fits the data best as shown in Figure 1.3. The underlying space X could be far more complex than being linear or of the shape of torus, with possibly many more holes of different sizes and of high dimensions.

The mathematical formalism which captures the notion of connectivity, loops, voids, tunnels and their higher-dimensional analogs is called homology. Homology is a topological invariant, that is, it does not change under 'continuous deformations' and it is of algebraic nature. We associate one group per dimension to the space X that 'measures' the number and the nature of the 'holes' of X. Topological Data Analysis (abbreviated as TDA) is a new and fast emerging field, whose goal is to extract geometric and topological properties of complex data with advanced tools like homology.

Persistent Homology

Since the point set P is usually a finite sample of X therefore it can not have the exact topology of X. One possible way to infer the topology of X is to consider balls of some radius (called scale), around each point of P such that their union covers X in a 'nice' way. In the above example Figure 1.4, at very small scale, the points seem to be isolated, with balls around them forming many small clusters. At medium scale, it is apparent that the points have circular shape. Finally, at large scale, the balls around them forms a single large cluster and does not seem to represent the original shape. Therefore, the radius of the balls in the middle could be thought as the 'right' scale at which the union of balls represents the circle from which the points could have been possibly sampled. This brings us the question of how to choose the 'right' scale. However, there might not be a single 'right' scale. In the example below, Figure 1.5, at no scale the union of balls could capture the two loops. To resolve this issue we would naturally like to look at the balls around the point set at multiple scale. If we track the evolution of the union of the balls as the scale increases, we see that a specific topological feature (hole) starts appearing at a certain scale and then dies at another scale. Therefore, every specific topological feature has a life span in this process, some persist longer and others die quickly. The natural conclusion of this observation would be that the features that last longer are real features of the data and the small persisting features are noise. The mathematical idea to capture this intuition is called Persistent homology.

Persistent homology (PH) was introduced by Edelsbrunner, Letscher and Zomorodian in their milestone paper [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF]. The scale of life and death of all topological features could be summarized as points (life, death) in R 2 . This summary of points is called the The computation of persistence diagram is performed over a combinatorial or discrete structure on the given point set P. This structure is called a Simplicial complex. A simplicial complex is a collection of points, edges, triangles, tetrahedron and their higher dimensional analogs called simplices, such that they are 'nicely' glued. Formally, a k-simplex σ is the convex hull of (k + 1) affinely independent points and k is called its dimension. A sub-collection τ of the (k + 1) points is also a simplex, called a face of σ and σ is called a co-face of τ. A simplicial complex K is then a collection of simplices such that 1. A face τ of any simplex σ is in K.

2. Two simplices σ 1 and σ 2 in K intersect only at a common face τ.

The dimension of a simplicial complex K is the maximum of the dimensions of its simplices. Simplicial complexes are one of the most important combinatorial structure in computational topology and arise naturally in many different contexts. There is a simplicial complex associated to the union of balls around the points in P. Given P and scale , we add edges between the points of P whenever two balls around them of radius have a common intersection, we put a triangle between three points of P whenever the balls around them have a common intersection, likewise we add tetrahedrons and higher dimensional simplices. The simplicial complex constructed in this fashion is called the Čech complex denoted as C(P, ). Most important, the union of balls and the Čech complex have the same topology (more precisely they are homotopy equivalent). See Figure 1.6 for an example of a union of balls and its associated Čech complex. As we increase the scale, the associated Čech complexes {C(P, )} 0≤ form a nested sequence, i.e. for 1 ≤ 2 , C(P, 1 ) ⊆ C(P, 2 ). More general such a sequence of nested simplicial complexes is called a filtration. Traditionally persistence has been defined and computed for such sequences.

The Alpha complex is another simplicial complex which arises from the union of balls and has the same homology as the Čech complex. Here, we restrict the ball around a point by the corresponding Voronoi cell of the point and look at the intersection patterns of the restricted balls. When two restricted balls intersect we put an edge and for an intersection of three restricted balls we put a triangle and so on so forth. This means that given two points whose Voronoi cells are not intersecting the balls around them would not intersect as well. Therefore points that are far apart will not span a simplex in the alpha complex. The alpha complex is a subcomplex of the Čech complex and the Delaunay triangulation. Below is an example of a union of restricted balls and its associated alpha complex, Figure 1.7. We define another simplicial complex closely related to the Čech complex. We define a subset of points of P as a simplex σ whenever pairwise distance between any two points of σ is less than 2 . We call this simplicial complex the Vietoris-Rips complex or simply the Rips complex, denoted as R(P, ).

The Rips complex is a special type of simplicial complex called a Flag complex. Flag complexes are fully characterized by their graph (or 1-skeleton), the other faces being obtained by computing the cliques of the graph. Hence, a flag complex can be represented by its 1-skeleton, which is a very compact representation. Flag complexes are very popular and, in particular, Rips complexes are widely used in Topological Data Analysis. Along with Rips complex, Čech and alpha complexes are commonly used too, specially in low dimensions. We discuss more about their advantages and disadvantages in Section 1.4.

We briefly summarize the complete pipeline of the PH computation.

Point Set P A Filtra- tion F over P Boundary Matrix M of F Persistence Diagram
Given a point set P in a metric space, we build a sequence of simplicial complexes (for example a filtration F of Rips complex) over P. We then compute a boundary matrix M over a filtration, such that the columns and rows of the boundary matrix are the simplices of the filtration sorted as per their filtration value. A non-zero entry M[σ i ][σ j ] implies σ i is a face of σ j . We then reduce this matrix to a special form, to retrieve special pairings of the simplices that corresponds to the points in the persistence diagram. We discuss the reduction algorithm in more details in Chapter 2. Stability: Two point sets P and P can be compared by their corresponding persistence diagrams associated to some filtrations defined over P and P . The bottleneck distance is a measure of similarity between two persistence diagrams, which we define more precisely in Chapter 2.

F K 1 → K 2 → K 3 → • • • → K n M M m,n =      0 0 • • • 1 0 1 • • • 1 . . . . . . . . . . . . 0 1 • • • 0      PD Figure 1.8
Stability of persistence diagrams is one of the most important result in the theory of persistence. It states that, small perturbations in the point set P leads to a small perturbation in its persistence diagram. More formally if P and P are two point sets such that their Hausdorff distance is at most then the bottleneck distance between their corresponding persistence diagrams would be bounded above by . The first result about stability of persistence diagram was proved by Cohen-Steiner, Edelsbrunner and Harer in [START_REF] Edelsbrunner | Stability of persistence diagrams[END_REF]. The stability in [START_REF] Edelsbrunner | Stability of persistence diagrams[END_REF] was defined for functions however we used the formulation of point sets for simple exposition.

At a scale , the Čech complex and the Rips complex of a point P ∈ R d follow the following inclusion property,

R(P, ) ⊆ C(P, √ 2 ) ⊆ R(P, √ 2 )
and are called interleaved. As a consequence of stability theorem, the interleaving relation implies that the bottleneck distance between the persistence diagram of a Rips filtration and the persistence diagram of the corresponding Čech filtration is bounded above by √ 2.

Extensions of Persistent Homology

Since its introduction, the theory of persistence has evolved very rapidly in subsequent years both on theoretical and algorithmic fronts. Carlsson and Zomorodian provided solid algebraic foundations and extended the algorithm for more general cases in [START_REF] Zomorodian | Computing persistent homology[END_REF]. Subsequently, Persistent Homology was defined for sequences more general than filtrations. A Zigzag filtration is a sequence of simplicial complexes connected through inclusions and removals (inclusion in the reverse direction) of simplices: A zigzag filtration:

K 1 → K 2 ← • • • → K m
Carlsson and Silva defined and provided an algorithm to compute zigzag persistence [START_REF] Carlsson | Zigzag persistence[END_REF] which was further improved in [START_REF] Carlsson | Zigzag persistent homology and real-valued functions[END_REF].

The theory of persistence extends naturally to zigzag sequences due to their connection with quiver theory [START_REF] Derksen | Quiver representations[END_REF]. For the same reason it was natural to define persistence diagrams corresponding to sequences of simplicial complexes connected through more general simplicial maps not just inclusions. Such a sequence is called a tower if the maps are in the same directions and a zigzag sequence if the maps are in both directions. Below are examples of a tower and a zigzag sequence respectively.

Tower:

K 1 f 1 -→ K 2 f 2 -→ • • • → K m A zigzag sequence: K 1 f 1 -→ K 2 g 2 ← -• • • → K m
Here f i and g i are simplicial maps. The first algorithm to compute the persistence of a tower was given by Dey, Fan and Wang in [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF]. Their strategy was to transform a tower into an equivalent filtration using the link condition over edges between contracting vertices of the simplicial maps. Their approach was further improved by Kerber and Schreiber in [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF] by using coning instead of the link condition. They also provided a theoretical guarantee over the size of the equivalent filtration. Using the same strategies it is possible to compute the zigzag persistence of any general zigzag sequence by converting it to an equivalent zigzag filtration.

Towers appear frequently in situations where one wants to approximate or sparsify a filtration using certain methods that involves mapping several vertices to one vertex that is either a topological or a geometric representative. The examples of such methods can be found in the work of Dey et. al. [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF] and the work of Choudhary et. al. [START_REF] Choudhary | Improved topological approximations by digitization[END_REF]. Our work reported in [START_REF] Boissonnat | Strong Collapse for Persistence[END_REF][START_REF] Boissonnat | Computing persistent homology of flag complexes via strong collapses[END_REF] also reduces a filtration usually to a tower.

Persistence has also been extended to multiple parameters, that is, there are more variables than the distance that dictate the growth of the filtrations. It is then called multidimensional persistence. Multidimensional persistence has been introduced by Carlsson and Zomorodian [START_REF] Zomorodian | The theory of multidimensional persistence[END_REF]. Multidimensional persistence does not have a well behaved descriptor like persistence diagram. However, there are other invariants like the rank invariant [START_REF] Zomorodian | The theory of multidimensional persistence[END_REF] and minimal presentations. Recently an algorithm to compute minimal presentations for 2-dimensional filtrations has been introduced [START_REF] Lesnick | Computing minimal presentations and betti numbers of 2-parameter persistent homology[END_REF].

Challenges and Previous Work

Challenges. The size of a filtration is defined as the size (number of simplices) of the last (largest) complex in the sequence. If the size of the filtration is n then the computation of persistence takes O(n 3 ) time 1 . In practice, it has been observed that the running time of the persistence algorithms is linear in n. This makes computation of persistence reasonably fast for small filtrations. However as the dimension of the simplices grows the size of any filtration ( Čech, Rips, alpha) grows exponentially with the dimension and it becomes impractical to compute persistence for higher dimensional filtrations. The major bottleneck in computing persistence diagram is the computation time of the complexes and their sizes. Improving the performance of computing Persistent Homology has been a central goal in Topological Data Analysis since the early days of the field about 20 years ago.

The time complexity of computing the Čech complex depends exponentially on the dimension d of the ambient space. Also the number of simplices in a Čech filtration could be very large, exponential in the number of points in P, O(2 n v ), where n v = |P|.

Therefore the computation time and its size makes a Čech filtration almost unusable for PH computation.

Alpha complexes have a better size complexity, O(n

d 2 v
), where n v is the number of points in P and d is the ambient dimension. That leads to a smaller size and fast computation in low ambient dimensions. However, in higher ambient dimensions the alpha complex has the same issues as the Čech complex.

The time to compute Rips complexes is much faster as we only need to compute the pairwise distances between the points of P and therefore the time complexity is independent of the ambient dimension d of the point set. However, Rips complexes has the same size complexity as the Čech complex, and therefore as the dimension of the complex grows the computation of persistence of Rips filtration is time intensive as well.

The k-skeleton of a simplicial complex K is the set of simplices of dimension less than or equal to k, it is a subcomplex of K. To compute Persistent Homology until dimension k, we only need simplices up to dimension k + 1, i.e. the (k + 1)-skeleton of the filtration. One way to restrict the size of a filtration is to restrict it to some particular skeleton. However, by doing so we loose the information about possible higher dimensional features in the persistence diagram of the filtration. Also, in practice restricting to k-skeleton is only tractable for values of k up to 4 or 5.

Therefore for higher dimensional simplicial complexes (Rips, Čech, alpha) the problem of size persists. The large size of these filtrations not only slows down the actual persistence computation, but it also induces large computation time to set-up the boundary matrix which we need to reduce to compute the persistence diagram. This thesis addresses this problem in a novel way and provides a solution which is a quite significant step forward.

Previous Work. Much progress has been accomplished in recent years along several directions. Regarding PH computation itself, a number of clever implementations and optimizations have led to a new generation of software [START_REF]Gudhi: Geometry understanding in higher dimensions[END_REF][START_REF] Bauer | PHAT -persistent homology algorithms toolbox[END_REF][START_REF] Bauer | Ripser[END_REF][START_REF] Mozozov | Dionysus[END_REF]. Gudhi [START_REF]Gudhi: Geometry understanding in higher dimensions[END_REF] and Phat [START_REF] Bauer | PHAT -persistent homology algorithms toolbox[END_REF] compute PH for any filtrations whereas Ripser [START_REF] Bauer | Ripser[END_REF] specializes in Rips filtration. Dionysus [START_REF] Mozozov | Dionysus[END_REF] is designed to compute the persistence diagram of a zigzag filtration.

One of the first significant optimization technique was developed in [START_REF] Bauer | Clear and compress: Computing persistent homology in chunks[END_REF]. The notion of persistent cohomology was introduced in [START_REF] Vin De Silva | Persistent cohomology and circular coordinates[END_REF]. Gudhi and Dionysus use the dual algorithm (computes persistent cohomology) to compute persistence diagrams which is substantially faster than the standard algorithm (persistent homology). In all the above mentioned technique the goal was to make the reduction of the boundary matrix faster.

A second way to improve the overall process is to reduce the size of the complexes in the input sequence while preserving (or approximating in a controlled way) the persistent homology of the sequence.

The first approximation scheme for filtrations was given by Hudson et. al in [START_REF] Hudson | Topological inference via meshing[END_REF]. Sheehy gave the first approximation scheme for Rips filtrations [START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF]. In a metric space, for a given ∈ (0, 1), they construct a (1 + )-approximate filtration of the Rips filtrations. The size of the k-skeleton of the approximate filtraion is n( 1)O(λk), where λ is the doubling dimension of the metric. The work of Sheehy [START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF] has two significant new features, 1. the approximation factor is an input parameter of the scheme, 2. the size of the approximate filtration depends on the dimension of the skeleton.

Dey et. al gave a similar approximation scheme for the Rips filtrations [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF]. Their method used vertex collapses based on geometric proximity and they reduce a filtration to an approximate simplicial tower. The scheme was further improved in [START_REF] Dey | SimBa: An efficient tool for approximating Ripsfiltration persistence via Simplicial Batch-collapse[END_REF], leading to a significantly better performance in practice compare to [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF] and [START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF].

Several other algorithms with theoretical guarantees have been proposed recently using a variety of similar ideas and techniques, e.g. interleaving smaller and easily computable simplicial complexes, or sub-sampling the point sample [START_REF] Chazal | Towards persistence-based reconstruction in Euclidean spaces[END_REF][START_REF] Botnan | Approximating persistent homology in euclidean space through collapses[END_REF][START_REF] Kerber | Approximate Čech complex in low and high dimensions[END_REF][START_REF] Choudhary | Polynomial-Sized Topological Approximations Using The Permutahedron[END_REF]. The work reported in [START_REF] Kerber | Approximate Čech complex in low and high dimensions[END_REF][START_REF] Choudhary | Polynomial-Sized Topological Approximations Using The Permutahedron[END_REF] approximates a Čech filtrations using geometric techniques. The work of Botnan and Spreemann [START_REF] Botnan | Approximating persistent homology in euclidean space through collapses[END_REF] approximates a Čech filtration using collapses derived using geometric criterion. Chazal and Oudot [START_REF] Chazal | Towards persistence-based reconstruction in Euclidean spaces[END_REF] use interleaving of the Rips complex and the Witness complex with the Čech complex to approximate the persistence of a Čech filtration.

The above approximation methods are based on geometric techniques. There are reduction methods based on topological notions. Examples of exact reductions can be found in the work of Mischaikow and Nanda [START_REF] Mischaikow | Morse theory for filtrations and efficient computation of persistent homology[END_REF] who use Morse theory to reduce the size of a filtration. The work of Maria and Schreiber [START_REF] Maria | Algorithms and data structures -16th international symposium[END_REF] extends the work of Mischaikow and Nanda [START_REF] Mischaikow | Morse theory for filtrations and efficient computation of persistent homology[END_REF] to zigzag filtrations. Similar to the work of Mischaikow and Nanda [START_REF] Mischaikow | Morse theory for filtrations and efficient computation of persistent homology[END_REF], the work of Dłotko and Wagner use simple collapses [START_REF] Dłotko | Simplification of complexes for persistent homology computations[END_REF]. These methods preserve the filtration nature of the output sequence, i.e. a filtration is reduced to a filtration and a zigzag filtration is reduced to a zigzag filtration. The above schemes [START_REF] Mischaikow | Morse theory for filtrations and efficient computation of persistent homology[END_REF][START_REF] Dłotko | Simplification of complexes for persistent homology computations[END_REF][START_REF] Maria | Algorithms and data structures -16th international symposium[END_REF] do not provide theoretical guarantees over the output size of the filtration as it is NP-Complete to compute optimal Morse-matching or a smallest 'simple'-core.

Recently Dey and Slechta [START_REF] Dey | Filtration simplification for persistent homology via edge contraction[END_REF] have used the notion of Edge contraction (different than the Edge collapses introduced in this thesis) that involves contracting edges that satisfy so called link condition to simplify a filtration. Their method is approximate for general simplicial complexes and exact when the underlying space of the simplicial complex is a 2-manifold.

Our Contribution

As described in the previous section the problem of efficient computation of persistent homology is the central topic of research since its introduction. Motivated by this problem, in this thesis, we introduce two new approaches (corresponding to two types of collapses) to compute the PH of a given sequence of simplicial complexes (filtration, tower, zigzag sequence) in an efficient way. Both approaches are closely related and are as follows, 1. We use the notion of strong collapse introduced by J. Barmak and E. Minian [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF] to simplify the complexes of the input sequence.

2. Instead of strong collapses, we use the so-called edge collapses. In fact, we more generally define k-collapses. When k = 0, we have strong collapses and when k = 1 edge collapses and we use edge collapse to simplify a filtration.

Both of our approaches are pre-processing methods and they are applied even before the boundary matrix is computed. In the case of general simplicial complexes our collapse strategy requires only the maximal faces of the simplicial complexes. And In the case of Flag complex both of them work on the 1-skeleton and this is the most powerful aspect of our approach. Therefore the collapses of the simplicial complexes are fast and memory efficient. Once we have a smaller sequence of simplicial complex we proceed normally by setting up the boundary matrix and then its reduction.

Numerous experiments show that both approaches outperform previous methods. Edge collapse performs better than strong (vertex) collapse. However, vertex and edge collapses can be applied together one after another. Also as both vertex and edge collapses are pre-processing methods they can be combined with any other pre-processing method and any PH computation software.

Strong Collapse Approach.

We use the notion of strong collapse as introduced by Barmak and Minian [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF] to reduce a sequence of simplicial complexes. Specifically, our 1st approach can be summarized as follows. Given a sequence

Z : {K 1 f 1 -→ K 2 g 2 ← -K 3 f 3 -→ • • • f (n-1) ---→ K n } of simplicial complexes K i connected through simplicial maps { f i -→ or g j ← -}.
We independently strong collapse the complexes of the sequence to reach a sequence

Z c : {K c 1 f c 1 -→ K c 2 g c 2 ← -K c 3 f c 3 -→ • • • f c (n-1) ---→ K c n }, with induced simplicial maps { f c i -→ or g c j
← -} (defined precisely in Chapter 3). The complex K c i is called the core of the complex K i and we call the sequence Z c the core sequence of Z. We show that one can compute the PH of the sequence Z by computing the PH of the core sequence Z c , which is usually of much smaller size.

Our approach has some similarity with the work of Wilkerson et. al. [START_REF] Wilkerson | Computing persistent features in big data: A distributed dimension reduction approach[END_REF][START_REF] Wilkerson | Simplifying the homology of networks via strong collapses[END_REF] who also use strong collapses to reduce the PH computation but it differs in three essential aspects: it is not limited to filtrations (i.e. sequences of nested simplicial subcomplexes) but works for other types of sequences like towers and zigzags. It also differs in the way strong collapses are computed and in the manner PH is computed.

General simplicial complexes.

A first central observation is that to strong collapse a simplicial complex K, we only need to store its maximal simplices (i.e. those simplices that have no coface). The number m of maximal simplices is smaller than the total number of simplices by a factor that is exponential in the dimension d of the complex and m is linear in the number n v of vertices for a variety of complexes [START_REF] Boissonnat | An efficient representation for filtrations of simplicial complexes[END_REF]. Working only with maximal simplices dramatically reduces the time and space complexities compared to the algorithm of [START_REF] Wilkerson | Simplifying the homology of networks via strong collapses[END_REF]. We prove that the complexity of our algorithm is O(n 2 v dΓ 2 0 ). Here Γ 0 is the largest number of maximal simplices incident to a vertex. As observed in [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF][START_REF] Boissonnat | An efficient representation for filtrations of simplicial complexes[END_REF], Γ 0 is usually small and appears to be almost constant along a filtration (see Section 3.5 for a discussion). As a consequence, the time to collapse the i-th simplicial complex K i in the sequence is almost independent of i, which is a clear advantage over methods that use a full representation of the complexes and suffer an increasing cost as i increases.

Once a reduced sequence has been computed as described above, we cannot compute its PH directly. Indeed, all PH algorithms require as input a full representation of the complexes. We thus have to convert the representation by maximal simplices used to efficiently perform the strong collapses into a full representation of the complexes. This takes time exponential in the dimension (of the collapsed complexes). However, this exponential burden is to be expected since it is known that computing PH is NPhard when the complexes are represented by their maximal faces [START_REF] Adamaszek | Complexity of simplicial homology and independence complexes of chordal graphs[END_REF]. Nevertheless, we demonstrate in Chapter 3 that strong collapses combined with known persistence algorithms lead to major improvements over previous methods to compute the PH of a sequence.

The major advantages of our approach are:

-The collapses of the complexes in the sequence can be performed independently and in parallel. This is due to the fact that strong collapses can be expressed as simplicial maps, unlike simple collapses [START_REF] Whitehead | Simplicial spaces nuclei and m-groups[END_REF].

-Instead of computing the exact PH, we can compute an approximate PH which is substantially faster at a very minimal cost. The approximation scheme is detailed in Sections 3.5.

Flag complex.

Most of the previous methods described in Section 1.4 are for general simplicial complexes except [START_REF] Bauer | Ripser[END_REF][START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF] which focus on the Rips complex, an example of a flag complex. In Chapter 4, we show that further decisive progress can be obtained if one restricts the family of simplicial complexes to flag complexes.

In the case of a Rips complex, the maximal simplices are the maximal cliques of the 1-skeleton of the complex and their computational time can be very large (exponential in the dimension of the complex). As a result, a naive application of our method would devote most of the time to compute the maximal faces of the complexes prior to their strong collapse. We show that we can avoid computing maximal cliques and we can strong collapse any flag complex using only the 1-skeleton or graph of the complex. The strong collapses of a flag complex can be computed in time O(n 2 v k 2 ) where n v is the number of vertices of the complex and k the maximal degree of its graph. Another crucial observation is that the reduced complex obtained by strong collapsing a flag complex is itself a flag complex.

Furthermore, if we consider a flag tower, i.e. flag complexes connected by simplicial maps, the obtained core sequence is also a flag tower. In the general case where the core sequence is not a filtration (which usually happens even if the original sequence is a filtration), we need to convert the flag tower to an equivalent filtration to compute its PH using known algorithms. To do so, we build on the work of [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF][START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF] again by restricting ourselves to flag complexes. This allows us to convert a flag tower to an equivalent flag filtration using again only the 1-skeleton.

The figure shows the flow diagram of our method when restricted to a flag filtration.

Filtration

(Flag)

Tower (Flag) Filtration (Flag)
Further advantages of our approach for flag complexes are:

-We can compute PH for large complexes of high dimensions as we don't need to compute the maximal simplices.

-The dimension of the original sequence is in fact irrelevant and what matters is the dimension of the core sequence, which is usually quite small.

Edge Collapse Approach.

We extend the notion of strong collapse to edge collapse. Edge collapses appear to be very powerful, specially in the context of flag complexes. Keeping the same general philosophy we further improve on our approach using strong collapse by using edge collapse. We again use edge collapse to simplify a flag filtration F to another smaller flag filtration F c with the same persistence.

The figure shows the flow diagram of our method using the edge collapse when applied to a flag filtration.

Filtration (Flag) Filtration (Flag)
Our method with edge collapse or in fact more general simple collapse works for all kind of simplicial complexes. However we focus on the case of flag complexes as the reduction in this case can be performed using only the 1-skeletons of the complexes.

The approach with edge collapse has some new key features that makes it several orders of magnitude more efficient than all known methods including our strong collapse approach.

1. Edge collapses share some important properties with strong collapses. Most notably, we can use edge collapses to reduce flag filtrations F to smaller flag filtrations F c with the same persistence, using only the 1-skeletons of the complexes.

2. The reduction is exact and the PH of the reduced sequence is identical to the PH of the input sequence. Our algorithm thus computes the exact PH as does [START_REF] Bauer | Ripser[END_REF] but differs from [START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF] where provably good approximations were computed. However, our algorithm using edge collapse can easily be adapted to compute approximate PH as well with larger gain in the computation time.

3. In the strong collapse approach, the reduced sequence associated to a filtration is usually a tower and part of the computing time was devoted to transforming this tower in another equivalent filtration. There is no such need in the algorithm using edge collapse, which is another main source of improvement.

4. The resulting method is simple and extremely efficient. On the theory side, we show that the edge collapse of a flag filtration can be computed in time O(n n c k 2 ), where n and n c are the number of edges in the input and output 1-skeletons respectively and k is the maximal degree of a vertex in the input graph.

Outline

An outline of this thesis is as follows.

-In Chapter 2, we review the basic ideas and constructions related to topology, simplicial complexes, simple and strong collapses, homology, persistent homology. For more details on the topics of persistent homology readers can refer to [START_REF] Edelsbrunner | Computational Topology: An Introduction[END_REF] , for Algebraic topology to [START_REF] Hatcher | Algebraic Topology[END_REF], for strong collapse to [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF].

-In Chapter 3, we provide an algorithm to strong collapse a general simplicial complex.

We then prove that strong collapse of a sequence of simplicial complexes preserves its persistence. We provide a scheme to approximate a Rips filtration and then we perform some experiments to show case the efficiency or our approach.

-In Chapter 4, we restrict our attention to flag complexes and build upon the work of Chapter 3. We show that the core of a flag complex is a flag complex and we can compute the core skeleton of a flag complex using only its 1-skeleton. The time complexity of the algorithm is O(n 2 v k 2 ) where n v is the number of vertices of the complex and k the maximal degree of its graph. This is a major improvement over using maximal simplices. Then we use the same scheme as in Chapter 3 to compute the core sequence of a filtration which is usually a flag tower. We further build on the work of [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF][START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF] and provide an algorithm to convert a flag tower to an equivalent flag filtration using again only the 1-skeleton. We end with some experiments. The experiments show that the gain is tremendous when we work only with the 1-skeleton.

-In Chapter 5, we more generally define k-collapses that are identical to the extended collapses introduced in [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF]. When k = 0, we have strong collapses and when k = 1 edge collapses and we use edge collapse to simplify a filtration. We show that edge collapse of a flag complex is also a flag complex. A complex with no possibilities of further edge collapse is called a 1-core. We show that, we can compute 1-core of a flag complex using only its skeleton. Furthermore, we show that a simplicial complex may have several 1-cores.

We then prove that simple collapse preserves the PH of a sequence of simplicial complex2 . We then use edge collapse to simplify a flag filtration to another flag filtration again using only 1-skeleton. We provide some experiments and show that edge collapse outperforms even strong collapse and works on more general point set that strong collapse.

Chapter 2

Basic Notions

In this chapter, we briefly review some of the basic concepts of Topology, notions like simplicial complex, homotopy equivalence, different notions of collapses, homology groups, persistent homology. Readers can refer to [START_REF] Hatcher | Algebraic Topology[END_REF][START_REF] Edelsbrunner | Computational Topology: An Introduction[END_REF][START_REF] Munkres | Elements of Algebraic Topology[END_REF] for a comprehensive introduction of these topics.

In Section 2.1, we provide definitions of a topological space, continuous maps and define the notions of topological equivalences like homeomorphism and homotopic equivalence. In Section 2.2, notions of simplicial complex, simplicial maps and examples of commonly used simplicial complexes are discussed. In Section 2.3 we introduce the notion of simple collapses. Different notions of homology groups are defined in Section 2.4. We provide more details about Persistent Homology along with the matrix reduction algorithm in Section 2.5.

Topology

Topology is the branch of mathematics which studies the properties a space X under continuous deformation. More specifically it characterizes invariants that do not change when we deform the space continuously.

Topological Space Definition 2.1.1.

A topological space is an ordered pair (X, U ), where X is a set and U is a collection of subsets of X, satisfying the following axioms:

1. The empty set ∅ and X itself belong to U .

2. Any arbitrary (finite or infinite) union of members of U is in U as well.

3. The intersection of any finite number of members of U still belongs to U .

The elements of U are called open sets and the collection

U is called a topology on X. A subset A of X is called closed if X \ A is an open set.
Examples:

1. Given X = {a, b, c, d}, the collection U = {∅, {a, b, c, d}} of only the two subsets of X forms a topology of X, called the trivial topology (indiscrete topology) on X.

2. Given X = {a, b, c, d}, the collection U = P (X) (the power set of X), (X, U ) is a topological space. U is called the discrete topology on X. A subset A ⊆ X is called a subspace of (X, U ) if A ∩ U is a topology on A, we call this an induced topology on A. For brevity we will write a topological space (X, U ), as X assuming some well defined topology U on X. We will also refer a topological space X by simply space unless it means something else.

Standard topology on R

d : The set of points B(c, ) := {x ∈ R d | ||x -c|| ≤ } is called a d-ball in R d ,
The notion of open sets is an abstraction of the concept of closeness (distance) on a metric space and that in turn facilitates a more abstract definition of continuous maps.

Definition 2.1.2. A map f : X → Y between two topological spaces is called continuous if for every open set V in Y the inverse f -1 (V) is an open set in X.
This definition of continuous map is then further used to define different notions of equivalence between two topological spaces.

Topological Equivalences

The most fundamental and strict form of equivalence between two topological spaces is called homeomorphism, which we define as follow.

Definition 2.1.3. A continuous map f : X → Y between two topological spaces is a homeomorphism if it has the following properties:

1 . f is a bijection (one-to-one and onto), i.e. there exist an inverse f -1 : Y → X.

The inverse map f

-1 is continuous.
If such a map exists, X and Y are called homeomorphic. Being homeomorphic is an equivalence relation on topological spaces.

Topology is precisely the study of properties of a topological space X which are preserved under homeomorphisms. Very often the topological spaces we consider are geometric objects, such as disks, sphere, R d etc. Some properties that are preserved under homeomorphism are connectedness, dimension, number of holes/cavities... Homeomorphism is a very strong notion of equivalence and when two spaces are homeomorphic they are topologically the same. However it is not an easy task to prove that two spaces are homoemorphic. This difficulty leads to a relatively relaxed notion of equivalence between topological spaces called homotopy equivalence. Definition 2.1.4. Let f and g be two continuous maps from a space X to a space Y. A homotopy between f and g is defined to be a continuous function H : X × [0, 1] → Y from the product of the space X with the unit interval [0, 1] to Y such that H(x, 0) = f (x) and H(x, 1) = g(x) for all x ∈ X.

Intuitively H describes a continuous deformation of f into g. If such an H exists then f and g are said to be homotopic. Definition 2.1.5. Two spaces X and Y are called homotopy equivalent, if there exist continuous maps f : X → Y and g : Y → X such that g • f is homotopic to the identity map id X and f • g is homotopic to id Y .

We call the maps f and g homotopy equivalences. Every homeomorphism is a homotopy equivalence, but the converse is not true. For example, a solid disk and a single point are homotopy equivalent however, the disk is not homeomorphic to the point. Next we look into a special type of homotopy equivalence called deformation retraction.

Definition 2.1.6. Let X be a topological space and A a subspace of X. Then a continuous map r : X → A is a retraction if the restriction of r to A is the identity map on A; that is, r(a) = a for all a in A.

Definition 2.1.7. A continuous map F : X × [0, 1] → X is a deformation retraction of a space X onto a subspace A if, for every x ∈ X and a ∈ A, 1. F(x, 0) = x 2. F(x, 1) ∈ A 3. F(a, 1) = a.
Equivalently, a deformation retraction is a homotopy between a retraction and the identity map on X. The subspace A is called a deformation retract of X. As stated before a deformation retraction is a special case of a homotopy equivalence.

If a deformation retraction does not move the points in A throughout the homotopy then F is called a strong deformation retraction, that is we add an additional (4th) condition of F(a, t) = a for all t ∈ [0, 1] and a ∈ A. Definition 2.1.8. A space is said to be contractible, if it is homotopy equivalent to a point.

Simplicial complex

In this section, we will introduce the concept of simplicial complexes which are of utmost importance in computational topology. We begin with the geometric notion of simplicial complex. However later we will primarily work with the abstract simplicial complexes.

Geometric simplicial complex

Definition 2.2.1. A geometric k-simplex σ is the convex hull of any k + 1 affinely inde- pendent points {v 0 , v 1 , ...v k } in R d .
Here k is called the dimension of σ and v i s are its vertices. For example, 0-simplex is a point, a 1-simplex is an edge, a 2-simplex is a triangle and a 3-simplex is a tetrahedron and so on and so forth. Since {v 0 , v 1 , ...v k } are affinely independent any smaller subset of vertices are also affinely independent, the convex hull τ of a subset of the set {v 0 , v 1 , ...v k } is then called a face of σ and σ is called a coface of τ. Definition 2.2.2. A geometric simplicial complex K is a set of geometric simplices that satisfies the following conditions:

1. Every face τ of a simplex σ ∈ K is also in K.

2. The non-empty intersection of any two simplices σ 1 , σ 2 ∈ K, is a face of both σ 1 and σ 2 .

Informally, a geometric simplicial complex is a set of simplices that are glued nicely, i.e. they only intersect each other at common faces.

Since K is a subset of R d any well defined topology on R d can easily be induced on K. When we consider K as a topological space, we will assume that the induced topology is the standard topology unless otherwise stated.

Abstract simplicial complex

Definition 2.2.3. An abstract simplicial complex K is a collection of subsets of a nonempty finite set X, such that for every subset A in K, all the subsets of A are in K.

An element of K is called a simplex (abstract). An element of cardinality k + 1 is called a k-simplex and k is called its dimension. A simplex is called maximal if it is not a proper subset of any other simplex in K. A sub-collection L of K is called a subcomplex, if it is a simplicial complex itself. L is a full subcomplex if it
contains all the simplices of K that are spanned by the vertices (0-simplices) of the subcomplex L.

The abstract simplicial complexes are purely combinatorial objects. However, any abstract simplicial complex K can be realised as a geometric simplicial complex in R d if d is sufficiently large. This can be easily seen through embedding a single abstract k-simplex σ in R k . We can always choose k + 1 affinely independent points in R k , mapping the vertices of σ to these k + 1 points we embed σ geometrically in R k , denoted as |σ|. A consistent choice of such points for all simplices in the abstract simplicial complex K will provide a geometric realisation of K in R d for some d. The geometric realisation K will be denoted as |K|. |K| itself is a geometric simplicial complex and can have the induced standard topology.

From now on we will call an abstract simplicial complex simply a simplicial complex or just a complex.

Examples of simplicial complexes

Now we will introduce some commonly used simplicial complexes.

Čech complex : Let P be a set of finite points in R d and B(P, ) := {B(c, )| c ∈ P} be the set of d-balls of some non-negative radius whose centers c are in P. The set of all non-empty intersections of such balls is an abstract simplicial complex and is called Čech complex, denoted as C(P, ).

Vietoris-Rips (VR) complex : Let σ ⊆ P be a subset of points in P such that any two points p, q in σ is at most 2 far apart, that ||p -q|| ≤ 2 . The collection of all such subsets of P defines a simplicial complex called the Vietoris-Rips (VR) complex of the point set P at distance (scale) 2 , denoted as R(P, ). Vietoris-Rips (VR) complexes are often called simply Rips complexes. It is not hard to see that the Čech complex C(P, ) is a subcomplex of the Rips complex R(P, ). In fact, they satisfy more stronger inclusion property,

R(P, ) ⊆ C(P, √ 2 ) ⊆ R(P, √ 2 )
and are called interleaved.

When the point set P is clear from the context, for parameter(radius) , we will denote the Čech complex as C and the Rips complex as R .

Star, Link and Simplicial Cone

Definition 2.2.4. Let σ be a simplex of a simplicial complex K, the closed star of σ in K, st K (σ) is a subcomplex of K which is defined as follows,

st K (σ) := {τ ∈ K| τ ∪ σ ∈ K}.
Definition 2.2.5. The link of σ in K, lk K (σ) is defined as the set of simplices in st K (σ) which do not intersect with σ,

lk K (σ) := {τ ∈ st K (σ)|τ ∩ σ = ∅}.
The open star of σ in K, st o K (σ) is defined as the set st K (σ) \ lk K (σ). It is not a subcomplex of K.

Let L be a simplicial complex and a a vertex not in L. Then the simplicial cone aL is defined as

aL := {a, τ | τ ∈ L or τ = σ ∪ a;
where σ ∈ L}.

Flag complex and Neighborhood

Definition 2.2.6. A complex K is a flag complex if, when a subset of its vertices has pairwise edges (1-simplices) between them, they span a simplex of K.

It follows that the full structure of K is determined by its 1-skeleton (or graph) we denote by G. The above defined Rips complex is an example of a flag complex.

For a vertex v in G, the open neighborhood N G (v) of v in G is defined as N G (v) := {u ∈ G | [uv] ∈ E}, here E is the set of edges of G. The closed neighborhood N G [v] is N G [v] := N G (v) ∪ {v}.

Similarly we define the closed and open neighborhood of an edge [xy] ∈ G, N G [xy]

and N G (xy) respectively as

N G [xy] := N[x] ∩ N[y]
and

N G (xy) := N(x) ∩ N(y).
The above definitions can be extended to any k-clique

(k-simplex of K) σ = [v 1 , v 2 , ..., v k ] of G; N G [σ] := v i ∈σ N[v i ] and N G (σ) := v i ∈σ N(v i ).

Simplicial maps

Definition 2.2.7. A vertex to vertex map ψ : K → L between two simplicial complexes is called a simplicial map, if it always maps a simplex in K to a simplex in L.

Since simplicial maps are determined by the images of the vertices they are finitely many.

A simplicial map ψ : K → L between two simplicial complexes K and L induces a continuous map |ψ| : |K| → |L| between the underlying geometric realizations.

Any general simplicial map can be decomposed into more elementary simplicial maps, namely elementary inclusions (i.e., inclusions of a single simplex) and elementary contractions {{u, v} → u} (where a vertex is mapped onto another vertex). The inverse operation of inclusion is called simplicial removal denoted as K ← L, where L is a subcomplex of K.

Here are examples of an elementary inclusion and an elementary contraction.

1. Elementary inclusion: inclusion of a single simplex (the solid triangle)

K 1 ∪σ -→ K 2 .
2. Elementary contraction: mapping a vertex v to another vertex u K

1 {u,v} →u -----→ K 2 . v u x y u x y Definition 2.2.8. Two simplicial maps φ : K → L and ψ : K → L are contiguous if, for all σ ∈ K, φ(σ) ∪ ψ(σ) ∈ L. v 1 v 2 v 3 ψ:v 1 →w 1 ;{v 2 ,v 3 } →w 2 ------------→ φ:{v 1 ,v 2 ,v 3 } →w 1 w 1 w 2 FIGURE 2.
2 -Maps φ and ψ are contiguous.

We denote two contiguous maps as φ ∼ c ψ. Two contiguous maps are known to be homotopic [START_REF] Munkres | Elements of Algebraic Topology[END_REF]Theorem 12.5]. Two maps φ 1 and φ 2 are in the same contiguity class if there exists a sequence of simplicial maps φ 1 = ψ 0 , ψ 1 , ..., ψ k = φ 2 such that the consecutive maps ψ i and ψ i+1 are contiguous for all i = 0...k. We denote two maps in the same contiguity class as φ 1 ∼ φ 2 . Two maps in the same contiguity class are homotopic.

Collapses and Edge Contraction

In this section, we will review some of the basic notion of simplicial collapses. Collapses are combinatorial analog of deformation retractions defined in section 2.1.

Simple Collapse

Simple collapse is the most fundamental type of collapse. The notion of simple collapse was introduced by J.H.C. Whitehead in the late 1930s [START_REF] Whitehead | Simplicial spaces nuclei and m-groups[END_REF].

Definition 2.3.1. Given a complex K, a simplex σ ∈ K is called a free simplex if σ has a unique coface τ ∈ K.

The pair {σ, τ} is called a free pair.

Definition 2.3.2. The action of removing a free pair: K → K \ {σ, τ} is called an elementary simple collapse.

A series of such elementary simple collapses is called a simple collapse. We denote it as K L. This operation preserves the homotopy type of the simplicial complex K, which we write K ∼ L. In particular, there is a retraction map |r| : |K| → |L| between the underlying geometric realization of K and L and there is a strong deformation retraction between |r| and the identity over |L|. The inverse operation of (elementary) simple collapse is called an (elementary) simple expansion. Two complexes K and L are said to be simple homotopic, if there exists a series of elementary simple collapses and/or expansions between them. A complex K will be called simply-minimal if there is no free pair {σ, τ} in K . A subcomplex K ec of K is called an elementary core of K if K K ec and K ec is simplyminimal. The elementary cores are not unique and they depend on the order of removals of free pairs. Definition 2.3.3. A complex K is said to be simply collapsible or collapsible, if it simply collapses to a vertex.

Edge Contraction

Related to the notion of collapses there is a notion called Edge contraction introduced by Dey et. al. in [START_REF] Dey | Topology preserving edge contraction[END_REF], which is a contraction of special edges that satisfies so called link condition defined below. The contraction operation merges the two vertices u, v to a single vertex either u or v. Given an edge [u, v] ∈ K that satisfies the link condition, the associated retraction map r [u,v] preserves the homotopy type of the complex K. satisfies the link condition. The complex (in the right) which is the image of an edge contraction may not be a subcomplex of the original complex K. As the triangle [p, q, u] doesn't exist in K.

Definition 2.3.4. An edge [u, v] in a complex K is said to satisfy the link condition if ln K ([u, v]) = ln K (u) ∩ ln K (v).

Homology Groups

Intuitively Homology groups capture the number of connected components, number of holes, number of cavities and higher dimensional equivalents of a space. We associate a family of groups, one per dimension to a topological space. The homology groups are topological invariants in the sense, that two homotopic spaces have the isomorphic homology groups. There are many different types of homology theories, in this section we will focus on simplicial homology and briefly talk about singular homology.

Simplicial Homology

Let K be a simplicial complex and G be any abelian group. We start with defining orientation of the simplices in the complex K by fixing an order on the vertices of the complex

K. A k-simplex σ with vertices {v 0 , v 1 , • • • , v k } will be denoted as an ordered set σ = [v 0 , v 1 , • • • , v k ].
A face τ of σ will inherit the order of the vertices from σ.

A (k -1) face of σ = [v 0 , v 1 , • • • , v k ] obtained by removing the vertex v i from σ will be denoted as [v 0 , • • • , vi , • • • , v k ].
Definition 2.4.1. For any non-negative integer p, the p-th chain group C(K, G, p), is the free abelian group defined using the p-simplices of K as basis and the elements of G as coefficients.

Therefore, any element c ∈ C(K, G, p) can be written as the formal sum

∑ α g α σ α
Where g α ∈ G and σ α is a p-simplex. c is called a p-chain. The summation ⊕ operation in C(K, G, p) is defined component-wise (at each basis element) using the summation operation of G. For a fixed K and G we will write C(K, G, p) as C p .

We define a boundary homomorphism between two consecutive chain groups C p

∂ p -→ C p-1 by specifying them on each p-simplex σ α = [v 0 , v 1 , • • • , v p ]. Definition 2.4.2 (boundary homomorphism). ∂ p (σ α ) = ∑ i (-1) i [v 0 , • • • , vi , • • • v p ]
Apart from being a homomorphism, ∂ p satisfies the following property (Lemma 2.4.1).

Lemma 2.4.1. ∂ p-1 (∂ p (σ α )) = 0.
Proof. The proof follows directly from the definition.

We can link all the chain groups C p s through the boundary homomorphisms ∂ p and we get the following sequence of abelian groups connected through homomorphisms,

• • • → C p+2 ∂ p+2 --→ C p+1 ∂ p+1 --→ C p ∂ p -→ C p-1 → • • • C 1 ∂ 1 -→ C 0 ∂ 0 -→ 0.
with the property ∂ p-1 ∂ p = 0. Such a sequence of chain groups linked by boundary homomorphisms is called a chain complex. Observe that the sequence has been extended by 0 at the end with a zero boundary map, ∂ 0 = 0. Definition 2.4.3. A p-chain c ∈ C p is called a p-boundary if for there exists a (p + 1)-chain γ ∈ C p+1 , the following is true,

∂ p+1 (γ) = c.
We denote the set of p-boundaries by B p = Im∂ p+1 := ∂ p+1 (C p+1 ). When we choose elements from a field F as coefficients instead of a group G to define the chain groups C p , that is C p = C(K, F, p), then the homology groups H p (K) are in fact vector spaces. This is a mere consequence of the fact that C(K, F, p) is itself a vector space. In computational topology, Z 2 (Z mod 2) is the most common used set of coefficients.

Definition 2.4.6. The p-th Betti number β p is defined as the rank of the p-th homology group, β p = rank(H p ).

The Betti numbers can be written as the difference between the rank of Z p and the rank of B p .

β p = rank(Z p ) -rank(B p ).
The definition of simplicial homology is purely combinatorial and algebraic. It does not use any topological structure of the simplicial complex. However, homology groups are topological invariants. Indeed, they are isomorphic for homeomorphic topological spaces and in fact they are isomorphic for homotopic spaces. The following lemma is the first fact that establishes the invariant nature of homology groups.

Lemma 2.4.2. Let f : K → L be a simplicial map between two simplicial complexes K and L. f induces a homomorphism between the corresponding homology groups of K and L, that is, there exists a map f * : H p (K) → H p (L), induced by f for all p.

Proof. We will provide a sketch of the proof. Using f we first define a homomorphism between the pth chain groups f # :

C p (K) → C p (L). For each p-simplex σ ∈ K, we define f # (σ) = f (σ) if dim( f (σ)) = p, and f # (σ) = 0 otherwise. Then, for c ∈ C p (K) c = ∑ α g α σ α f # (c) := ∑ α g α f (σ α )
f # satisfies the following property,

f # ∂ = ∂ f #
Where ∂ is the respective boundary homomorphisms of C p (L) and C p (K). The property f # ∂ = ∂ f # implies that f # takes cycles to cycles and boundaries to boundaries. Therefore, it induces a homomorphism f * : H p (K) → H p (L) on the corresponding homology groups as well.

The above defined map f # is called a chain map as it satisfies

f # ∂ = ∂ f # .

Singular Homology

Simplicial homology is one of the most traditional definition of homology, which is defined for simplicial complexes. However using the notion of singular simplices (defined later) it is possible to have a more general notion of homology that extends to any general topological spaces. A singular p-simplex in a topological space X is a continuous map

Let ∆ p = [v 0 , • • • , v p ] denote
σ o : ∆ p → X.
Using this basic definition of a singular simplex we can extend all the notions like chain complex, boundary maps, homology groups etc.

Definition 2.4.8. For any non-negative integer p, the singular p-th chain group C o (X, G, p), is the free abelian group defined using the singular p-simplices of X as basis and the elements of G as coefficients.

We will write C o p for C o (X, G, p) when X and G are clear from the context. We define the boundary homomorphism between two consecutive singular chain groups C o p and C o p-1 implicitly by the boundary homomorphism on the corresponding standard simplex. Below is the definition of a singular boundary homomorphism over a singular p-simplex which can be extended to any singular p-chain c

∈ C o p componentwise. Let σ o α |[v 0 , • • • , vi , • • • v p ] denotes the restriction of the map σ o α : ∆ p → X to the face [v 0 , • • • , vi , • • • v p ] of ∆ p .
Definition 2.4.9 (singular boundary homomorphism).

∂ o p (σ o α ) := ∑ α (-1) i σ o α |[v 0 , • • • , vi , • • • v p ].
∂ o p also follows the same properties of being a 'boundary' homomorphism, that is,

∂ o p-1 (∂ o p (σ o α )) = 0.
Therefore we can define the p-th singular homology H o p (X) = Ker∂ o p /Im∂ o p+1 . In the case of simplicial homology, a simplicial map between two simplicial complexes induces a homomorphism between their homology groups. we have the following analog for singular homology Lemma 2.4.3. If f : X → Y be a continuous map between two spaces X and Y, then f induces a homomorphism between the corresponding singular homology groups of X and Y. In other words, there exists a map f * :

H o p (X) → H o p (Y), induced by f for all p.
Using the above lemma and some of its consequences we have the following homotopy invariant property of singular homology groups.

Theorem 2.4.1. Let f : X → Y be a continuous map between two spaces X and Y such that f is a homotopy equivalence. Then f * :

H o p (X) → H o p (Y) is an isomorphism for all p.
With the definition of singular homology we can have a homology theory for any topological space. Furthermore, there is a remarkable fact that singular homology and simplicial homology of a simplicial complex K are isomorphic. The implicit consequence of the above theorem is that for any triangulated space X its simplicial homology does not depend on that particular triangulation. As a consequence of the above theorem and lemmas, we have the following homotopy invariant property of simplicial homology groups.

Theorem 2.4.3. Let f : K → L be a simplicial map between two simplicial complexes K and L such that

| f | : |K| → |L| is a homotopy equivalence. Then f * : H p (K) → H p (L) is an isomorphism for all p.
The simplicial chain group of a finite simplicial complex is finitely generated since it has finitely many simplices and therefore a finite basis. However even for a compact ('finite') space X there is an infinite number of continuous maps from ∆ p to X and therefore an infinite number of singular p-simplices. This implies that a singular p-th chain group is infinitely generated. The definition of singular homology is more widely applicable and mathematically more powerful, however due to the infinite number of singular simplices, it is computationally intractable. Therefore for all practical purposes we use simplicial homology as our main tool.

Persistent Homology

Persistent Homology (PH) is a new child of the traditional homology theories, a dynamic variant. Imagine a topological space, for example, a simplicial complex which is evolving with time (e.g. growing with inclusion of more simplices) and you want to keep track of the evolution using homological measurements. Persistent homology is precisely a tool for such a measurement. The advent of Persitent homology was to understand the topology of data, usually represented as a point cloud P in some euclidean space R d . The underlying assumption is that the point cloud P is a finite sample of some topological space X. The goal of persistent homology is then to infer the topological (more specifically homological) information of X through P. Now since P is just a finite sample of X, we can not get the true homological information of X by computing the homology groups of P. One way to solve this problem and approximate the space X would be to inflate the points in P as solid d-balls of some radius . And if we choose the right parameter the union of balls P := p∈P B(p, )

will be a 'good' cover of X and then we compute the homology group of P . However there are two problems associated with this approach, the first problem is how to choose the right parameter and the second and more fundamental problem is that there might not be a single parameter providing the right homology. Persistent homology solves both of these problems, by computing homology at multiple scales and provides information about the many 'right' scales that correspond to some topological feature of the data. Mathematically, there are several different ways to characterize the evolution of a space. We will start with the simplest version of it, which is called a filtration.

Sequences of complexes

Definition 2.5.1. A filtration F is a sequence of nested simplicial complexes

F : K 1 ⊆ K 2 ⊆ • • • ⊆ K m .
A filtration could also be defined as a function f : K → R over the final simplicial complex K = K m . Where f assigns a real value to each simplex σ in K such that if τ ⊆ σ is a face of σ then f (τ) ≤ f (σ).

The most natural example of a filtration is a filtration coming out of the union of balls P and the Čech complex C is precisely the desired simplicial complex. For increasing values of > 0, the Čech complexes {C } 0≤ forms a filtration. Also, the Rips complexes {R } 0≤ with increasing scale parameter forms a filtration. Illustration of a filtration, Figure 2.6. Filtrations can be further generalized to a tower.

Definition 2.5.2. A sequence of simplicial complexes

T : K 1 f 1 -→ K 2 f 2 -→ K 3 f 3 -→ • • • f (m-1) ---→ K m .
connected through simplicial maps f i is called a simplicial tower or simply a tower.

This could be even further generalized to a zigzag sequence.

Definition 2.5.3. A sequence of simplicial complexes

Z : K 1 f 1 -→ K 2 g 2 ← -K 3 f 3 -→ • • • f (m-1) ---→ K m .
connected through simplicial maps f i and g i s in both directions is called a zigzag sequence.

When the maps f i and g i are inclusions, a zigzag sequence is called zigzag filtration.

A tower is then a special case of zigzag sequence, when the simplicial maps are only in one direction and a filtration is a special case of tower where the simplicial maps are only inclusions.

Persistent homology.

Although Persistent homology could be defined for zigzag sequences, we will restrict our exposition mostly to towers and filtrations.

If we compute the homology classes of all the K i with coefficients from a field F, we get the sequence

P (T ) : H p (K 1 ) f * 1 -→ H p (K 2 ) f * 2 -→ H p (K 3 ) f * 3 -→ • • • f * (m-1) ---→ H p (K m ).
Here f * i is the homomorphism induced from f i . P (T ) is a sequence of vector spaces connected through the homomorphisms f * i and is called a persistence module. More formally, a persistence module V is a sequence of vector spaces {V 1 -→

V 2 -→ V 3 -→ • • • -→ V m } connected
I[2, 4] : {0 0 -→ F I -→ F I -→ F 0 -→ 0 0 -→ 0}, here n = 6.
The following theorem states that any persistence module can be decomposed into a collection of intervals of the form [i, j] [START_REF] Carlsson | Zigzag persistence[END_REF][START_REF] Zomorodian | Computing persistent homology[END_REF].

Theorem 2.5.1. Any persistence module V is isomorphic to a direct sum of interval modules,

P (T ) ∼ = I[i, j]
The multiset of all the intervals [i, j] in this decomposition is called the persistence diagram of the persistence module. An interval of the form [i, j] in the persistence diagram of P (T ) corresponds to a homological feature (a 'cycle' of dimension p ) which is born at i and died at j.

Computing Persistence Diagram

In this subsection, we will discuss an algorithm to compute the persistence diagram of a persistence module induced by a filtration function f on a complex K with coefficients Z 2 .

Let {σ 1 , σ 2 , • • • , σ m } = K be the set of ordered (by filtration value) simplices of K.

Notice that as we move in increasing order of simplices, each simplex either creates a homological feature ('cycle') or destroys one. The simplex which creates a cycle is called a positive simplex and the one which destroys a cycle is called negative simplex. Therefore, an algorithm which computes the persistence diagram of a filtered simplicial complex K should essentially compute the pairings [positive, negative] of simplices corresponding to each homological feature.

We set up the following boundary matrix, ∂,

∂[i, j] = 1 if σ i ⊂ σ j and dim(σ i ) = dim(σ j ) -1; ∂[i, j] = 0 otherwise.
Therefore, the rows and columns of ∂ have the same order as the simplices and its columns stores the boundary of a simplex. Also ∂ is an upper-triangular matrix since a face simplex appears before its cofaces. We reduce ∂ to another matrix R using column operations so that we get the desired pairings of positive and negative simplices.

Let low(j) be the maximum value of the non-zero row index in column j (i.e. the index of the lowest non-zero row) and let it undefined for a zero column. The algorithm reduces ∂ by adding columns from left to right and it is reduced if low(j) = low(j ) whenever j = j for any two non-zero columns.

Algorithm 1 Reduction Algorithm while there exists j < j with low(j ) = low(j) do 5:

add column j to column j mod 2 operation.

6:

end while

7:
end for 8: end procedure Return R

We discuss a few properties of the matrix R.

Each zero column of R corresponds to a positive simplex, and the number of zero columns corresponding to the p-simplices of K is the rank of Z p . Each non-zero column corresponds to a negative simplex, and the number of non-zero columns corresponding to the p-simplices of K is the rank of B p . This gives us the rank of the homology classes of K as β p = rank(Z p )rank(B p ). However to compute the persistent homology we need to find the appropriate pairings of positive and negative simplices. Interestingly the matrix R does contain this information.

To compute the pairings we consider a zero column i, as mentioned before σ i is a positive simplex and therefore we look for its negative partner. We look at the corresponding row, i for the negative partner simplex. There are two possibilities:

1. There exists a column j, such that low(j) = i. Then σ j is said to be paired with σ i and therefore [i, j] or with the filtration values [ f (σ i ), f (σ j )] is a point in the persistence diagram of H p (K), where dim(σ i ) = p.

2. There exists no column j, such that low(j) = i. Then σ i remains un-paired, so σ i corresponds to a class that was created but was never destroyed and this gives a

point [i, ∞) or [ f (σ i ), ∞) in the persistence diagram of H p (K), where dim(σ i ) = p.
Although the reduced matrix R is not unique, the above properties are true for any matrix reduced from δ. The runtime complexity of the algorithm is O(m 3 ). However, in most practical cases, the runtime is usually near-linear in m as ∂ is usually sparse.

Equivalence and Stability of Persistence Modules

The following theorem states a condition under which two persistence module will be equivalent [START_REF] Carlsson | Zigzag persistence[END_REF][START_REF] Derksen | Quiver representations[END_REF].

Theorem 2.5.2. Two different persistence modules

V : {V 1 -→ V 2 -→ • • • -→ V m } and W : {W 1 -→ W 2 -→ • • • -→ W m }, connected through a set of homomorphisms φ i : V i → W i are equivalent if the φ i are isomorphisms and the following diagram commutes. V 1 V 2 • • • V m-1 V m W 1 W 2 • • • W m-1 W m φ 1 φ 2 φ m-1 φ m
Equivalent persistence modules have the same interval decomposition, hence the same diagram.

For simplicity we have chosen the set of natural numbers as our index set, that is the vector spaces V i in V are indexed over N and therefore the intervals are also natural numbers. However, the definition works well for any index set J ⊆ R. There exists more approximate notions of similarity between two persistence modules.

Bottleneck distance. If J ⊆ R is the chosen index set then a persistence diagram is a multiset of points in the extended plane, R2 . Clearly, the persistence diagram consists of points above the diagonal (the line x = y). To have a well defined notion of distance between two persistence diagrams, we add the points of the diagonal to the diagram, each with infinite multiplicity. We use the L ∞ norm to define distance between two points v = (v 1 , v 2 ) and w = (w

1 , w 2 ) in R2 , that is, v -w ∞ = max{|v 1 -w 1 |, |v 2 -w 2 |}.
Let dgm(V) and dgm(W) be two persistence diagrams. Let us consider bijections η : dgm(V) → dgm(W) then the bottleneck distance d B (dgm(V), dgm(W)) between the diagrams is defined as follows, Definition 2.5.4 (bottleneck distance).

d B (dgm(V), dgm(W)) = inf η sup v∈dgm(V) v -η(v) ∞ .
Therefore, it is an infimum over all possible η.

The problem of computing the bottleneck distance between two persistence diagrams can be reduced to a matching problem of a bipartite graph. Assuming that the persistence diagrams consist of finitely many off-diagonal points with finite multiplicity and all the diagonal points with infinite multiplicity. In this case, computing d B (dgm(V), dgm(W)) reduces to a bipartite graph matching problem.

Let X = dgm(V) and Y = dgm(W) then X 0 and Y 0 respectively denote the offdiagonal points of X and Y. If a = (x, y) is an off-diagonal point, then the closest point to a on the diagonal is its orthogonal projection on the diagonal, denoted as a = ( (x+y) 2 ,

(x+y)

2 ). Let X 0 denote the set of all projections of X 0 and similarly Y 0 denote the set of all projections of Y 0 .

We define M = X 0 ∪ Y 0 and N = X 0 ∪ Y 0 ; they both have the same cardinality. Then computing bottleneck distance is computing a matching in the weighted complete bipartite graph, G = (M ∪ N, M × N, c) and the weights are given by the following weight function 2 and we denote this log transform on dgm(V) as log(dgm(V)). The bottleneck distance on log scale is then defined as d B (log(dgm(V)), log(dgm(W))).

(v 1 , v 2 ) ∈ dgm(V) ∈ R 2 to (log(v 1 ), log(v 2 )) ∈ R

Stability.

Stability of persistence diagrams is the hallmark result in the theory of persistence, it provides a context to the persistence theory. There are several different variants of the stability theorem. The following Theorem 2.5.3 states that if there are two close filtrations on a simplicial complex K then their persistence diagram would be close as well.

Theorem 2.5.3. Let K be a simplicial complex and f , g : K → R two filtration functions on K. Let V f and V g be two persistence modules associated with the filtrations f and g respectively, then the bottleneck distance between dgm(V f ) and dgm(V g ) is bounded from above by the L ∞ -distance between f and g, that is,

d B (dgm(V f ), dgm(V g )) ≤ f -g ∞ where f -g ∞ = sup σ∈K | f (σ) -g(σ)|
One of the application of the above stability theorem is that given a point set P, the bottleneck distance on log scale between the persistence diagrams of the Čech filtration and the Rips filtration is bounded. We make this more precise as follows. Proof. The Čech and the Rips filtrations individually define two filtration functions f and g on the final simplicial complex K which is a |P|-simplex. As mentioned before since these filtrations are interleaved, with the following inclusions,

R(P, ) ⊆ C(P, √ 2 ) ⊆ R(P, √ 2 )
the corresponding filtration functions satisfy,

log( f ) -log(g) ∞ ≤ √ 2
and therefore Theorem 2.5.3 implies,

d B (log(dgm(C )), log(dgm(R ))) ≤ √ 2.
Another implicit consequence of the stability theorem is that if the point set P is transformed to P with small perturbations then the persistence of diagram of the perturbed point changes with small amount, bounded above by the amount of perturbation.

Conclusion

In this chapter, we reviewed some essential notions of topology and in particular of persistent homology and briefly explained a simple algorithm to compute the persistence diagram of a filtration.

As discussed in Section 1.4 of Chapter 1, recently there are many improved algorithms to compute the persistence diagram of filtrations by exploiting the sparsity and the structure of the boundary matrix. Another variant is to compute persistence cohomology, which is dual to homology.

All these algorithm focuses on the faster reduction of the boundary matrix. The second approach for faster computation of the persistence diagram is to simplify the input filtration to a smaller filtration by preserving the persistence or approximating it by bounded bottleneck distance. Our work in this thesis is along the second approach we uses strong collapses and edge collapses to simplify the input filtration.

In Section 1.3 of Chapter 1, we have mentioned the extensions of persistent homology to more general sequences like towers and zigzag sequences. We also mention new techniques to compute persistence diagrams of towers as well, usually by converting the tower to an equivalent filtration by simplicial expansion (conning) and then compute the persistence of the equivalent filtration [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF][START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF]. We have made further advancements in the special case of the flag tower (tower of flag complexes) based on the previous works [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF][START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF], which we will explain in more details in Chapter 4.

There are algorithms to compute zigzag persistence of zigzag filtration [START_REF] Carlsson | Zigzag persistence[END_REF][START_REF] Carlsson | Zigzag persistent homology and real-valued functions[END_REF]. The usual technique to convert a tower to an equivalent filtration works for the conversion of a general zigzag sequence to an equivalent zigzag filtration. And this facilitates the computation of the zigzag persistence of any general zigzag sequence.

Chapter 3

Strong Collapse And Persistence

In this chapter, we introduce our first approach to simplify the complexes of the input sequence using the notion of strong collapse. As described before in Chapter 1, Given a zigzag sequence

Z : {K 1 f 1 -→ K 2 g 2 ← -K 3 f 3 -→ • • • f (n-1) ---→ K n } of simplicial complexes K i connected through simplicial maps { f i -→ or g j
← -}, we independently strong collapse the complexes of the sequence to reach a sequence

Z c : {K c 1 f c 1 -→ K c 2 g c 2 ← -K c 3 f c 3 -→ • • • f c (n-1) ---→ K c n }, with induced simplicial maps { f c i -→ or g c j ← -} (defined in Section 3.4).
K c i is the core of the complex K i and the sequence Z c is called the core sequence of Z. In Section 3.4, we prove that Z and its core sequence Z c are equivalent.

We introduce the notion of strong collapse in Section 3.1. In Section 3.2 we define the notion of nerve of a simplicial complex and show its relationsip with the strong collapse. We describe an algorithm to compute the core K c of a general simplicial complex K using strong collapses. The algorithm uses a representation of K that consists of only the maximal simplices of K. It is based on the nerve-square N 2 (K) construction defined in Section 3.2.

We then use our algorithm to compute the core sequence by independently strong collapsing the constituent complexes of the sequence. We explain an approximation scheme that compromizes between precision and time by choosing the number of simplicial complexes of the sequence we strong collapse. In Section 5.4, we perform some experiments on publicly available data sets, which shows that our approach is extremely fast and memory efficient in practice.

Strong Collapse

The notion of strong collapse is relatively new and it was introduced by Barmak and Minian [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]. It is a special type of simple collapse and is a stronger notion than simple collapse.

Definition 3.1.1. A vertex v in K is called a dominated vertex if the link of v in K, lk K (v) is a simplicial cone, that is, there exists a vertex v = v and a subcomplex L in K, such that lk K (v) = v L. v v v v v FIGURE 3.
1 -Illustration of an elementary strong collapse. In the complex on the left, v is dominated by v . The link of v is highlighted in red. Removing v leads to the complex on the right.

We say that the vertex v is dominating v and v is dominated by v . The symbol K \ v (deletion of v from K) refers to the subcomplex of K which has all the simplices of K except the ones containing v.

Removal of a simplex. We denote by K \ σ the subcomplex of K obtained by removing σ, i.e. the complex that has all the simplices of K except the faces and the cofaces of σ.

Below is an important remark from [3, Remark 2.2], which proposes an alternative definition of dominated vertices.

Definition 3.1.3.

There is a strong collapse from a simplicial complex K to its subcomplex L, if there exists a series of elementary strong collapses from K to L, denoted as K L.

The inverse of a strong collapse is called a strong expansion. If there exists a combination of strong collapses and/or strong expansion from K to L then K and L are said to have the same strong homotopy type.

The notion of strong homotopy type is stronger than the notion of simple homotopy type in the sense that if K and L have the same strong homotopy type, then they have the same simple homotopy type (simple homotopic), and therefore the same homotopy type [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]. The converse is not necessarily true, there are examples of contractible or simply collapsible simplicial complexes that are not strong collapsible.

A complex without any dominated vertex will be called a minimal complex. A core of a complex K is a minimal subcomplex K c ⊆ K, such that K K c . Every simplicial complex has a unique core up to isomorphism. The core decides the strong homotopy type of the complex, and two simplicial complexes have the same strong homotopy type if and only if they have isomorphic cores [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]Theorem 2.11].

Retraction map: If a vertex v ∈ K is dominated by another vertex v ∈ K, the vertex map r : K → K \ v defined as: r(w) = w if w = v and r(v) = v , induces a simplical map that is a retraction map. The homotopy between r and the identity i K\v over K \ v is in fact a strong deformation retraction. Furthermore, the composition (i K\v )r is contiguous to the identity i K over K [3, Proposition 2.9].

Existence of a simplicial map (the retraction map r) corresponding to a strong collapse is a special property of strong collapse, which is not true in the case of simple collapse. For example in Figure 2.4 (a) there are no simplicial map corresponding to the removal of the free pair (the triangle and the edge).

Nerve and Strong Collapse

One of the most remarkable property of strong collapses is its association with the operation of nerve of a simplicial complex. We will first begin with the definition of a cover and the general definition of a nerve. Definition 3.2.1. A closed cover U of a topological space X is a set of closed sets of X such that X is equal to their union.

Here we choose closed sets to define a cover, if we choose open sets we define an open cover where X could be a subset of the union of the open sets in U .

Definition 3.2.2. A cover U is called a good cover if for any subset

{U i 1 , • • • , U i k } ⊆ U the intersection i j U i j is either empty or contractible.
Definition 3.2.3. The nerve of a cover U is an abstract simplicial complex, defined as the set of all non-empty intersections of the elements of U .

The following theorem is one of the foundational theorem of computational topology. Theorem 3.2.1. The nerve of a finite good closed cover U is homotopy equivalent to the space X :=

U α ∈U U α .
The nerve is a well known construction that transforms a continuous space to a combinatorial space preserving its homotopy type. The Čech complex defined in subsection 2.2.3 is the nerve of the cover (the set of d-balls) of the space defined by the union of the balls. Since a d-ball is convex, the intersection of any finitely many d-ball is convex and hence contractible, therefore the Čech complex is homotopic to the space defined by the union of the balls.

Nerve of a simplicial complex:

The nerve N (K) of a simplicial complex K is defined as the nerve of the set of maximal simplices of the complex K (considered as a cover of the complex). Hence all the maximal simplices of K will be the vertices of N (K) and their non-empty intersection will form the simplices of N (K). For j ≥ 2 the iterative construction is defined as N j (K) = N (N j-1 (K)). This definition of nerve preserves the homotopy type, K N (K) [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]. A remarkable property of this nerve construction is its connection with strong collapses.

Taking the nerve of any simplicial complex K twice corresponds to a strong collapse. An easy consequence of this theorem is that a complex K is minimal if and only if it is isomorphic to N 2 (K) [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]Lemma 3.6]. This means that we can keep collapsing our complex K by applying iteratively N 2 (.) until we reach the core of the complex K.

The sequence K, N 2 (K), ..., N 2p (K) is a decreasing sequence in terms of number of simplices.

Strong collapse of a simplicial complex

In this section, we describe an algorithm to strong collapse a simplicial complex K, provide the details of the implementation and analyze its complexity.

Data structure. Basically, we represent K as the adjacency matrix M between the vertices and the maximal simplices of K. We will simply call M the adjacency matrix of K. The rows of M represent the vertices and the columns represent the maximal simplices of K. For convenience, we will identify a row (resp. column) and the vertex (resp. maximal simplex) it represents. An entry M[v i ][σ j ] associated with a vertex v i and a maximal simplex σ j is set to 1 if v i ∈ σ j , and to 0 otherwise. For example, the matrix M in the left of the Table 3.1 corresponds to the leftmost simplicial complex K in Figure 3.2.

Usually, M is very sparse. Indeed, each column contains at most d + 1 non-zero elements since the simplices of a d-dimensional complex have at most d + 1 vertices, and each line contains at most Γ 0 non-zero elements where Γ 0 is the maximum number of maximal simplices that are incident to a given vertex. As already mentionned, in many practical situations, Γ 0 is a small fraction of the number of maximal simplices. It is therefore beneficial to store M as a list of vertices and a list of maximal simplices. Each vertex v in the list of vertices points to the maximal simplices that contain v, and each simplex in the list of maximal simplices points to its vertices. This data structure is similar to the SAL data structure of [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF].

Core algorithm. Given the adjacency matrix M of K, we compute the adjacency matrix C of the core K c . It turns out that using basic row and column removal operations, we can easily compute C from M. Loosely speaking our algorithm recursively computes N 2 (K) until it reaches K c .

σ 1 σ 2 σ 3 σ 4 σ 5 a 0 0 1 0 0 b 1 1 1 0 0 c 1 0 0 0 0 d 0 0 1 1 0 e 0 1 0 1 1 f 0 0 0 0 1 b d e σ 1 1 0 0 σ 2 1 0 1 σ 3 1 1 0 σ 4 0 1 1 σ 5 0 0 1 σ 2 σ 3 σ 4 b 1 1 0 d 0 1 1 e 1 0 1 TABLE 3.1 -From left to right M, N (M) and N 2 (M).
The columns of M (which represent the maximal simplices of K) correspond to the vertices of N (K). Also, the columns of M that have a non-zero value in a particular row v correspond to the maximal simplices of K that share the vertex associated with row v. Therefore, each row of M represents a simplex of the nerve N (K). Not all simplices of N (K) are associated with rows of M but all maximal simplices are since they correspond to subsets of maximal simplices with a common vertex. To remedy this situation, we remove all the rows of M that correspond to non-maximal simplices of N (K). This results in a new smaller matrix M whose transpose, noted N (M), is the adjacency matrix of the nerve N (K). We then exchange the roles of rows and columns (which is the same as taking the transpose) and run the very same procedure as before so as to obtain the adjacency matrix N 2 (M) of N 2 (K).

The process is iterated as long as the matrix can be reduced. Upon termination, we output the reduced matrix C := N 2p (M), for some p ≥ 1, which is the adjacency matrix of the core K c of K. Removing a row or column is the most basic operation of our algorithm. We will discuss it in more detail later in the paragraph Domination test.

Example. As mentioned before, the matrix M in the left of the Table 3.1 represents the simplicial complex K in the left of Figure 3.2. We go through the rows first, rows a and c are subsets of row b and row f is a subset of e. Removing rows a, c and f and transposing M yields the adjacency matrix N (M) of N (K) in the middle. Now, row σ 1 is a subset of σ 2 and of σ 3 , and σ 5 is a subset of σ 2 and of σ 4 . We remove these two rows of N (M) and transpose N (M) so as to get N 2 (M) (the rightmost matrix of Table 3.1), which corresponds to the core drawn in red in Figure 3.2.

Domination test. Now we explain in more detail how to detect the rows that need to be removed. Let v be a row of M and σ v be the associated simplex in N (K). If σ v is not a maximal simplex of N (K), it is a proper face of some maximal simplex σ v of N (K). Equivalently, the row v of M that is associated with σ v contains row v in the sense that the non zero elements of v appear in the same columns as the non zero elements of v . We will say that row v is dominated by row v and determining if a row is dominated by another one will be called the row domination test. Notice that when a row v is dominated by a row v , the same is true for the associated vertices since all the maximal simplices that contain vertex v also contain vertex v , which is the criterion to determine if v is dominated by v (See Remark 1 in Section 3.1.1). The algorithm removes all dominated rows and therefore all dominated vertices of K.

After removing rows, the algorithm removes the columns that are no longer maximal in K, which might happen since we removed some rows. Removing a column may lead in turn to new dominated vertices and therefore new rows to be removed. When the algorithm stops, there are no rows to be removed and we have obtained the core K c of the complex K. Note that the algorithm provides a constructive proof of 3.2.2.

Removing columns is done in very much the same way: we just exchange the roles of rows and columns.

Computing the retraction map r. The algorithm also provides a direct way to compute the retraction map r defined in Section 3.1. The retraction map corresponding to the strong collapses executed by the algorithm can be constructed as follows. A row r being removed in M corresponds to a dominated vertex in K and the row which contains r corresponds to a dominating vertex. Therefore we map the dominated vertex to the dominating vertex and compose all such maps to get the final retraction map from K to its core K c . The final map is simplicial as well, as it is a composition of simplicial maps.

Reducing the number of domination tests. We first observe that, when one wants to determine if a row v is dominated by some other row, we don't need to test v with all other rows but with at most d of them. Indeed, at most d + 1 rows can intersect a given column since a simplex can have at most d + 1 vertices. For example, in Table 3.1 (Left), to check if row e (highlighted in brown) is dominated by another row, we pick the first non-zero column σ 2 (highlighted in Gray) and compare e with the non-zero entries {b} of σ 2 .

A second observation is that we don't need to test all rows and columns for domination, but only the so-called candidate rows and columns. We define a row r to be a candidate row for the next iteration if at least one column containing one of the non-zero elements of r has been removed in the previous column removal iteration. Similarly, by exchanging the roles of rows and columns, we define the candidate columns. Candidate rows and columns are the only rows or columns that need to be considered in the domination tests of the algorithm. Indeed, a column τ of M whose non-zero elements all belong to rows that are present from the previous iteration cannot be dominated by another column τ of M, since τ was not dominated at the previous iteration and no new non-zero elements have ever been added by the algorithm. The same argument follows for the candidate rows.

We maintain two queues, one for the candidate columns (colQueue) and one for the candidate rows (rowQueue). These queues are implemented as First in First out (FIFO) queues. At each iteration, we pop out a candidate row or column from its respective queue and test whether it is dominated or not. After each successful domination test, we push the candidate columns or rows in their appropriate queue in preparation for the subsequent iteration. In the first iteration, we push all the rows in rowQueue and then alternatively use colQueue and rowQueue. Algorithm 2 gives the pseudo code of our algorithm.

Time Complexity.

The most basic operation in our algorithm is to determine if a row is dominated by another given row, and similarly for columns. In our implementation, the rows (columns) of the matrix that are considered by the algorithm are stored as sorted lists. Checking if one sorted list is a subset of another sorted list can be done in Algorithm 2 Core algorithm 1: procedure CORE(M) M is the adjacency matrix of K.

2:

rowQueue ← push all rows of M (all vertices of K) return M M is now the adjacency matrix of the core of K. 30: end procedure time O(l), where l is the size of the longer list. Note that the length of a row list is at most Γ 0 where Γ 0 denotes the largest number of maximal simplices incident to a vertex. The length of a column list is at most d + 1 where d is the dimension of the complex. Hence checking if a row is dominated by another row (Line 8) takes O(Γ 0 ) time and checking if a column is dominated by another column (Line 19) takes O(d) time.

Next consider one execution of the while loop on rows (Lines 4-14). We will loop at most n v times since rowQueue contains at most n v elements, where n v is the number of vertices of the complex K. Since simplex σ has at most d + 1 vertices w and since testing if v is a subset of w (Line 8) takes at most Γ 0 time as shown above, a row domination test (Lines 7-13) takes time O(dΓ 0 ). Hence, executing one while loop on rows takes n v dΓ 0 time. If, during the execution of the while loop, we never execute Lines 9-10, there is no dominated vertex, colQueue remains empty and the algorithm stops. Otherwise, we enter the while loop on columns (Lines 15-25).

We will loop at most m times since colQueue contains at most m elements where m is the number of maximal simplices in K. Vertex v is incident to at most Γ 0 maximal simplices and, as shown above, testing if τ is a subset of σ (Line 19) takes O(d) time. It follows that executing one while loop on columns takes O(mdΓ 0 ) time.

It remains to bound the number of times we execute the while loops or, equivalently, the number of times we execute Line 27. This number is at most n v . Indeed, each time we execute Line 27, the algorithm has removed at least one row from M since otherwise it stops. It follows that the total complexity of the algorithm is O(n v dΓ 0 (n v + m)). Noticing that n v Γ 0 ≥ m, the complexity can be simply written as O(n 2 v dΓ 2 0 ). In practice, m is much smaller than n, the total number of simplices, and Γ 0 is much smaller than Γ, the maximum number of simplices incident on a vertex. Typically Γ grows exponentially with d while Γ 0 remains almost constant as d increases. See Table 5 in [START_REF] Boissonnat | Building efficient and compact data structures for simplicial complexes[END_REF], related results in [START_REF] Boissonnat | An efficient representation for filtrations of simplicial complexes[END_REF], and the plots in Section 3.5.

Strong collapse of a sequence of simplicial complexes

In this section, we will present our main result that the persistence homology of a sequence of simplicial complexes is preserved under strong collapse. We begin with some brief background on zigzag persistence all the notions recalled here are simply extensions of the notions about towers and filtration recalled in Section 2.5, we mention them here for completeness. Readers interested in more details can refer to [START_REF] Carlsson | Zigzag persistence[END_REF][START_REF] Carlsson | Zigzag persistent homology and real-valued functions[END_REF][START_REF] Derksen | Quiver representations[END_REF].

Given a zigzag sequence of simplicial complexes

Z : {K 1 f 1 -→ K 2 g 2 ← -K 3 f 3 -→ • • • f (n-1) ---→ K n }.
If we compute the homology classes of all K i s, we get the sequence

P (Z ) : {H p (K 1 ) f * 1 -→ H p (K 2 ) g * 2 ← -H p (K 3 ) f * 3 -→ • • • f * (n-1) ---→ H p (K n )}.
Here H p (-) denotes the homology class of dimension p with coefficients from a field F and * denotes an induced homomorphism. P (Z ) is a sequence of vector spaces connected through homomorphisms, called a zigzag module. More formally, a zigzag module V is a sequence of vector spaces

{V 1 -→ V 2 ← -V 3 -→ • • • ← → V n }
connected with homomorphisms {-→, ← -} between them. A zigzag module arising from a sequence of simplicial complexes captures the evolution of the topology of the sequence.

For two integers b and d, 1 ≤ b ≤ d ≤ n; we can define an interval module I[b, d] by assigning V i to F when i ∈ [b, d], and null spaces otherwise, the maps between any two F vector spaces is identity and is zero otherwise. For example

I[2, 4] : {0 0 -→ F I ← -F I -→ F 0 ← -0 0 -→ 0},
here n = 6. Any zigzag module can be decomposed as the direct sum of finitely many interval modules, which is unique upto the permutations of the interval modules [START_REF] Carlsson | Zigzag persistence[END_REF].

The multiset of all the intervals [b j , d j ] corresponding to the interval module decomposition of any zigzag module is called a zigzag (persistence) diagram. The zigzag diagram completely characterizes the zigzag module, that is, there is bijective correspondence between them [START_REF] Carlsson | Zigzag persistence[END_REF][START_REF] Zomorodian | Computing persistent homology[END_REF].

Two different zigzag modules

V : {V 1 -→ V 2 ← -V 3 -→ • • • ← → V n } and W : {W 1 -→ W 2 ← -W 3 -→ • • • ← → W n },
connected through a set of homomorphisms φ i : V i → W i are equivalent if the φ i s are isomorphisms and the following diagram commutes [START_REF] Carlsson | Zigzag persistence[END_REF][START_REF] Derksen | Quiver representations[END_REF].

V 1 V 2 V 3 • • • V n-1 V n W 1 W 2 W 3 • • • W n-1 W n φ 1 φ 2 φ 3 φ n-1 φ n
Note that the length of the modules and the directions of the arrows in them should be consistent. Two equivalent zigzag modules will have the same interval decomposition, therefore the same zigzag diagram.

Strong collapse of the zigzag module: Given a zigzag sequence

Z : {K 1 f 1 -→ K 2 g 2 ← -K 3 f 3 -→ • • • f (n-1) ---→ K n }.
We define the core sequence Z c of Z as

Z c : {K c 1 f c 1 -→ K c 2 g c 2 ← -K c 3 f c 3 -→ • • • f c (n-1) ---→ K c n }.
Where K c i is the core of K i . The forward maps are defined as, f c j := r j+1 f j i j ; and the backward maps are defined as g c j := r j g j i j+1 . The maps i j : K c j → K j and r j : K j → K c j are the composed inclusions and the retractions maps defined in Section 3.1 respectively. We call the procedure of forming the core sequence using the cores and the induced simplicial maps as core-assembly. Theorem 3.4.1. Zigzag modules P (Z ) and P (Z c ) are equivalent.

Proof. Consider the following diagram

K 1 K 2 K 3 • • • K n-1 K n K c 1 K c 2 K c 3 • • • K c n-1 K c n f 1 r 1 r 2 g 2 r 3 f n-1 r n-1 r n f c 1 g c 2 f c n-1
and the associated diagram after computing the p-th homology groups

H p (K 1 ) H p (K 2 ) H p (K 3 ) • • • H p (K n-1 ) H p (K n ) H p (K c 1 ) H p (K c 2 ) H p (K c 3 ) • • • H p (K c n-1 ) H p (K c n ) f * 1 r * 1 r * 2 g * 2 r * 3 f * n-1 r * n-1 r * n ( f c 1 ) * (g c 2 ) * ( f c n-1 ) *
Since there exists a strong deformation retraction between r j and i j , the induced homomorphisms r * j and i * j are isomorphisms [START_REF] Hatcher | Algebraic Topology[END_REF]Corollary 2.11]. We claim that the composed map i j r j is contiguous to the identity on K j . Indeed, i j can be decomposed into a series of inclusions i 1 j i 2 j ...i s j that correspond to elementary strong collapses and similarly r j can be decomposed into r s j r s-1 j ...r 1 j for some s. Using [3, Proposition 2.9] and the fact that contiguity is preserved under composition, it follows that i j r j is contiguous to the identity on K j since

i j r j = i 1 j i 2 j ...i s j • r s j r s-1 j ...r 1 j ∼ i 1 j i 2 j ...i s-1 j • r s-1 j ...r 1 j ∼ ... ∼ i 1 j • r 1 j ∼ id
It then follows that f c j r j = r j+1 f j i j r j is contiguous to r j+1 f j , and similarly that g c j r j+1 is contiguous to r j g j . Now, since contiguous maps are homotopic at the level of geometric realizations and since homotopic maps induce the same homomorphism, we have ( f c j r j ) * = (r j+1 f j ) * and thus ( f c j ) * r * j = r * j+1 f * j and similarly (g c j ) * r * j+1 = r * j g * j , see [START_REF] Hatcher | Algebraic Topology[END_REF]Proposition (1) page 111]. Therefore all the squares in the lower diagram commute and the set of maps r * j s are isomorphisms, therefore P (Z ) and P (Z c ) are equivalent and hence their zigzag diagrams are identical.

Remark.

The above result can be extended to multidimensional persistence using the more general notion of quiver representation [START_REF] Derksen | Quiver representations[END_REF].

The algorithms to compute persistence are for sequences of simplicial complexes connected via inclusions only : inclusions can be in both directions, that is either zigzag filtrations or filtrations. To compute the persistent homology of more general sequences, one usually converts them to an equivalent inclusion-only sequence. Zigzag sequences will thus be transformed in zigzag filtrations and towers will be transformed in filtrations respectively.

The works of Dey et. al. [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF] and Kerber and Schrieber [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF] describe methods to convert a tower to a filtration general towers. The same techniques could be applied to convert a zigazag sequence to a zigzag filtration. Given a zigzag sequence of general simplicial complexes, one can individually strongly collapse each of the complexes using the algorithm described in Section 3.3 and then assemble the cores using the maps prescribed in this section and compute the persistence of the core sequence. The core sequence of a zigzag filtration is usually a general zigzag sequence rather than a zigzag filtration. To compute the persistent homology of such a core sequence, one can expand it so as to obtain a zigzag filtration using the approach described in [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF] and [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF].

In the next section we perform some experiments using the methods described in this section. Our experiments are performed on filtrations of Rips complex and after strong collapsing the filtrations we get towers. We then use the algorithm described in [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF] to compute the persistence of the core tower.

In the special case of a flag filtration or of a flag tower, the core sequence is a flag tower. Again, to compute the persistence of a flag tower, one needs to expand it to get a filtration. We describe a method to transform a flag tower to a flag filtration using only the 1-skeleton of the tower in Chapter 4.

Approximation of the persistence diagram of filtrations

In this section, we restrict our attention to the case of filtrations, i.e. nested sequences of simplicial complexes connected by inclusions. Filtrations, and in particular Rips filtrations, are easy to construct and commonly used in Topological Data Analysis. However, because of their inclusive nature, the number of simplices grows exponentially in the number of sample points which often limits PH computation to small examples.

As we have seen, our method tackles this issue by using only maximal simplices and dramatically reducing the size of the input complexes using strong collapses. Further dramatic reduction can be obtained if we allow to approximate the PH of the input filtration as shown now.

An approximation scheme: Instead of strong collapsing all the complexes in the filtration, we can strong collapse the complexes less often, i.e. after several inclusions rather than just one. This will result in a faster algorithm but comes with a cost: the computed PD will only be approximate.

The complexes in a filtration F are usually associated to different real values of a scale parameter. For example, in a VR filtration, the filtration value of a simplex is the length of the longest edge of the simplex and in general the filtration consists of a sequence of elementary inclusions (i.e. inclusion of a single simplex) with non decreasing filtration values. A persistent pair then associates the filtration value of a simplex that creates a homology cycle with the filtration value of the simplex that kills the cycle. The length of the persistence pair is the difference between the two filtration values.

We call snapshots the values of the scale parameter at which we choose to strong collapse the complex. The difference between two consecutive snapshots is called a step. We approximate the filtration value of a simplex as the value of the snapshot at which it first appears. It is not hard to see that our algorithm will report all persistence pairs that are separated by at least one snapshot. Hence if all steps are at most some > 0, we will compute all the persistence pairs whose lengths are at least . It follows that the bottleneck distance between the computed PD and the exact one is at most .

Computational experiments:

Now, we present some computational experiments to showcase the efficiency achieved by our approach. For our experiments, we choose three datasets coming from applications, for more detail about the datasets please refer to [START_REF] Otter | A roadmap for the computation of persistent homology[END_REF]. The algorithms to strong collapse a simplicial complex (Algorithm 2) and to form the core sequence (core-assembly) have been coded in C++. We name our package to preprocess the initial sequence and construct the collapsed sequence PH-Collapser. The code has been compiled using the compiler 'clang-900.0.38' and all computations were performed on a '2.8 GHz Intel Core i5' machine with 16 GB of available RAM.

For each data set, we select a number of snapshots and independently strong collapse all the complexes associated to these snapshots. We then assemble the resulting individual cores using the induced simplicial maps introduced in Section 3.4. The resulting core sequence with induced simplicial maps between the collapsed complexes is in general a simplicial tower we call the core tower. We then convert the core tower into an equivalent filtration using the Sophia software [START_REF] Schreiber | Sophia[END_REF], which implements the algorithm described by Kerber and Schreiber [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF]. Finally, we run the persistence algorithm of the Gudhi library [START_REF]Gudhi: Geometry understanding in higher dimensions[END_REF] to obtain the persistence diagram (PD) of the equivalent filtration. For the core tower, we use Gudhi through Sophia using the command <./sophia -cgudhi inputTowerFile outputPDFile>1 . Table 3.2 summarises the results of the experiments. The total time includes 1. the time taken to compute the entire VR filtration at snapshot values, 2. the time taken to collapse all the subcomplexes, assemble their cores and transform them into an equivalent filtration, and 3. the time to compute the PD of the equivalent filtration. At each snapshot, we compute the full associated VR complex with no restriction on its dimension and compute the PD in all dimensions upto the dimension of the complex. The experiments are done on the three datasets netw-sc, senate and eleg from [18] In all cases, the total time stays within a small factor (less than 2) from the time to compute the VR complex. The only exception is the dataset senate, which has comparatively fewer points and for which the time to compute the VR complex is relatively fast. However, here too the ratio is less than eight, which is much less than 403, the number of snapshots. This clearly indicates that in our approach the time to perform the strong collapses and the core assemblies together with the time to compute the PD is much smaller than the time to compute the VR complex. This implies that one can refine the PD (through smaller steps) at a very low cost.

Our choice of snapshots is arbitrary and could be done in a non uniform way after analyzing the distribution of the length of the edges in the Rips-complex at a relatively small increase in the total computing time. Comparison with Ripser. Ripser [START_REF] Bauer | Ripser[END_REF] is a state-of-the-art software to compute persistence of Rips complex. To compare, we perform the same experiments using Ripser. Command <./ripser inputData -format distances -threshold inputTh -dim inputDim > was used to run Ripser and we used the distance matrix format for all the datasets. Differently from PH-Collapser, Ripser needs a parameter -dim until which it computes the PD. For a given threshold (maximum scale parameter) and dim, Ripser basically computes the dim-skeleton of the VR complex and then computes the PD of the skeleton. The datasets we considered here didn't have any non-trivial persistence pairs beyond dimension 4-5, however with our approach we were able to say it and until the maximum possible dimension. Whereas in most of the cases, Ripser couldn't compute even the Rips skeleton beyond dimension 7.

Data

As mentioned before in this section, we define the filtration value of a simplex as the value of the snapshot parameter at which it appears for the first time. Therefore, the computed PD by PH-Collapser is not exact. However, in the above experiments, we choose steps that are very small so that the bottleneck distance between the two PD returned by Ripser and PH-collapser for a given data set is also very small.

The above experiments have been performed considering Rips complexes as general simplicial complexes. This was to illustrate the general performances of our algorithm that works for any type of simplicial complexes. However, in the case of Rips complexes and, more generally, in the case of flag complexes, we can further improve the performances by representing the complexes by their 1-skeletons instead of their maximal faces, an even more compact representation. In Chapter 4, we adapt the methodology introduced in this Chapter to the case of flag complexes and show that we can compute the core filtration (which is itself a flag filtration) using only 1-skeletons.

The plots below count the maximal simplices and the dimensions of the complexes across the initial filtration (in solid) and the collapsed tower (as dashed). We show in solid red and dashed red respectively the filtration and the collapsed tower of the data netw-sc. Similarly we show in solid green and dashed green respectively the filtration and the collapsed tower of the data senate. Finally, we show in solid black and dashed black respectively the filtration and the collapsed tower of the data eleg.

We can observe that in all cases the number of maximal simplices never increases. Also they are far fewer (by a factor exponential in the dimension) in number compared to the total number of simplices. Observe that for the uncollapsed filtrations solid red, green and black, the dimension of the complexes increases quite rapidly with the snapshot index. Another key fact to observe is that the dimension of the complexes in the corresponding core tower are much smaller than their counterparts in the original filtration. This has a huge effect on the performances since the total number of simplices depends exponentially on the dimension. Observations from the plots combined with the experimental results of Table 3.2 clearly indicate that performances are much improved when using strong collapses.

Discussion

In this chapter, we presented a novel approach to compute the persistence homology of a sequence of simplicial complexes. Our approach is based on strong collapses that has been introduced by Barmak and Minian [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]. Our method works very well in pratice and, as shown using publicly available data, it is much faster and memory efficient with respect to not using it. We believe that the solid mathematical foundations presented in [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF], its applicability to all kinds of sequences of simplicial complexes, and the availability of the simple and efficient algorithms developed in this chapter, strong collapses will be immensely useful to reduce the complexity of many problems in computational topology.

On the theoretical side, this work raises several questions. In particular, it would be nice to have theoretical guarantees on the amount of reduction the algorithm can achieve. We intend to explore this and related issues in future work.

This chapter was based on our work reported in [START_REF] Boissonnat | Strong Collapse for Persistence[END_REF].

Chapter 4

Persistence of Flag Complexes

In this chapter, we restrict the class of simplicial complexes to flag complexes and we focus on the problem of computing Persistent Homology of a flag tower, i.e. a sequence of flag complexes connected by simplicial maps. The case of flag filtration is then a special case of flag tower. Flag complexes are fully characterized by their graph (or 1-skeleton), the other faces being obtained by computing the cliques of the graph. By restricting to the case of flag complexes, we achieve further decisive improvement in terms of time and space complexities with respect to our approach in the previous chapter.

We first show that strong collapses of flag complexes can be computed in time O(k 2 n 2 v ) where n v is the number of vertices of the complex and k is the maximal degree of its graph. Moreover we can strong collapse a flag complex knowing only its 1-skeleton and the resulting complex is also a flag complex.

In the previous chapter, we showed that the persistent homology of Rips filtrations can be computed very efficiently using strong collapses. However, most of the time was devoted to computing the maximal cliques of the complex prior to their strong collapse. Using the results developed in this chapter we avoid computing the maximal simplices.

After strong collapsing a flag tower as prescribed in the previous chapter, Section 3.4, the reduced sequence is also a flag tower. As previously described in Chapter 1 to compute persistence of a tower we need to transform it to an equivalent filtration. In Section 4.2, we show how to transform a flag tower to an equivalent flag filtration using again only 1-skeletons. This implies that the complete pre-processing described in the previous chapter can be performed only on the 1-skeleton, when the complex is a flag complex. This leads to a very simple and extremely efficient method.

In Section 4.1 we prove that strong collapse of a flag complex can be computed using the 1-skeleton of the complex and provide a simple algorithm to compute the 1-skeleton of the core. The algorithm to transform a flag tower to a flag filtration is discussed in Section 4.2. In Section 4.3 we provide the computational experiments.

Strong Collapse of a Flag complex

In this section, we show that the core of a flag complex K is itself a flag complex whose graph is called the core graph of K. The core graph of K can be computed from the 1-skeleton G of K in time O(n 2 v k 2 ). Although this change with respect to the Algorithm 2 in previous chapter might look minor, it is crucial in practice as the time to compute all the maximal simplices of a flag complex from its graph is exponential in the number of its vertices. We thus reduce immensely the time and space complexity of the general algorithm of previous chapter whose complexity is O(v 2 Γ 0 d + m 2 Γ 0 d), where Γ 0 is an upper bound on the number of maximal simplices incident to a vertex.

In the following lemma, we describe a condition in terms of the closed neighborhood N G [v] of a vertex v of a flag complex K under which v will be dominated by another vertex v of K. This result has been studied in another context in [START_REF] Fieux | Foldings in graphs and relations with simplicial complexes and posets[END_REF]Lemma 4.1].

Lemma 4.1.1. Let K be a flag complex. A vertex v ∈ K is dominated by v iff N G [v] ⊆ N G [v ].
Proof. If v is dominated by v , then, according to Remark 1, the set of maximal simplices that contain v is a subset of the set of maximal simplices that contain v . It follows that

N G [v] ⊆ N G [v ].
Now we prove the other direction. Let σ be a maximal simplex of K containing v. Any other vertex x of σ is joined to v by an edge

[x, v] ∈ σ. Moreover, since N G [v] ⊆ N G [v ], [v, v ] and [x, v ] are in K.
It follows that every vertex in σ has an edge with both v and v and, since K is a flag complex and σ is maximal, v must be in σ. This implies that all the maximal simplices that contain v also contain v . Hence v is dominated by v .

As mentioned before in Chapter 2, an elementary strong collapse consists in removing a dominated vertex, and it can be easily observed that removing a vertex does not affect the 'flagness' of the residual complex K \ v. In other words, if σ is a maximal clique with vertex v, the resultant clique σ \ v is still a maximal clique in K \ v. Moreover, all the other cliques that do not contain v still span the complete simplices. This implies that the core K c of a flag complex K with graph G is a flag complex of a sub-graph G c of G.

In what follows next, we describe an algorithm to compute the core graph G c ⊆ G whose flag complex is the core K c of K.

Data structure:

We represent G with its adjacency matrix M, where the rows and the columns of M represent the vertices of G. An entry M[v i ][v j ] associated with vertices v i and v j is set to 1 if either the edge [v i , v j ] ∈ G or i = j, and to 0 otherwise. Note that we set M[v i ][v j ] = 1 for i = j to be able to consider closed neighborhood. We will say that a row v is contained in another row v if the set of column indices of the non-zero entries of v is a subset of the indices of the non-zero entries of

v . It is clear that if a row v is contained in another row v , we have N G [v] ⊆ N G [v ]
and therefore the vertex v is dominated by the vertex v Core graph algorithm: Given the adjacency matrix M of G, we compute the adjacency matrix C of the core graph G c . In view of Lemma 4.1.1, we can easily compute C from M using basic row removal operations. Loosely speaking, we remove the rows of M that are contained in another row. After removing the row associated to v, we simultaneously update the matrix by removing the column associated to v. The process is iterated as long as the matrix can be reduced. Upon termination, we output the reduced matrix C, which is the adjacency matrix of the core graph G c of K. Since the core of a complex is always unique, the order in which vertices are removed does not matter [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF].

Retraction map computation:

We can easily compute the retraction map r defined in Section 3.1 using the above core graph algorithm. A row v being removed in M corresponds to a dominated vertex in K and the row which contains v corresponds to a dominating vertex. Therefore we map the dominated vertex to the dominating vertex.

Domination tests optimization:

Let us observe that, to check if a row v is dominated by some other row v , it is sufficient to compare v with its neighbors, which are at most k in number, if k denotes the maximum degree of the vertices in G.

We define a row v to be a candidate row for the next iteration if at least one of its neighbors has been removed in a previous row removal iteration. We observe that the candidate rows are the only rows that need to be considered in the domination tests of the algorithm. Indeed, a row w of M whose set of neighbors has not been modified at the previous iteration cannot be dominated by another row v of M, as w was not dominated in the previous iteration and all other vertices can only loose neighbors. This ensures that w will still remain un-dominated.

We maintain a queue, for the candidate rows (rowQueue) which is implemented as a First in First out (FIFO) queue. At each iteration, we pop out a candidate row from rowQueue for domination test. After each successful domination test, we push the new candidate rows in the queue in preparation for the subsequent iteration. In the first iteration, we push all the rows in rowQueue. Algorithm 3 gives the pseudo code of our algorithm. rowQueue ← push all rows of M (all vertices of K) 4: while rowQueue is not empty do

5: v ← pop(rowQueue) 6: N G [v] ← the non-zero columns of v 7: for w in N G [v] do 8: if N G [v] ⊆ N G [w] then 9:
Remove from M the column and the row associated to v

return M

M is now the adjacency matrix of the core of K 16: end procedure Time Complexity: Let us start by analyzing the most basic operation in our algorithm which is to determine if a row is dominated by another row. We store the rows of the matrix as sorted lists. Deciding if a sorted list is included in another sorted list (Line 8) can be done in time O(l), where l is the size of the longer list. In our case, the length of a row list is at most k + 1 where k denotes as before the maximal degree of any vertex. Hence lines 8-12 takes O(k) time.

As explained in the paragraph Domination tests optimization, each row is checked against at most k other rows. Hence the for loop (Lines 7-13) is executed at most k times. Moreover, since at each iteration we ought to remove at least one row, the total number of iterations on the rows, i.e. the number of times the while loop is executed, is at most O(n 2 v ), where n v is the total number of vertices of the complex K. It follows that the worst-case time complexity of our algorithm is O(n 2 v k 2 ).

From a Flag Tower to a Flag Filtration

In this section, we show that, thanks to the notion of strong collapses, we can efficiently turn a flag tower into a flag filtration using only edge inclusions over the 1-skeletons of the complexes.

Previous work

It is known that any general simplicial map can be decomposed into elementary inclusions and elementary contractions. Hence if we can replace an elementary contraction {{u, v} → u} by an equivalent (not necessarily elementary) inclusion, we transform a tower into an equivalent filtration. This was the philosophy introduced by Dey et al. [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF]. This idea has been further refined by Kerber and Schreiber [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF] who introduced a slightly different approach based on coning. They provided theoretical bounds on the size and time to construct the final equivalent filtration. Specifically, they proved that the size of the equivalent filtration is O(d * n * log n 0 ), where d is the maximal dimension of the complexes in the input tower and n (resp. n 0 ) the total number of elementary inclusions (resp. vertex inclusions) in the input tower [34, Theorem 2].

A new construction

We now present an algorithm that turns a flag tower into a flag filtration with the same PH. Our work builds upon the above mentioned previous works [START_REF] Dey | Computing topological persistence for simplicial maps[END_REF][START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF]. The difference is that we use strong expansion which is the inverse operation of a strong collapse. The main advantage of strong expansions is that, when the input is a flag tower, we can use the domination criterion of Lemma 4.1.1. This leads to a simple algorithm that only deals with edges. The output filtration is a flag filtration, which can be represented very compactly. Moreover, since a strong expansion is a coning, we will be able to use the theoretical results of [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF]. Now we describe our construction.

Let K i be a flag complex and G i be its 1-skeleton. We associate to K i an augmented complex K i ⊇ K i . As will be seen below, K i is also a flag complex whose 1-skeleton will be denoted by G i . Following the terminology of [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF], we call a vertex v ∈ K i to be active if it is currently not dominated. The active closed neighborhood ActN G i [v] is then defined as the set of all active vertices in

N G i [v]. Similarly, ActN G i [v \ u] denotes the set of active vertices in the closed neighborhood N G i [v] of v that are not in N G i [u]. Finally, let {[u, ActN G i [v \ u]]} denote the set of edges between u and ActN G i [v \ u].
Using the notions defined above, we now explain how to inductively construct a filtration associated to a given flag tower. The construction operates in a streaming fashion on the 1-skeleton. We distinguish two kinds of inputs: elementary inclusions (of a vertex or an edge) and elementary contractions. For i = 0, we set G 0 = ∅. We then define G i as follows.

1. if G i ∪σ -→ G i+1 is an elementary inclusion where σ is either a vertex or an edge, we set Note that G i ⊆ G i+1 and thus K i ⊆ K i+1 . We continue the construction until the end of our input tower.

G i+1 := G i ∪ σ. 2. if G i {u,v} →u -----→ G i+1 is an elementary contraction 2.1. if |ActN G i [v \ u]| ≤ |ActN G i [u \ v]|, we set G i+1 := G i ∪ {[u, ActN G i [v \ u]} and v as contracted 2.2. otherwise, we set G i+1 := G i ∪ {[v, ActN G i [u \ v]} and u as contracted. v u I G i I G i+1

Complexity Analysis:

The vertices marked contracted during our construction are exactly the same as the inactive vertices defined in [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF]. By construction, any contracted vertex will be dominated permanently in the filtration. Since such a vertex stops existing in the tower later on, its neighborhood stays the same and the vertex remains dominated. Therefore, at any point in our construction, the number of active vertices is less than the number of active vertices that are used in [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF]. Moreover, since a strong expansion is a coning, the size of the final filtration in our construction is at most that obtained by the construction prescribed in [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF]. Moreover, since we are working with 1-skeletons only, the space and time complexity of our method is much lower than that of [START_REF] Kerber | Barcodes of towers and a streaming algorithm for persistent homology[END_REF].

Let us now analyze the time complexity of the algorithm. Notice that there are two basic operations on the 1-skeleton, elementary inclusions in Line -----→ K i+1 be the first elementary contraction in the tower

T : K 0 f 0 -→ K 1 f 1 -→ ... f m-1 --→ K m .
Then there exists a complex K i+1 ⊆ K i+1 such that K i+1 K i+1 and K i+1 K i+1 .

Proof. Since f i is the first contraction Removing all the dominated vertices in N G i [v \ u] thus provides a sequence of elementary strong collapses both in K i+1 and K i+1 . By performing all such elementary strong collapses, K i+1 is eventually transformed into a complex K 0 i+1 , K i+1 K 0 i+1 and K i+1 to K i+1 , K i+1 K i+1 . See Figure 4.2 for an example of all the graphs associated to the complexes defined here.

K i = K i and G i = G i . Let G i+1 := G i ∪ {[u, ActN G i [v \ u]}
By doing so, in G i+1 we have removed all the dominated vertices from N G i [v \ u] and added edges between u and the non dominated vertices that are in N G i [v \ u]. This implies that v is dominated by u in K 0 i+1 . The elementary strong collapse of v onto u, implies K 0 i+1 K i+1 and therefore K i+1 K i+1 .

T : K 0 f 0 -→ K 1 f 1 -→ ... f m-1 --→ K m .
Then the following diagram commutes

H p (K i ) H p (K i+1 ) H p (K i+1 ) f * i i * k φ * i+1
and φ * i+1 is an isomorphism.

Here

φ i+1 := i • r : K i+1 r -→ K i+1 i -→ K i+1
is the composition of the retraction r and the inclusion i associated to corresponding strong collapses as defined in Lemma 4.2.1. i * k , f * i and φ * i+1 are homomorphisms induced by the corresponding simplicial maps.

Proof. Using the fact that f i is the first contraction, we have the inclusion K i = K i ⊆ K i+1 . Let K 0 i+1 and K i+1 be the complexes as defined in the proof of Lemma 4.2.1. Consider the following diagram of simplicial complexes, and note that i = i 1 • i 0 where i 0 and i 1 are both inclusions induced by the respective strong collapses and

r • f i := K i f i -→ K i+1 r -→ K i+1 . K i K i+1 K i+1 K 0 i+1 r• f i i k i 0 i 1
We claim that the maps φ i+1 • f i and i k are in the same contiguity class, which we denote

φ i+1 • f i ∼ i k .
Let r 0 and r 1 be the retraction maps associated with the strong collapses K 0 i+1 K i+1 and K i+1 K 0 i+1 respectively. We have i 1

• i 0 • r 0 • r 1 ∼ 1 K i+1 [3]
, where 1 K i+1 is the identity over K i+1 . Now we observe that the retraction map r 0 is the same as f i as it is the elementary contraction {u, v} → u. And the retraction map r 1 : K i+1 → K 0 i+1 is the same as the retraction map r : K i+1 → K i+1 expect for any vertex x that is dominated by v in K i+1 . For such x, r 1 (x) = v and r(x) = u as x is dominated by u in K i+1 and is mapped to u through the map r [see proof of Lemma 4.2.1]. This implies that, the composition r 0 • r 1 = r • f i for all vertices in K i or K i+1 (K i and K i+1 have the same vertex set), see Figure 4.2 for an illustration.

By replacing i 1 • i 0 by i and r 0 • r 1 by r • f i , we have i 1 • i 0 • r 0 • r 1 = i • r • f i ∼ 1 K i+1 . Now since K i ⊆ K i+1 and K i and K i+1 have the same vertex set i k = 1 K i+1 also by definition φ i+1 = i • r, therefore φ i+1 • f i ∼ i k .
Since maps in the same contiguity class are homotopic at the level of geometric realizations, the diagram in the lemma commutes.

It follows directly from the definition that φ * i+1 is an isomorphism as φ * i+1 = (i ) * • r * and (i ) * and r * both are isomorphism since (i ) and r are inclusion and retraction maps associated to strong collapse.

Proceeding by induction, Lemma 4.2.1 then immediately implies the following result. Lemma 4.2.3. Given a tower T : K 0

f 0 -→ K 1 f 1 -→ ... f m-1 --→ K m .
For each 0 ≤ i ≤ m , there exists a map φ i : K i → K i that is an isomorphism, where φ i is a composition of retraction and inclusion associated to strong collapse.

Again, using an inductive argument along with Lemmas 4.2.2 and 4.2.3, we can deduce the following result.

H p (K 1 ) H p (K 2 ) • • • H p (K m-1 ) H p (K m ) H p (K 1 ) H p (K 2 ) • • • H p (K m-1 ) H p (K m ) f * 1 φ * 1 f * 2 φ * 2 f * m-1 φ * m-1 φ * m * * *
As a consequence, the tower T : K 0

f 0 -→ K 1 f 1 -→ ... f m-1
--→ K m and the constructed filtration

F : K 0 → K 1 → ... → K m have the same persistence diagram.
Here φ i is a composition of retraction map and inclusion map associated to strong collapse (as defined in Lemma 4.2.1) and therefore an isomorphism for each i ∈ {0, • • • , m} and * indicates the induced homomorphisms.

We summarize our result in the following theorem. We write T :

K 0 f 0 -→ K 1 f 1 -→ ... f m-1
--→ K m for the given flag tower where, w.l.o.g., K 0 = ∅. and each f i is either an inclusion or an elementary contraction. The inclusions are not necessarily elementary but corresponds to an elementary inclusion on the graphs G i . We denote by d the maximal dimension of the K i s in T , and by n the total number of elementary inclusions of simplices in T , by n c the total number of elementary contractions and by n 0 the number of vertex inclusions in T .

Computational experiments

Next we describe the complete pre-processing pipeline for a tower and a general approximation scheme for any tower and then perform experiments on Rips filtrations, similar to what we did in the previous chapter. However, we use the approach developed in this chapter for our experiments.

The pre-processing pipeline. Let T : {K 1

f 1 -→ K 2 f 2 -→ • • • f (m-1)
---→ K m } be a flag tower of which we want to compute the persistence diagram. We first strong collapse the various complexes K i , i = 1, ..., m as suggested in Section 3.4. As each K i is a flag complex, the computation of its core is computed much more efficiently using only its 1-skeleton.

We then compute a core tower that connects the K c i s through induced simplicial maps. This is again an adaptation of what has been done in Chapter 3 for general simplicial complexes to the case of flag complexes. Lastly, we compute a flag filtration with the same PH as the core tower, using our approach detailed in Section 4.2. This filtration can then be sent to any algorithm that computes the persistence homology of a flag filtration [START_REF] Mozozov | Dionysus[END_REF][START_REF] Bauer | Ripser[END_REF][START_REF] Bauer | PHAT -persistent homology algorithms toolbox[END_REF][START_REF]Gudhi: Geometry understanding in higher dimensions[END_REF].

An approximation scheme. Using the above approach we compute the exact PH of the input flag tower T . However, instead of considering all the K i s and the associated simplicial maps, we can select some of the K i s we rename K 1 , ..., K q , and compose the original maps f 1 , ..., f m-1 to obtain simplicial maps f 1 , ..., f q-1 connecting the selected complexes. We thus obtain a sub-tower T and the algorithm will then compute the exact PH of T . An application of this idea has been presented for Rips filtrations in Section 3.5 of the previous chapter, which we describe again below.

Recall that, for Rips filtrations, the filtration value of a simplex is the length of the longest edge of the simplex. Given a Rips filtration, one can choose to collapse the original complexes after each edge inclusion. However, we can also choose to strong collapse the complexes less often, i.e. after several edge inclusions rather than just one. This will result in a faster algorithm but comes with a cost: the computed PD is then only approximate. We call snapshots the values of the scale parameter at which we choose to strong collapse the complex. The difference between two consecutive snapshots is called a step. We approximate the filtration value of a simplex as the value of the snapshot at which it first appears. We can observe that our algorithm will report all persistence pairs that are separated by at least one snapshot. Hence if all steps are equal to some > 0, we will compute all the persistence pairs whose lengths are at least . It follows that the l ∞ -bottleneck distance between the computed PD and the exact one is at most . If instead the ratio between any two consecutive steps is taken to a constant ρ > 1, the l ∞ -bottleneck distance will be at most log ρ after reparameterizing the filtrations on a log-log-scale [START_REF] Sheehy | Linear-size approximations to the Vietoris-Rips filtration[END_REF].

Experimental setup : Our algorithm has been implemented for Rips filtrations as a C++ module named VertexCollapser. VertexCollapser takes as input a Rips filtration and returns the reduced flag filtration. VertexCollapser can be used in two modes: in the exact mode, the output filtration has the same PD as the input filtration while, in the approximate mode to be described above, a certified approximation is returned. The output filtration can then be sent to any software that computes the PD of a Rips filtration such as the Gudhi library (the one we chose for our experiments) [START_REF]Gudhi: Geometry understanding in higher dimensions[END_REF] or Ripser [START_REF] Bauer | Ripser[END_REF]. Therefore VertexCollapser is to be considered as an ad-on to software computing PD. VertexCollapser will be available as an open-source package of a next release of the Gudhi library.

We present results on five datasets netw-sc, senate, eleg, HIV and drag 1 that are publicly available [18]. Each dataset is given as the interpoint distance matrix. The reported time includes the time of VertexCollapser and the time to compute the persistent diagram (PD). The time of VertexCollapser includes: 1. The time taken to compute the largest 1-skeleton associated to the maximum threshold value, 2. The time taken to collapse all the sub-skeletons and assemble their cores. 3. To transform them into an equivalent flag-filtration.

The code has been compiled using the compiler 'clang-900.0.38' and all computations were performed on a '2.8 GHz Intel Core i5' machine with 16 GB of available RAM. We took all steps to be equal. Parameter Step controls the quality of the approximation, if Step = 0, we obtain the exact PD, otherwise Step is an upper bound on the l ∞bottleneck distance between the output diagram and the exact one. VertexCollapser works irrespective of the dimension of the input complexes. However, the size of the complexes in the reduced filtration, even if much smaller than in the original filtration, might exceed the capacities of the PD computation algorithm. For this reason, we introduced a parameter dim and restricts PD computation to dimension at most dim. Some experimental results are reported in Table 4.1, some of them are the same as done in Table 3.2 of Chapter 3. As previously observed in Chapter 3 the reduction done by VertexCollapser is enormous as well, same as before. However, the main point to observe is that VertexCollapser is extremely fast due to its ability to work with only the 1-skeleton. The reduced complexes are small and of low dimension (column Size/Dim) compared to the input Rips complexes which are of dimensions respectively 57, 54 and 105 for the first three datasets netw-sc, senate and eleg. We also observe that, while the time taken by VertexCollapser is large for exact persistence computation, very good approximations can be obtained fast. Moreover the computing time mildly increases with the number of snapshots. This suggests that implementing the collapses in parallel would lead to further substantial improvement.

Data

Pnt Thrsld VertexCollapser +PD Size/Dim dim Pre-Time Tot-Time

Step This chapter was based on our work reported in [START_REF] Boissonnat | Computing persistent homology of flag complexes via strong collapses[END_REF].

FIGURE 5.1 -The above complex does not have any dominated vertex and thus cannot be 0-collapsed. However, by proceeding from the boundary edges, one can edge collapse this complex to a 1-dimensional complex. The 1-core obtained in this way is collapsible to a point using 0-collapse.

Efficiency of reduction.

As will be demonstrated in Section 5.4, edge collapse appears to be a very efficient tool to reduce the size of a complex while preserving its homotopy type. A simple example will help giving some intuition why edge collapse can be superior to vertex collapse. See FIGURE 5.2 -The complex on the left has two different 1-cores, the one in the middle is obtained after removing the inner edges [START_REF] Adamaszek | Complexity of simplicial homology and independence complexes of chordal graphs[END_REF][START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF] and [START_REF] Bauer | Ripser[END_REF][START_REF] Bauer | Clear and compress: Computing persistent homology in chunks[END_REF], and the one in the right by removing the outer edges [START_REF] Adamaszek | Complexity of simplicial homology and independence complexes of chordal graphs[END_REF][START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF] and [START_REF] Bauer | Ripser[END_REF][START_REF] Bauer | PHAT -persistent homology algorithms toolbox[END_REF]. Note that the one in the right can be further strong collapsed.

Simple Collapse and Persistence

In this section, we turn our attention to the general case of simple collapses (of which k-collapses are a special case) and provide one of the main result of this chapter. This can be seen as a generalization of Theorem 2 of [START_REF] Boissonnat | Strong Collapse for Persistence[END_REF].

Theorem 5.2.1. Let f : K → L be a simplicial map between two complexes K and L and let K ⊂ K and L ⊂ L be subcomplexes of K and L such that K K and L L . Then there exists a map f : K → L , induced by f , such that the persistence of f The map | f | induces a map f := r l • f • i k between the simplicial complexes K and L . Note that f can be expressed as a composition of inclusions, contractions and removals of simplices, as i k is an inclusion, f is simplicial and r l is a simple collapse. Also, for simplicial complexes, singular homology is isomorphic to simplicial homology [START_REF] Hatcher | Algebraic Topology[END_REF]Theorem 2.27] The use of singular homology in the proof is due to the lack of a simplicial map associated with the retraction (|r|) of a simple collapse. Due to the same reason, the induced map f : K → L may not be necessarily simplicial. However, as mentioned in the above proof the map f can be expressed as a combination of inclusions, contractions and removals of simplices. When a sequence of simplicial complexes contains removals of simplices, it is called a zigzag sequence. There are algorithms [START_REF] Mozozov | Dionysus[END_REF][START_REF] Maria | Zigzag persistence via reflections and transpositions[END_REF] to compute zigzag persistence but they are not as efficient as the usual algorithms for filtrations and towers.

| f | is defined as | f | := |r l || f ||i k |. Hence | f ||r k | = |r l || f ||i k ||r k |. Now observe that, since |r k | is a deformation retraction, |i k ||r k | is homotopic to the identity over |K|. It follows that |r l || f ||i k ||r k | is homotopic to |r l || f |.
In the next section, we consider the case of flag filtrations and show that we can restrict the way the edge collapses are performed so that the reduced filtration is also a flag filtration.

Edge collapse of a flag filtration

In Section 5.1, we have introduced edge collapse for general simplicial complexes and provided an easy criterion for edge-domination in a flag complex using only the 1-skeleton of the complex. In this section, we provide an algorithm to simplify a flag filtration using edge collapse and again using only the 1-skeleton of the complex.

We define a notion of removable edge to help explain how our algorithm works (Algorithm 4) and to prove its correctness. Let G be a graph and K be the associated flag complex. We say that an edge e in a graph G is removable either if it is dominated in K or if there exists a sequence of edge collapses K 1 K c such that e is dominated in the reduced complex K c . Our algorithm is based on the fact that the flag complexes K and K c are homotopy equivalent [START_REF] Welker | Constructions preserving evasiveness and collapsibility[END_REF]Lemma 2.7] and [2, Lemma 8]. If e = [u, v], we define the edge-neighborhood of an edge e ∈ G as the set EN G (e

) := {[x, y], x ∈ {u, v}, y ∈ N G ([uv])}. Algorithm. Let F : K 1 → K 2 → • • • → K n be a flag filtration and G F : G 1 → G 2 → • • • → G n
be the associated sequence of 1-skeletons. We further assume that G i → G i+1 is an elementary inclusion, namely the inclusion of a single edge we name e i+1 . The edges in E := {e 1 , ..., e n } are thus indexed by their order in the filtration and we denote by G i the subset {e 1 , ..., e i }. Our algorithm computes a subset of edges E c ⊆ E and attach to each edge in E c a new index. We thus obtain a new sequence of flag complexes F c corresponding to E c , we call the core sequence. The construction of E c and of the new indices is done so that F c has the same persistence diagram as F .

Let's give an intuitive presentation of the algorithm first. The central idea is to identify edges that appear to be non-removable at some point in the algorithm. We store such edges in a set E c . To be more specific, consider the case of the inclusion of an edge G i-1 e i -→ G i such that e i is dominated in G i : e i is thus removable in G i and is not included in E c . Suppose first that all further edges e s are dominated in G s , i < s ≤ n. Then e i remains removable and will never be put in E c . This is consistent with the fact that e i does not change the topology of the complexes K s and is therefore not required when computing persistence.

Assume now that some edge e p , i < p ≤ n, is non-dominated in G p . The status of e i , that was removable in all G s for s < p, may change to non-removable in G p . Therefore, we check whether e i is non-removable in G p (by proceeding in the reverse filtration order) and, in the affirmative, include e i in E c . In turn, the fact that e i changed from removable to non removable may change the status of the edges with smaller indices which could become non-removable after the inclusion of e i . If such edges are found, they are also included in E c . Before describing the algorithm in detail, two remarks are in order. First, we do not change the status of an edge from non-removable to removable even if it has become removable: this will enforce the output sequence to be a filtration. Second, we change the filtration values of some edges: the new filtration value of an edge is the first index at which it is found to be non-removable. The second point leads to faster computation of E c , otherwise one has to proceed backward recursively to search for new non-removable edges.

We now explain how to compute E c . See [Algorithm 4] for the pseudo-code. The main for loop on line 6 (called the forward loop) iterates over the edges in the filtration F by increasing filtration values, i.e. in the forward direction, and check whether or not the current edge e i is dominated in the graph G i . If not, we insert e i in E c and keep its original index i.

After the insertion of an edge e i in E c , we proceed to the so-called backward loop ([Lines 9-26]) and look for new non-dominated edges in G i , considering the edges by decreasing filtration values. We assign G i to a temporary graph G, and we assign the edge-neighborhood of e i in the graph G i to E nbd [Line 9 -10]. As established in Lemma 5.3.1, the search for new non-dominated edges can be restricted to E nbd . If an edge e j is not in E c and not in E nbd [Line 13-14], e j is still dominated : we then remove it from G [ Line 22]. If e j ∈ E c and e j ∈ E nbd , then we check whether it is dominated or not. If e j is dominated, we remove it from G [Line 19]. Otherwise, we insert e j in E c and assign to it the new index i, i.e. the index of the edge e i that has triggered the backward search in G i . Next we enlarge the edge-neighborhood E nbd by inserting the edge-neighbors of e j in G. We repeat this process until the last index j = 1. Upon termination of the forward loop [Line 6-30], we output E c as the final set. input : set of edges E of G F sorted by filtration value.

3:

E c ← ∅; i ← 1; 4: E nbd ← ∅ 5: G ← ∅ 6:
for e i ∈ E do For i = 1, ..., n in increasing order 7:

if e i is non-dominated in G i then 8:
Insert {e i , i} in E c .

9:

G ← G i 10:

E nbd ← EN G i (e i ) 11: j ← i -1 12:
for e j in G i do For j = (i -1), ..., 1 in decreasing order return E c E c is the 1-skeleton of the core flag filtration. 32: end procedure The computation of non-removable edges (the set E c ) is dependent on the order in which we do the backward search (the backward loop). In Algorithm 4 we chose to proceed in the reverse order of the filtration. A different choice of order might result in a different set of non-removable edges since edge collapses are order dependent as mentioned in Section 5.1.

We now prove the correctness of the above algorithm after some more definitions.

Critical Edges: Edges in E c are called critical while edges in E \ E c are called noncritical. All edges have an original index i given by the insertion order in the input filtration F . The critical edges received a second index j, called their critical index, when they are inserted in E c . By convention, if an edge is not critical and thus has never been inserted in E c , we will set its critical index to be ∞. Hence, at the end of Algorithm 4, each edge e ∈ E has two indices, an original and a critical index. To make this explicit, we denote e as e j i . Clearly i ≤ j. We further distinguish the cases i = j and i < j. If i = j, e i has been put in E c during the forward loop and we call e i a primary critical edge. If i < j, e i has been put in E c during the backward loop and we call it a secondary critical edge.

For i = 1, ..., n, we define the critical graph at index i, denoted G c i , as the graph whose edges are the edges in E c with a critical index at most i. We denote the associated flag complex as K c i .

Correctness. We now prove some lemmas to certify the correctness of our algorithm.

The following lemma justifies the fact that the search for new critical edges during the backward loop of Algorithm 4 is restricted to the neighborhood of already found critical edges. Proof

. Let e ≺ v in G, then N G [e] ⊆ N G [v ]. Plainly, N G [v ] ⊆ N G [v ] and, since e / ∈ EN G (e ), N G [e] = N G [e]. Therefore, N G [e] = N G [e] ⊆ N G [v ] implies e ≺ v in G .
The following lemma says that a non-critical edge is always removable and that a critical edge is removable until it becomes critical.

Lemma 5.3.2. Let e j i be an edge with i < j, then it is removable in all G t , i ≤ t < min(n + 1, j).

Proof. According to the algorithm, if i < j, e j i is dominated in G i (j being finite or not). 1. Let us first consider the case j = ∞. Note that e ∞ i is non-critical and let j i be the smallest primary critical index greater than i. If no such index exists, set j i = n + 1. We show by induction that e ∞ i remains removable in all G t , i ≤ t < n + 1. As shown above, it is true for t = i since e j i is dominated in G i . So assume that e j i is removable in G t-1 and consider the insertion of e t in G t , for some t < j i . By definition of j i , e t is dominated in G t , which implies that e j i is removable in G t (in the backward sequence e t , e t-1 , . . . , e i ). Consider now t = j i . Since e j i is a primary critical edge, it is non-dominated in G j i . According to the algorithm, a backward loop has been triggered at j i . During this backward loop, e ∞ i has not been inserted in E c since its second critical index is ∞. This is only possible because e ∞ i has been found to be dominated in G. Since G is initialized as G j i , it follows that e ∞ i is removable in G j i . We can now proceed in a similar way for all t, j i < t < n + 1.

2. The proof is very similar for the case i < j ≤ n. As e j i has not been inserted in E c until the backward loop triggered at index j, e j i remains removable in all G t , i ≤ t < j.

Note that our statement does not imply that a critical edge e j i , i < j ≤ n, can never be removable in G t , t ≥ j. It just means that we are sure that it will remain removable until the point it becomes critical. Lemma 5.3.3. For each i, Algorithm 4 produces a sequence of elementary edge collapses such that K i 1 K c i .

Proof. By definition, G i \ G c i = {e m t | t ≤ i, m > i} is the set of edges of G i whose critical index m is greater than i, which includes the non-critical edges (m = ∞). Any edge e m t ∈ G i \ G c i is removable in all K j , j < m by Lemma 5.3.2.

The proof of the following theorem certifying the correctness of our algorithm follows directly through the application of Lemma 5. Complexity: Write n v for the total number of vertices, n for the total number of edges and k for the maximum degree of a vertex in G n . We represent each graph G i as an adjacency list, where every vertex stores a sorted list of at most k adjacent vertices. Additionally, we store the set of edges (E and E c ) as a separate data structure. Let us now analyze the worst-case time complexity of Algorithm 4. At each step i of the forward loop [Line 6], either e i is dominated (which can be checked in O(k 2 ) time) or a backward loop is triggered [ Line 12]. The backward loop will consider all edges with (original) index at most i and check whether they are dominated or not. Writing n c for the number of primary critical edges, the worst-case time complexity is nk 2 + ∑ n c i=1 n k 2 = O(nn c k 2 ). The space complexity is O(n). In practice, n c is a small fraction of n (see Table 5.1).

Computational Experiments

Our algorithm [Algorithm 4] has been implemented for Rips filtrations as a C++ module named EdgeCollapser. Our previous preprocessing method described in Chapter 4 to simplify Rips filtrations using strong collapse is called the VertexCollapser. Both EdgeCollapser and VertexCollapser take as input a Rips filtration and return the reduced flag filtration according to their respective algorithms.

We present results on five datasets netw-sc, senate, eleg, HIV and torus. The first four datasets are publicly available [18] and are given as the interpoint distance matrix of the points. The last dataset torus has 2000 points sampled in a spiraled fashion on a torus embedded in a 3-sphere of R 4 [START_REF] Hudson | Topological inference via meshing[END_REF]. The reported time includes the time of EdgeCollapser/VertexCollapser and the time to compute the persistence diagram (PD) using the Gudhi library [START_REF]Gudhi: Geometry understanding in higher dimensions[END_REF].

The code has been compiled using the compiler 'clang-900.0.38' and all computations were performed on a '2.8 GHz Intel Core i5' machine with 16 GB of available RAM. Both EdgeCollapser and VertexCollapser work irrespective of the dimension of the complexes associated to the input datasets. However, the size of the complexes in the reduced filtration, even if much smaller than in the original filtration, might exceed the capacities of the PD computation algorithm. For this reason, we introduced, as in Ripser, a parameter dim and restricts the expansion of the flag complexes to a maximal dimension dim.

The experimental results using EdgeCollapser are summarized in Table 5.1. Observe that the reduction in the number of edges done by EdgeCollapser is quite significant. The ratio between the number of initial edges and the number of critical edges is approximately 20. If the number of edges in a graph is |E| then the size of the (k + 1)cliques O(|E| k ). Therefore the reduction in the size of k-simplices can be as large as O(20 k ). This is verified experimentally too, as the reduced complexes are small and of low dimension (column Size/Dim) compared to the input Rips-complexes which are of dimensions respectively 57, 54 and 105 for the first three datasets netw-sc, senate and eleg. 1Comparison with VertexCollapser. The same set of experimental results using VertexCollapser are summarized in Table 5.2, which is a subset of the experiments reported in the previous chapter in Table 4.1. As mentioned before VertexCollapser can be used in two modes: in the exact mode (step=0), the output filtration has the same PD as the input filtration while, in the approximate mode (step>0), a certified approximation is returned. For comparison, we use the results in Table 5.2 are of exact mode, for experiments in approximate mode please refer to Table 4.1.

It can be seen that EdgeCollapser is faster than VertexCollapser by approximately two orders of magnitude. The main reason for this is the efficient preprocessing algorithm behind EdgeCollapser. As it can be noticed in some cases, the reduction obtained using by VertexCollapser is better than using EdgeCollapser, but even in those cases EdgeCollapser is faster than VertexCollapser.

In terms of size reduction, EdgeCollapser either outperforms VertexCollapser by a big amount or is comparable. Some intuition can be gained from the case of torus. This is a well distributed point sets sampled from a manifold without boundary. The fact that there is no boundary implies that there are only few dominated vertices, which dramatically reduces the capacity of VertexCollapser to collapse. At appropriate scale the flag complex of such point sets does not contain many dominated vertices. It is due to the fact that usually the vertices that are first dominated, lie towards a boundary. So, intuitively a strong collapse begins from a boundary of the manifold and retracts homotopically towards 'center'. To better grasp this fact, one can play with examples of well distributed points on a circle or a sphere (without boundary) and on a disk (with boundary). Remarkably, EdgeCollapser does not face this problem. The experimental finding confirms our intuition and EdgeCollapser performs much better than VertexCollapser in this case.

EdgeCollapser computes the exact PD of the input filtration while VertexCollapser has an exact and an approximate modes, Results in Table 5.2 are obtained using the exact mode of VertexCollapser, while results in Table 4 Comparison with Ripser. As in both previous chapters (Chapter 3 and Chapter 4 we provide the same experimental results using Ripser [START_REF] Bauer | Ripser[END_REF]. Ripser computes the exact PD associated to the input filtration up to dimension dim. Again EdgeCollapser (as well as VertexCollapser) are not really competitors of Ripser since they act more as a preprocessing of the input filtration and do not compute Persistence Homology. Hence they can be associated to any software computing flag filtrations. Nevertheless, we again mention the results using Ripser2 to demonstrate the benefit of using EdgeCollapser.

Results are presented in Table 5.3. The main observation is that, in most of the cases, EdgeCollapser computes PD in all dimensions and outperforms Ripser, even when we restrict the dimension of the input filtration given to Ripser.

Data

Discussion

In this chapter, we introduced the notion of k-collapse which is an extension of the notion of strong collapse. We studied the special case of edge collapses in more detail and provided a novel approach to simplify a flag filtration to a smaller flag filtration using edge collapse. Through experiments we show that our approach outperforms all other approaches including the strong collapse approach described in previous chapters.

The algorithm (Algorithm 4) described in this chapter performs exact reduction of a flag filtration to a flag filtration. However, as we have mentioned it can be easily adapted to perform an approximate reduction. Such an adaptation should lead to even more efficient computation of PH.

Similarly as in the case of strong collapses in general it seems difficult to provide a theoretical bound on the amount of reduction done by edge collapse. And we would like to explore this question specially in the setting of random simplicial complexes as a future research topic.

This chapter is based on an article accepted in the proceedings of "36th International Symposium on Computational Geometry (SoCG), 2020".

Chapter 6 Conclusion

We briefly summarize the approaches developed in this thesis and discuss some possible future work.

We introduced two new approaches to improve the computation of the PH of a given sequence of simplicial complexes (either a filtration, a tower, or a zigzag sequence). Both approaches are closely related, 1. We used the notion of strong collapse introduced by J. Barmak and E. Minian [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF] to simplify the complexes of the input sequence.

2. We extended the notion of domination of a vertex to any k-simplex and then used edge collapses to simplify flag filtrations.

Numerous experiments performed on publicly available data showed that both methods beat the state of the art methods to compute persistent homology. Our experiments show that our approach using edge collapses performs the best among all approaches. However, both methods can be used in combination as they are complementary. In case of general simplicial complexes our methods require a representation of the complexes consisting only of the maximal simplices. And in the case of flag complexes they can be performed over the 1-skeleton. The gain in time by applying our method is enormous especially in high dimensions.

Futute Work. Both strong collapse and edge collapse have shown promises to solve computational problems in Topology. Again their strength comes from their characterization in terms of maximal simplices or the neighborhoods of a graph (in case of flag complex). Below we mention a few problems which we think should be considered as future work.

-As mentioned in the discussion section of Chapter 3 and Chapter 5, we would like to have a theoretical bound on the reduction size of both strong collapse and edge collapse. Obtaining such bounds in general seems difficult. A possibly easier goal would be to estimate the size reduction in the case of random simplicial complexes [START_REF] Kahle | Random simplicial complexes[END_REF]. There are many different models of random simplicial complexes, each model should provide a different insight about reduction capabilities of these collapses. Many variants of this problem have been studied in the case of simple collapse [START_REF] Kahle | Random simplicial complexes[END_REF].

-As shown in Section 5.1 of Chapter 5, the 1-core corresponding to edge collapse is not unique. We conjecture that it is NP-complete to compute an optimal 1-core. And therefore the problem of computing an approximate 1-core by some constant factor of the optimal 1-core could be well defined and appropriate for providing theoretical guarantees about the reduction achieved by edge collapse.

xv List of Figures 1 . 1

 11 Point cloud sampled from a torus. . . . . . . . . . . . . . . . . . . . . . 1.2 Left: Point set in R 2 and Right: Its clusters represented in different colors. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 A regression line fitting the given point set. . . . . . . . . . . . . . . . . 1.4 Points in R 2 and euclidean balls around them, with increasing radii. . 1.5 At no scale the union of balls can capture both the loops. . . . . . . . . 1.6 Union of balls and the associated Čech complex. . . . . . . . . . . . . . 1.7 Union of restricted balls and the associated alpha complex. The black edges are the 1-cells of the Voronoi cell decomposition that restrict the balls around the points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 A Persistence Diagram: Different colors denote different dimensions of the homology groups. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 On the left is the Čech complex and the right is the Rips complex. . . . 2.2 Maps φ and ψ are contiguous. . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Examples of simple collapses. . . . . . . . . . . . . . . . . . . . . . . . .

4. 1 4 . 2

 142 Demonstration of strong expansion: On the left we have the active neighborhoods of the vertex u (in red) and of v (in blue) in the graph G i . The graphs G i might have other vertices and edges, here we have zoomed into the local active neighborhoods of u and v. On the right, we have the local neighborhoods of u and v in G i+1 after conning v to the active neighborhood of u. . . . . . . . . . . . . . . . . . . . . . . . . xvi An example of the graphs associated to the complexes defined in the proof of Lemma 4.2.1. Vertices in red are dominated (inactive) and in green are active. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. 1 39 3. 2 47 4. 1 5 . 2

 139247152 From left to right M, N (M) and N 2 (M). . . . . . . . . . . . . . . . . . The columns are, from left to right: dataset (Data), number of points (Pnt), maximum scale parameter (Threshold), dimension of the VR Complex (Dim), time taken to compute the VR complex (Rips-Comp-Time), total time (Total-Time), parameter step (Step) and total number of snapshots used (TotSnaps). All times are averaged over five trials. . 47 3.3 The columns are, from left to right: dataset (Data), number of points (Pnt), maximum scale parameter (Threshold), input dimension for Ripser (Dim), total time taken by Ripser (Time). Most results are averaged over five trials except the longer ones. ∞ in the Time column means that the experiment ran longer than 12hrs or crashed due to memory overload. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), number of simplices (Size) and dimension of the final filtration (Dim), parameter (dim), time (in seconds) taken by VertexCollapser, total time (in seconds) including PD computation (Tot-Time), parameter Step and the number of snapshots used (Snaps). K and M in the size columns are thousands and millions respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.2 The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), parameter (dim), Time is the total time (in seconds) taken by Ripser. ∞ means that the experiment ran longer than 12 hours or crashed due to memory overload. 62 5.1 The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), Initial number of edges/Critical (final) number of edges Edge(I)/Edge(C), number of simplices (Size) and dimension of the final filtration (Dim), parameter (dim), time (in seconds) taken by Edge-Collapser and total time (in seconds) including PD computation (Tot-Time). K and M in the size columns are thousands and millions respectively. . . . . . . . . . . . . 72 xviii The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), number of simplices (Size) and dimension of the final filtration (Dim), parameter (dim), time (in seconds) taken by VertexCollapser, total time (in seconds) including PD computation (Tot-Time), parameter Step (linear approximation factor) and the number of snapshots used (Snaps). *The last experiment (torus) could not finish (>12hrs) the preprocessing due to large number of snapshots and the size of the complex. K and M in the size columns are thousands and millions respectively. . . . . . . . . 73 5.3 The first three columns are as in

FIGURE 1 . 1 -

 11 FIGURE 1.1 -Point cloud sampled from a torus.

FIGURE 1 . 2 -

 12 FIGURE 1.2 -Left: Point set in R 2 and Right: Its clusters represented in different colors.

FIGURE 1 . 3 -

 13 FIGURE 1.3 -A regression line fitting the given point set.

FIGURE 1 . 4 -

 14 FIGURE 1.4 -Points in R 2 and euclidean balls around them, with increasing radii.

FIGURE 1 . 5 -

 15 FIGURE 1.5 -At no scale the union of balls can capture both the loops.

  persistence diagram, see Figure 1.8 for an example. In the same paper [27], Edelsbrunner et. al. provided a simple and fast algorithm to compute the persistence diagram as well.

FIGURE 1 . 6 -

 16 FIGURE 1.6 -Union of balls and the associated Čech complex.

FIGURE 1 . 7 -

 17 FIGURE 1.7 -Union of restricted balls and the associated alpha complex. The black edges are the 1-cells of the Voronoi cell decomposition that restrict the balls around the points.

FIGURE 1 . 8 -

 18 FIGURE 1.8 -A Persistence Diagram: Different colors denote different dimensions of the homology groups.

3 .

 3 Given X = R, i.e. the set of real numbers, the set U = { (a, b)| a < b; a, b ∈ R} of union of open intervals in R is a topology on R, called the standard topology.

  here c is the center and is the radius of the ball. If we replace the inequality ||x -c|| ≤ with the strict inequality ||x -c|| < , then we call the set an open dball, denoted as B o (c, ). The open ball extends the notion of the open interval (a, b) to the higher dimensional Euclidean space. If X = R d and U is the set of union of open balls in R d , then U defines a topology on R d and is called the standard topology on R d .

Figure 2 .

 2 Figure 2.1 is an example of a Čech (bottom left) and a Rips(bottom right) complex of a point set.

FIGURE 2 . 1 -

 21 FIGURE 2.1 -On the left is the Čech complex and the right is the Rips complex.

  Figure 2.4 is an example of a simple collapse and expansion.

FIGURE 2 . 3 -

 23 FIGURE 2.3 -Examples of simple collapses.

Definition 2 . 3 . 5 .

 235 Given an edge [u, v], the associated simplicial map r [u,v] defined by r(x) = x; if x / ∈ {u, v}, r(x) = u; if x ∈ {u, v} is called an edge contraction.

FIGURE 2 . 4 -

 24 FIGURE 2.4 -The edge[u, v] satisfies the link condition. The complex (in the right) which is the image of an edge contraction may not be a subcomplex of the original complex K. As the triangle [p, q, u] doesn't exist in K.

  a standard p-simplex, whose vertices v i are the unit vectors along the coordinate axes of R d . Definition 2.4.7.

Figure 2 .

 2 5 is an illustration of this problem.

FIGURE 2 . 5 -

 25 FIGURE 2.5 -At no scale the union of balls can capture both the loops.

FIGURE 2 . 6 -

 26 FIGURE 2.6 -A sequence of simplicial complexes connected through inclusions.

  through homomorphisms {-→} between them. A persistence module arising from a sequence of simplicial complexes captures the evolution of the topology of the sequence. For two integers b and d, 1 ≤ b ≤ d ≤ n, we can define an interval module I[b, d] by assigning V i to F when i ∈ [b, d], and to the null space otherwise. The maps between any two F vector spaces are identity and are zero otherwise. For example

  c(a, b) = ab ∞ ; if either a or b or both are not on the diagonal, c(a, b) = 0; Otherwise The points in the dgm(V) can be transformed to log scale by mapping a point

Theorem 2 . 5 . 4 .

 254 Let P ⊂ R d be a point set and {C } and {R } be the filtrations of Čech and Rips complexes for increasing values of 0 ≤ ∈ R, then d B (log(dgm(C )), log(dgm(R ))) ≤ √ 2

Remark 3 . 1 . 1 .Definition 3 . 1 . 2 .

 311312 A vertex v ∈ K is dominated by another vertex v ∈ K, if and only if all the maximal simplices of K that contain v also contain v[START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]. An elementary strong collapse is the deletion of a dominated vertex v from K, which we denote with K e K \ v.

Figure 3 .

 3 Figure 3.1 illustrates an easy case of an elementary strong collapse.

Theorem 3 . 2 . 2 .FIGURE 3 . 2 -

 32232 FIGURE 3.2 -Left: K (in grey), Right: N (K) (in grey) and N 2 (K) (in red). N 2 (K) is isomorphic to a full-subcomplex of K highlighted in red on the left.

  complex Dimension of the complex across filtrations

Algorithm 3

 3 Core graph algorithm 1: procedure CORE(M) 2:input : the adjacency matrix M of the graph of a flag complex K 3:

10 :

 10 push all the entries of N G (v) to rowQueue if not pushed before

FIGURE 4 . 1 -

 41 FIGURE 4.1 -Demonstration of strong expansion: On the left we have the active neighborhoods of the vertex u (in red) and of v (in blue) in the graph G i . The graphs G i might have other vertices and edges, here we have zoomed into the local active neighborhoods of u and v. On the right, we have the local neighborhoods of u and v in G i+1 after conning v to the active neighborhood of u.

FIGURE 4 . 2 -

 42 FIGURE 4.2 -An example of the graphs associated to the complexes defined in the proof of Lemma 4.2.1. Vertices in red are dominated (inactive) and in green are active.

Lemma 4 . 2 . 2 .

 422 Let f i : K i {u,v} →u -----→ K i+1 be the first elementary contraction in the tower

Theorem 4 . 2 . 1 .

 421 The following diagram commutes and all the vertical maps φ * i are isomorphisms.

Theorem 4 . 2 . 2 .

 422 There exists a filtration F : K 0 → K 1 → ... → K m , where the inclusions are not necessarily elementary, such that T and F have the same persistence diagram and the size of the filtration |K m | is at most O(d * n * log n 0 ). Moreover, F is a flag filtration which can be computed from T using only the 1-skeletons G i s of the K i s. The time complexity of the algorithm to compute the 1-skeleton of F is O(|G m | + n c * k 3 ) time and its space complexity O(n 0 * k), where G m denotes the 1-skeleton of K m and k is an upper bound on the degree of the vertices in G m .

Figure 5

 5

  Since homotopic maps induce identical homomorphisms on the corresponding homology groups [31, Proposition 2.19], we deduce that | f | * |r k | * = |r l | * | f | * (commutativity). Also, since |r k | * and |r l | * are induced by deformation retractions, they are isomorphisms on their respective singular homology groups. We have thus proved that the above diagram commutes and that the vertical maps |r k | and |r l | are isomorphisms. This implies that the two maps | f | : |K| → |L| and | f | : |K | → |L | have the same singular persistent homology.

Algorithm 4

 4 Core flag filtration algorithm 1: procedure CORE-FLAG-FILTRATION(E) 2:

Lemma 5 . 3 . 1 .

 531 Let e be an edge in a graph G and let e be a new edge and G := G ∪ e . If e is dominated in G and e / ∈ EN G (e ), then e is dominated in G .

3 . 3 and 1 . 5 . 3 . 1 .Using Lemma 5 . 3 . 3 ,

 331531533 Theorem 5.2.Theorem Let F : K 1 → K 2 → • • • → K n be a flag filtration and G F : G 1 → G 2 → • • • → G nbe the associated sequence of 1-skeletons, such that G i → G i+1 is an elementary inclusion of an edge e i+1 . Let G c i be the critical graph and K c i be its flag complex as defined before. Then the associated flag filtration of the critical edges, F c :K c 1 → K c 2 → • • • → K c nhas the same persistence diagram as F .Proof. Let us consider the following diagram of the geometric realizations of the flag complexes for any i ∈ {1, ..., n}, where K c i is the flag complex of the critical graph G c i . there is an edge collapse and therefore a simple collapse from K i to K c i and from K i+1 to K c i+1 . And |r i | and |r i+1 | are the deformation retractions induced by the corresponding edge collapses. The equivalence of the persistence modules then follows directly from the application of Theorem 5.2.1.

  The cost of inserting and removing an edge from such an adjacency list is O(k). Since the size of N G[v] is at most k for any vertex v, the cost of computing N G [e] for an edge e is O(k). Checking if an edge e is dominated by a vertex v ∈ N G [e] reduces to checking whether N G [e] ⊆ N G [v], see Lemma 5.1.2. Since all the lists are sorted, this operation takes O(k) time per vertex v, hence O(k 2 ) time in total.

Table 5

 5 .2 and then, from left to right: parameter (dim), Time is the total time (in seconds) taken by Ripser. ∞ means that the experiment ran longer than 12 hours or crashed due to memory overload. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

xix Dedicated to my village and river Surhar.

Table 3 .

 3 3 contains the results of Ripser. By comparing the tables, PH-Collapser clearly outperforms Ripser by a huge margin considering that we compute the persistence diagram until the full dimension. Ripser performs quite well for computing PD in low-dimensions, however as we move to intermediate dimensions it slows down quite considerably and in some cases (dimension above 7) the size of the complex is so huge that Ripser crashed due to memory overload. In Table3.3, we provide the running time of Ripser with increasing dimension of the PD computed.

			Val		Val	Val
				Dim Time Dim Time Dim Time
	netw-sc 379	4.5	4	3.8s	5	21.5s	7	357s
	"	"	5.5	4	25.3s	5	231.2s	6	∞
	senate 103 0.415	3	0.52s	4	5.9s	5	52.3s
	"	"	"	6	406.8s	7	∞
	eleg	297	0.3	3	8.9s	4	217s	5	∞
	TABLE 3.3 -The columns are, from left to right: dataset (Data), number
	of points (Pnt), maximum scale parameter (Threshold), input dimen-
	sion for Ripser (Dim), total time taken by Ripser (Time). Most results
	are averaged over five trials except the longer ones. ∞ in the Time
	column means that the experiment ran longer than 12hrs or crashed
				due to memory overload.

  1, and the computation and comparison of ActNG i [v \ u] and ActN G i [u \ v] in Lines 2.1 and2.2. Elementary inclusions can be performed in constant time O(1). To computeActN G i [v \ u] we need to compute N G i [v], N G i [u] and the subset of vertices that are dominated (inactive) in N G i [v \ u]. We can access N G i [v] and N G i [u] in constant time O(1) and compute the set-difference N G i [v \ u] in O(k log k) time,where k is the maximum degree of a vertex. Finally computing the dominated vertices inN G i [v \ u] can be done in O(k 3 ) time as |N G i [v \ u]| ≤ k. Therefore computing ActN G i [v \ u] and ActN G i [u \ v] takes O(k 3 ) time.Since the size of active relative closed neighborhoods are bounded by k, for each elementary contraction, we include at most k edges in O(k) time. It follows that the worst-case time complexity for each elementary contraction is O(k 3 ). conclude that the time complexity of the algorithm is O(|G m | + n c * k 3 ) where n c is the number of elementary contractions in the input tower and |G m | is the size of the 1-skeleton of the output flag filtration. The space complexity of our construction is O(n 0 * k) which is the size of a sparse adjacency matrix of a flag complex with n 0 vertices. Finally we prove few lemmas and state our main result Theorem 4.2.2 to certify the correctness of the output of our construction.

	We Correctness: Lemma 4.2.1. Let f i : K i	{u,v} →u

  be the graph defined in the construction Line 2.1. By construction, contracting v to u in both graphs G i and G i+1 yields the same graph G i+1 .Let x ∈ ActN G i [v \ u]. We observe that adding the edge [ux ] to G i does not change the fact that all x ∈ {N G i [v \ u] \ ActN G i [v \ u]} are still dominated in G i+1 since the addition of [ux ] only adds neighbors to N G i [x ] and N G i [u]. Also, x is still dominated in G i+1 as well. Since the only vertex whose domination can change is the one that was dominated by v and the contraction {u, v} → u transfers the neighborhood of v to u and therefore x would now be dominated by u.

TABLE 4 .

 4 We again compare our results with Ripser. As mentioned before in Chapter 3, Ripser[START_REF] Bauer | Ripser[END_REF] is the state of the art software to compute persistent diagrams of Rips filtrations. It computes the exact PD associated to the input filtration up to dimension dim. Although VertexCollapser is more complementary to Ripser than a competitor, we run Ripser 1 on the same datasets as in Table4.1 to demonstrate the benefit of using VertexCollapser.Results are presented in Table4.2. The main observation is that Ripser performs quite well in low dimensions but its ability to handle higher dimensions is limited.

	Snaps

1 -The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), number of simplices (Size) and dimension of the final filtration (Dim), parameter (dim), time (in seconds) taken by VertexCollapser, total time (in seconds) including PD computation (Tot-Time), parameter Step and the number of snapshots used (Snaps). K and M in the size columns are thousands and millions respectively.

Comparison with Ripser:

TABLE 4 .

 4

2 -The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), parameter (dim), Time is the total time (in seconds) taken by Ripser. ∞ means that the experiment ran longer than 12 hours or crashed due to memory overload.

  Let us consider the following diagram between the geometric realizations of the complex |K|, |L|, |K | and |L |. Here |r k | and |r l | are the deformation retractions on the geometric realizations associated with the simple collapse and |i k | and |i l | are the inclusion maps. H o p () denotes the singular homology and * is the induced homomorphisms by the corresponding continuous maps. The map

	|K|	| f |	|L|
	|i k |	|r k |	|i l |	|r l |
	|K |	| f |	|L |
	and the associated diagram after computing the p-th singular homology groups
	H o p (|K|)	| f | *	H o p (|L|)
	|i k | *	|r k | *		|i l | *	|r l | *
	H o p (|K |)	| f | *	H o p (|L |)

* : H p (K) → H p (L) and f * : H p (K ) → H p (L ) are the same for any integer p ≥ 0. The induced map f may not be simplicial. Nevertheless, it can be expressed as a combination of inclusions, contractions and removals of simplices.

Proof.

  . This implies that the persistent singular homology | f |

* : H o p (|K |) → H o p (|L |) and the persistent simplicial homology f * : H p (K ) → H p (L ) are equivalent. Therefore, the persistent simplicial homologies f * : H p (K) → H p (L) and f * : H p (K ) → H p (L ) are equivalent.

  .1 of Chapter 4 are obtained using the approximate mode. In both cases, EdgeCollapser performs much better than VertexCollapser. It would be easy to implement an approximate version of EdgeCollapser similarly to what has been done for VertexCollapser. Instead of triggering the backward loop of the algorithm [Line12-26] at each primary critical edge we find, we can trigger the backward loop at certain snapshot values only. See Section 4.3 of Chapter 4 for more details on the approximate methodology and description of snapshot.

	Data	Pnt Thrsld	EdgeCollapser +PD Edge(I)/Edge(C) Size/Dim dim Pre-Time Tot-Time
	netw-sc 379	5.5	8.4K/417	1K/6	∞	0.62	0.73
	senate	103	0.415	2.7K/234	663/4	∞	0.21	0.24
	eleg	297	0.3	9.8K/562	1.8K/6	∞	1.6	1.7
	HIV	1088	1050	182K/6.9K	86.9M/?	6	491	2789
	torus	2000	1.5	428K/14K	44K/3	∞	288	289

TABLE 5 .

 5 1 -The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), Initial number of edges/Critical (final) number of edges Edge(I)/Edge(C), number of simplices (Size) and dimension of the final filtration (Dim), parameter (dim), time (in seconds) taken by Edge-Collapser and total time (in seconds) including PD computation (Tot-Time). K and M in the size columns are thousands and millions respectively.

	Data	Pnt Thrsld	VertexCollapser +PD Size/Dim dim Pre-Time Tot-Time Step Snaps
	netw-sc 379	5.5	175/3	∞	366.46	366.56	0	8420
	senate	103	0.415	417/4	∞	15.96	15.98	0	2728
	eleg	297	0.3	835K/16	∞	518.36	540.40	0	9850
	HIV	1088	1050	127.3M/?	4	660	3,955	4	184
	torus	2000	1.5		4	∞*	∞	0	428K

TABLE 5 .

 5 2 -The columns are, from left to right: dataset (Data), number of points (Pnt), maximum value of the scale parameter (Thrsld), number of simplices (Size) and dimension of the final filtration (Dim), parameter (dim), time (in seconds) taken by VertexCollapser, total time (in seconds) including PD computation (Tot-Time), parameter Step (linear approximation factor) and the number of snapshots used (Snaps). *The last experiment (torus) could not finish (>12hrs) the preprocessing due to large number of snapshots and the size of the complex. K and M in the size columns are thousands and millions respectively.

TABLE 5 .

 5 3 -The first three columns are as in Table5.2 and then, from left to right: parameter (dim), Time is the total time (in seconds) taken by Ripser. ∞ means that the experiment ran longer than 12 hours or crashed due to memory overload.

		Pnt Threshold	Val dim Time dim Time dim Time Val Val
	netw-sc 379	5.5	4	25.3	5	231.2	6	∞
	senate	103	0.415	3	0.52	4	5.9	5	52.3
	"	"	"	6	406.8	7	∞
	eleg	297	0.3	3	8.9	4	217	5	∞
	HIV	1088	1050	2	31.35	3	∞
	torus	2000	1.5	2	193	3	∞

The theoretical time complexity to compute PH is O(n ω ), where ω ≤

2.4 is the matrix multiplication exponent[START_REF] Milosavljevic | Zigzag persistent homology in matrix multiplication time[END_REF][START_REF] Gall | Powers of tensors and fast matrix multiplication[END_REF]. However, most practical algorithms has time complexity O(n 3 ).

This could be seen as an extension of the same result about strong collapse preserving the PH of sequence of simplicial complex.

When we use the -cgudhi option, Sophia reports two computation times. The first one is the total time taken by Sophia which includes (1) reading the tower, (2) transforming it to a filtration and (3) computing PD using Gudhi. The second reported time is just the time taken by Gudhi to compute the exact PD of the input filtration. In our comparisons, we report the total time taken by Sophia.

We used the command <./ripser inputData -format distances -threshold inputTh -dim inputDim >.

The sizes of the complexes are so big that we could not compute the exact number of simplices.

We used the command <./ripser inputData -format distances -threshold inputTh -dim inputDim >.

Acknowledgements

This thesis is an outcome of a collaborative effort and has a unique story behind it, like almost all other theses. It is almost impossible to thank each and everyone who has been part of this journey but I'll try my best to do so and if I could not mention someone please forgive me.

Chapter 5

Edge Collapse And Persistence

In this chapter, we extend the notions of dominated vertex and strong collapse of a simplicial complex discussed and used for PH computation in the previous chapters. We say that a simplex (of any dimension) is dominated if its link is a simplicial cone. Domination of edges appear to be very powerful and we study it in the case of flag complexes in more detail. We show that edge collapse (removal of dominated edges) in a flag complex can be performed using only the 1-skeleton of the complex. Furthermore, the residual complex is a flag complex as well.

Edge collapses do not have an associate simplicial maps like strong collapses. However, we show that similar to the case of strong collapses, we can use edge collapse to reduce a flag filtration F to a smaller flag filtration F c with the same persistence.

Here again, we only use the 1-skeletons of the complexes. To be able to use edge collapse to simplify a filtration, we prove a much more general result and show that simple collapses preserves persistence, a result that could be seen as an extension of Theorem 3.4.1 of Chapter 3.

The resulting method to compute F c is simple and extremely efficient and, when used as a preprocessing for persistence computation, leads to gains of several orders of magnitude with respect to the state-of-the-art methods (including our previous approach using strong collapse). The method is exact, irrespective of dimension, and improves performance of persistence computation even in low dimensions. Again this is demonstrated by numerous experiments on publicly available data.

In Section 5.1 we define Edge collapse and discuss some of its theoretical and algorithmic properties. In Section 5.2 we prove that simple collapse preserves the persistence of a sequence of simplicial complex. The algorithm to simplify a flag filtration to a smaller flag filtration using edge collapse is described in Section 5.3. In Section 5.4 we provide some computational experiments.

Edge Collapse

In this section, we first extend the definition of a dominated vertex introduced in [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF] to simplices of any dimension. Given a simplex σ ∈ K, we denote by Σ σ the set of maximal simplices of K that contain σ. The intersection of all the maximal simplices in Σ σ will be denoted as Σ σ := τ∈Σ σ τ. Dominated simplex. A simplex σ in K is called a dominated simplex if the link lk K (σ) of σ in K is a simplicial cone, i.e. if there exists a vertex v / ∈ σ and a subcomplex L of K, such that lk K (σ) = v L. We say that the vertex v is dominating σ and that σ is dominated by v , which we denote as σ ≺ v .

k-collapse. Given a complex K, the action of removing a dominated k-simplex σ from K is called an elementary k-collapse, denoted as K k {K \ σ}. A series of elementary k-collapses is called a k-collapse, denoted as K k L. We further call a complex K k-collapse minimal if it does not have any dominated k simplices. A subcomplex

The notion of k-collapse is the same as the notion of extended collapse introduced in [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF]. We give it a different name to indicate the dependency on the dimension. A 0-collapse is a strong collapse as introduced in [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF]. A 1-collapse will be called an edge collapse.

It is not hard to see that an elementary simple collapse of a k-simplex σ is a k-collapse, as it is dominated by the vertex v = τ \ σ, where τ is the unique coface containing σ.

Each k-collapse can be decomposed into a sequence of elementary simple collapses and therefore k-collapses preserve the simple homotopy type [START_REF] Welker | Constructions preserving evasiveness and collapsibility[END_REF]Lemma 2.7] and [2, Lemma 8]. Therefore, like simple collapses, k-collapses induce a strong deformation retract as well on the geometric realization.

The following lemma extends a result in [START_REF] Barmak | Strong homotopy types, nerves and collapses[END_REF] to general k-collapse. It shows that the domination of a simplex can be characterized in terms of maximal simplices.

by definition. This implies that for any maximal simplex τ in st K (σ), v ∈ τ. Therefore, v ∈ Σ σ . For the reverse direction, let v ∈ Σ σ . Hence, for any maximal simplex τ in st K (σ), we have v ∈ τ. Now as v / ∈ σ, v belong to all the simplices τ \ σ, and thus lk K (σ) = v L where L = (τ \ σ) \ v . Hence σ ≺ v iff v ∈ Σ σ . Lemma 5.1.1 has important algorithmic consequences. To perform a k-collapse, one simply needs to store the adjacency matrix between the k-simplices and the maximal simplices of K.

Next we study the special case of a flag complex K and characterize the domination of a simplex σ of a flag complex K in terms of its neighborhood. Lemma 5.1.2. Let σ be a simplex of a flag complex K. Then σ will be dominated by a vertex v if and only if

and let τ be a maximal simplex of K that contains σ. For a vertex x ∈ τ and for any vertex v ∈ σ, the edge

Every vertex in τ is thus linked by an edge to v and, since K is a flag complex and τ is maximal, v must be in τ. This implies that all the maximal simplices that contains σ also contain v . Hence σ is dominated by v .

Consider the other direction. If σ ≺ v , by Lemma 5.1.1, all the maximal simplices that contain σ also contain v . This implies N G [σ] ⊆ N G [v ].

Lemma 5.1.2 is a generalisation of Lemma 1 in [START_REF] Boissonnat | Computing persistent homology of flag complexes via strong collapses[END_REF]. The next lemma, though elementary, is of crucial significance. Both lemmas show that edge collapses are well-suited to flag complexes. Lemma 5.1.3. Let K be a flag complex and let L be any subcomplex of K obtained by edge collapse. Then L is also a flag complex.