### Journal Articles, Conference Proceedings and Preprints

**Title**A Polynomial Time Algorithm to Compute Quantum Invariants of 3-manifolds with Bounded First Betti Number

**Authors**

*Clément Maria, Jonathan Spreer*

**Conference**Symposium on Discrete Algorithms (SoDA) 2017: 2721-2732

**Abstract**In this article, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV4,q, using the dimension of the first homology group of the manifold as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4,q is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the extremely large family of 3-manifolds with first homology group of bounded rank. Our algorithm is easy to implement and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3- manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets we are able to roughly double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4,q to be added to the short list of standard properties (such as orientability, connectedness, Betti numbers, etc.) that can be computed ad-hoc when first investigating an unknown triangulation.

**Cite**BibTex on the DBLP

**DOI:**10.1137/1.9781611974782.180

**Title**Admissible Colourings of 3-manifold Triangulations for Turaev-Viro Type Invariants

**Authors**

*Clement Maria, Jonathan Spreer*

**Conference**European Symposium on Algorithms (ESA) 2016: 64:1-64:16

**Abstract**Turaev-Viro invariants are amongst the most powerful tools to distinguish 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them rely on the enumeration of an extremely large set of combinatorial data defined on the triangulation, regardless of the underlying topology of the manifold. In the article, we propose a finer study of these combinatorial data, called admissible colourings, in relation with the cohomology of the manifold. We prove that the set of admissible colourings to be considered is substantially smaller than previously known, by furnishing new upper bounds on its size that are aware of the topology of the manifold. Moreover, we deduce new topology-sensitive enumeration algorithms based on these bounds. The paper provides a theoretical analysis, as well as a detailed experimental study of the approach. We give strong experimental evidence on large manifold censuses that our upper bounds are tighter than the previously known ones, and that our algorithms outperform significantly state of the art implementations to compute Turaev-Viro invariants.

**Cite**BibTex on the DBLP

**DOI:**10.4230/LIPIcs.ESA.2016.64

**Title**Computing Zigzag Persistent Cohomology

**Authors**

*Clement Maria, Steve Oudot*

**Preprint**arXiv:1608.06039 2016

**Abstract**Zigzag persistent homology is a powerful generalisation of persistent homology that allows one not only to compute persistence diagrams with less noise and using less memory, but also to use persistence in new fields of application. However, due to the increase in complexity of the algebraic treatment of the theory, most algorithmic results in the field have remained of theoretical nature. This article describes an efficient algorithm to compute zigzag persistence, emphasising on its practical interest. The algorithm is a zigzag persistent cohomology algorithm, based on the dualisation of reflections and transpositions transformations within the zigzag sequence. We provide an extensive experimental study of the algorithm. We study the algorithm along two directions. First, we compare its performance with zigzag persistent homology algorithm and show the interest of cohomology in zigzag persistence. Second, we illustrate the interest of zigzag persistence in topological data analysis by comparing it to state of the art methods in the field, specifically optimised algorithm for standard persistent homology and sparse filtrations. We compare the memory and time complexities of the different algorithms, as well as the quality of the output persistence diagrams.

**Cite**BibTex on the DBLP

**arXiv:**1608.06039

**Title**The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology

**Authors**

*Jean-Daniel Boissonnat, Tamal K. Dey, Clément Maria*

**Journal**Algorithmica 73(3): 607-619 (2015)

**Abstract**Persistent homology with coefficients in a field 𝔽 coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

**Cite**BibTex on the DBLP

**DOI:**10.1007/s00453-015-9999-4

**Title**Algorithms and Complexity of Turaev-Viro Invariants

**Authors**

*Benjamin A. Burton, Clément Maria, Jonathan Spreer*

**Conference**International Colloquium on Automata, Languages, and Programming (ICALP) 2015: 281-293

**Abstract**The Turaev-Viro invariants are a powerful family of topological invariants for distinguishing between different 3-manifolds. They are invaluable for mathematical software, but current algorithms to compute them require exponential time. The invariants are parameterised by an integer r≥3 . We resolve the question of complexity for r=3 and r=4, giving simple proofs that computing Turaev-Viro invariants for r=3 is polynomial time, but for r=4 is #P-hard. Moreover, we give an explicit fixed-parameter tractable algorithm for arbitrary r, and show through concrete implementation and experimentation that this algorithm is practical—and indeed preferable—to the prior state of the art for real computation.

**Cite**BibTex on the DBLP

**DOI:**10.1007/978-3-662-47672-7_23

**Title**Zigzag Persistence via Reflections and Transpositions

**Authors**

*Clément Maria, Steve Y. Oudot*

**Conference**Symposium on Discrete Algorithms (SoDA) 2015: 181-199

**Abstract**We introduce a new algorithm for computing zigzag persistence, designed in the same spirit as the standard persistence algorithm. Our algorithm reduces a single matrix, maintains an explicit set of chains encoding the persistent homology of the current zigzag, and updates it under simplex insertions and removals. The total worst-case running time matches the usual cubic bound. A noticeable difference with the standard persistence algorithm is that we do not insert or remove new simplices “at the end” of the zigzag, but rather “in the middle”. To do so, we use arrow reflections and transpositions, in the same spirit as reflection functors in quiver theory. Our analysis introduces new kinds of reflections in quiver representation theory: the “injective and surjective diamonds”. It also introduces the “transposition diamond” which models arrow transpositions. For each type of diamond we are able to predict the changes in the interval decomposition and associated compatible bases. Arrow transpositions have been studied previously in the context of standard persistent homology, and we extend the study to the context of zigzag persistence. For both types of transformations, we provide simple procedures to update the interval decomposition and associated compatible homology basis.

**Cite**BibTex on the DBLP

**DOI:**10.1137/1.9781611973730.14

**Title**The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes

**Authors**

*Jean-Daniel Boissonnat, Clément Maria*

**Journal**Algorithmica 70(3): 406-427 (2014)

**Abstract**This paper introduces a new data structure, called simplex tree, to represent abstract simplicial complexes of any dimension. All faces of the simplicial complex are explicitly stored in a trie whose nodes are in bijection with the faces of the complex. This data structure allows to efficiently implement a large range of basic operations on simplicial complexes. We provide theoretical complexity analysis as well as detailed experimental results. We more specifically study Rips and witness complexes.

**Cite**BibTex on the DBLP

**DOI:**10.1007/s00453-014-9887-3

**Title**Computing Persistent Homology with Various Coefficient Fields in a Single Pass

**Authors**

*Jean-Daniel Boissonnat, Clément Maria*

**Conference**European Symposium on Algorithms (ESA) 2014: 185-196

**Abstract**This article introduces an algorithm to compute the persistent homology of a filtered complex with various coefficient fields in a single matrix reduction. The algorithm is output-sensitive in the total number of distinct persistent homological features in the diagrams for the different coefficient fields. This computation allows us to infer the prime divisors of the torsion coefficients of the integral homology groups of the topological space at any scale, hence furnishing a more informative description of topology than persistence in a single coefficient field. We provide theoretical complexity analysis as well as detailed experimental results. The code is part of the Gudhi library.

**Cite**BibTex on the DBLP

**DOI:**10.1007/978-3-662-44777-2_16

**Title**The Gudhi Library: Simplicial Complexes and Persistent Homology

**Authors**

*Clément Maria, Jean-Daniel Boissonnat, Marc Glisse, Mariette Yvinec*

**Conference**International Congress on Mathematical Software (ICMS) 2014: 167-174

**Abstract**We present the main algorithmic and design choices that have been made to represent complexes and compute persistent homology in the Gudhi library. The Gudhi library (Geometric Understanding in Higher Dimensions) is a generic C++ library for computational topology. Its goal is to provide robust, efficient, flexible and easy to use implementations of state-of-the-art algorithms and data structures for computational topology. We present the different components of the software, their interaction and the user interface. We justify the algorithmic and design decisions made in Gudhi and provide benchmarks for the code. The software, which has been developped by the first author, will be available soon at project.inria.fr/gudhi/software/.

**Cite**BibTex on the DBLP

**DOI:**10.1007/978-3-662-44199-2_28

**Title**The Compressed Annotation Matrix: An Efficient Data Structure for Computing Persistent Cohomology

**Authors**

*Jean-Daniel Boissonnat, Tamal K. Dey, Clément Maria*

**Conference**European Symposium on Algorithms (ESA) 2013: 695-706

**Abstract**Persistent homology with coefficients in a field 𝔽 coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substancially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.

**Cite**BibTex on the DBLP

**DOI:**10.1007/978-3-642-40450-4_59

**Title**The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes

**Authors**

*Jean-Daniel Boissonnat, Clément Maria*

**Conference**European Symposium on Algorithms (ESA) 2012: 731-742

**Abstract**This paper introduces a new data structure, called simplex tree, to represent abstract simplicial complexes of any dimension. All faces of the simplicial complex are explicitly stored in a trie whose nodes are in bijection with the faces of the complex. This data structure allows to efficiently implement a large range of basic operations on simplicial complexes. We provide theoretical complexity analysis as well as detailed experimental results. We more specifically study Rips and witness complexes.

**Cite**BibTex on the DBLP

**DOI:**10.1007/978-3-642-33090-2_63

**Title**An Exponantial Lower Bound on the Complexity of Regularization Paths

**Authors**

*Bernd Gärtner, Martin Jaggi, Clément Maria*

**Journal**Journal of Computational Geometry (JoCG) 3(1): 168-195 (2012)

**Abstract**For a variety of regularized optimization problems in machine learning, algorithms computing the entire solution path have been developed recently. Most of these methods are quadratic programs that are parameterized by a single parameter, as for example the Support Vector Machine (SVM). Solution path algorithms do not only compute the solution for one particular value of the regularization parameter but the entire path of solutions, making the selection of an optimal parameter much easier. It has been assumed that these piecewise linear solution paths have only linear complexity, i.e. linearly many bends. We prove that for the support vector machine this complexity can be exponential in the number of training points in the worst case. More strongly, we construct a single instance of n input points in d dimensions for an SVM such that at least Θ(2^n/2) = Θ(2^d) many distinct subsets of support vectors occur as the regularization parameter changes.

**Cite**BibTex on the DBLP

**DOI:**link

**Title**Introduction to the R package TDA

**Authors**

*Brittany Terese Fasy, Jisu Kim, Fabrizio Lecci, Clément Maria*

**Preprint**arXiv:1411.1830 2014

**Abstract**We present a short tutorial and introduction to using the R package TDA, which provides some tools for Topological Data Analysis. In particular, it includes implementations of functions that, given some data, provide topological information about the underlying space, such as the distance function, the distance to a measure, the kNN density estimator, the kernel density estimator, and the kernel distance. The salient topological features of the sublevel sets (or superlevel sets) of these functions can be quantified with persistent homology. We provide an R interface for the efficient algorithms of the C++ libraries GUDHI, Dionysus and PHAT, including a function for the persistent homology of the Rips filtration, and one for the persistent homology of sublevel sets (or superlevel sets) of arbitrary functions evaluated over a grid of points. The significance of the features in the resulting persistence diagrams can be analyzed with functions that implement recently developed statistical methods. The R package TDA also includes the implementation of an algorithm for density clustering, which allows us to identify the spatial organization of the probability mass associated to a density function and visualize it by means of a dendrogram, the cluster tree.

**Cite**BibTex on the DBLP

**arXiv**:1411.1830