An official website of the United States government
We consider the multiparameter random simplicial complex as a higher dimensional extension of the classical Erdős–Rényi graph. We investigate appearance of “unusual” topological structures in the complex from the point of view of large deviations. We first study upper tail large deviation probabilities for subcomplex counts, deriving the order of magnitude of such probabilities at the logarithmic scale precision. The obtained results are then applied to analyze large deviations for the number of simplices of the multiparameter simplicial complexes. Finally, these results are also used to deduce large deviation estimates for Betti numbers of the complex in the critical dimension.
more »
« less
Efficient 1-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences
We present efficient algorithms for solving systems of linear equations in 1-Laplacians of well-shaped simplicial complexes. 1-Laplacians, or higher-dimensional Laplacians, generalize graph Laplacians to higher-dimensional simplicial complexes and play a key role in computational topology and topological data analysis. Previously, nearly-linear time solvers were developed for simplicial complexes with known collapsing sequences and bounded Betti numbers, such as those triangulating a three-ball in ℝ³ (Cohen, Fasy, Miller, Nayyeri, Peng, and Walkington [SODA'2014], Black, Maxwell, Nayyeri, and Winkelman [SODA'2022], Black and Nayyeri [ICALP'2022]). Furthermore, Nested Dissection provides quadratic time solvers for more general systems with nonzero structures representing well-shaped simplicial complexes embedded in ℝ³. We generalize the specialized solvers for 1-Laplacians to simplicial complexes with additional geometric structures but without collapsing sequences and bounded Betti numbers, and we improve the runtime of Nested Dissection. We focus on simplicial complexes that meet two conditions: (1) each individual simplex has a bounded aspect ratio, and (2) they can be divided into "disjoint" and balanced regions with well-shaped interiors and boundaries. Our solvers draw inspiration from the Incomplete Nested Dissection for stiffness matrices of well-shaped trusses (Kyng, Peng, Schwieterman, and Zhang [STOC'2018]).
more »
« less
- Award ID(s):
- 2238682
- PAR ID:
- 10489122
- Editor(s):
- Gørtz, Inge Li; Farach-Colton, Martin; Puglisi, Simon J.; Herman, Grzegorz
- Publisher / Repository:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Date Published:
- Journal Name:
- Leibniz International Proceedings in Informatics (LIPIcs):31st Annual European Symposium on Algorithms (ESA 2023)
- Subject(s) / Keyword(s):
- 1-Laplacian Solvers Simplicial Complexes Incomplete Nested Dissection Theory of computation → Design and analysis of algorithms Mathematics of computing → Computations on matrices Mathematics of computing → Algebraic topology
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Aichholzer, Oswin; Wang, Haitao (Ed.)The Betti tables of a multigraded module encode the grades at which there is an algebraic change in the module. Multigraded modules show up in many areas of pure and applied mathematics, and in particular in topological data analysis, where they are known as persistence modules, and where their Betti tables describe the places at which the homology of filtered simplicial complexes changes. Although Betti tables of singly and bigraded modules are already being used in applications of topological data analysis, their computation in the bigraded case (which relies on an algorithm that is cubic in the size of the filtered simplicial complex) is a bottleneck when working with large datasets. We show that, in the special case of 0-dimensional homology (relevant for clustering and graph classification) Betti tables of bigraded modules can be computed in log-linear time. We also consider the problem of computing minimal presentations, and show that minimal presentations of 0-dimensional persistent homology can be computed in quadratic time, regardless of the grading poset.more » « less
-
Despite the vast literature on network dynamics, we still lack basic insights into dynamics on higher-order structures (e.g., edges, triangles, and more generally, [Formula: see text]-dimensional “simplices”) and how they are influenced through higher-order interactions. A prime example lies in neuroscience where groups of neurons (not individual ones) may provide building blocks for neurocomputation. Here, we study consensus dynamics on edges in simplicial complexes using a type of Laplacian matrix called a Hodge Laplacian, which we generalize to allow higher- and lower-order interactions to have different strengths. Using techniques from algebraic topology, we study how collective dynamics converge to a low-dimensional subspace that corresponds to the homology space of the simplicial complex. We use the Hodge decomposition to show that higher- and lower-order interactions can be optimally balanced to maximally accelerate convergence and that this optimum coincides with a balancing of dynamics on the curl and gradient subspaces. We additionally explore the effects of network topology, finding that consensus over edges is accelerated when two-simplices are well dispersed, as opposed to clustered together.more » « less
-
A bstract Perturbations of massless fields in the Kerr-Newman black hole background enjoy a (“Love”) SL(2 , ℝ) symmetry in the suitably defined near zone approximation. We present a detailed study of this symmetry and show how the intricate behavior of black hole responses in four and higher dimensions can be understood from the SL(2 , ℝ) representation theory. In particular, static perturbations of four-dimensional black holes belong to highest weight SL(2 , ℝ) representations. It is this highest weight properety that forces the static Love numbers to vanish. We find that the Love symmetry is tightly connected to the enhanced isometries of extremal black holes. This relation is simplest for extremal charged spherically symmetric (Reissner-Nordström) solutions, where the Love symmetry exactly reduces to the isometry of the near horizon AdS 2 throat. For rotating (Kerr-Newman) black holes one is lead to consider an infinite-dimensional SL(2 , ℝ) ⋉ $$ \hat{\textrm{U}}{(1)}_{\mathcal{V}} $$ U ̂ 1 V extension of the Love symmetry. It contains three physically distinct subalgebras: the Love algebra, the Starobinsky near zone algebra, and the near horizon algebra that becomes the Bardeen-Horowitz isometry in the extremal limit. We also discuss other aspects of the Love symmetry, such as the geometric meaning of its generators for spin weighted fields, connection to the no-hair theorems, non-renormalization of Love numbers, its relation to (non-extremal) Kerr/CFT correspondence and prospects of its existence in modified theories of gravity.more » « less
-
Persistent topological Laplacians constitute a new class of tools in topological data analysis (TDA). They are motivated by the necessity to address challenges encountered in persistent homology when handling complex data. These Laplacians combine multiscale analysis with topological techniques to characterize the topological and geometrical features of functions and data. Their kernels fully retrieve the topological invariants of corresponding persistent homology, while their non-harmonic spectra provide supplementary information. Persistent topological Laplacians have demonstrated superior performance over persistent homology in the analysis of large-scale protein engineering datasets. In this survey, we offer a pedagogical review of persistent topological Laplacians formulated in various mathematical settings, including simplicial complexes, path complexes, flag complexes, digraphs, hypergraphs, hyperdigraphs, cellular sheaves, and N-chain complexes.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.ESA.2023.41
