An official website of the United States government
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
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
-
-
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
-
Abstract Our previous multiscale graph basis dictionaries/graph signal transforms—Generalized Haar-Walsh Transform (GHWT); Hierarchical Graph Laplacian Eigen Transform (HGLET); Natural Graph Wavelet Packets (NGWPs); and their relatives—were developed for analyzing data recorded on vertices of a given graph. In this article, we propose their generalization for analyzing data recorded on edges, faces (i.e., triangles), or more generally$$\kappa $$ -dimensional simplices of a simplicial complex (e.g., a triangle mesh of a manifold). The key idea is to use the Hodge Laplacians and their variants for hierarchical partitioning of a set of$$\kappa $$ -dimensional simplices in a given simplicial complex, and then build localized basis functions on these partitioned subsets. We demonstrate their usefulness for data representation on both illustrative synthetic examples and real-world simplicial complexes generated from a co-authorship/citation dataset and an ocean current/flow dataset.more » « less
-
Abstract Persistent Betti numbers are a major tool in persistent homology, a subfield of topological data analysis. Many tools in persistent homology rely on the properties of persistent Betti numbers considered as a two-dimensional stochastic process$$ (r,s) \mapsto n^{-1/2} (\beta^{r,s}_q ( \mathcal{K}(n^{1/d} \mathcal{X}_n))-\mathbb{E}[\beta^{r,s}_q ( \mathcal{K}( n^{1/d} \mathcal{X}_n))])$$. So far, pointwise limit theorems have been established in various settings. In particular, the pointwise asymptotic normality of (persistent) Betti numbers has been established for stationary Poisson processes and binomial processes with constant intensity function in the so-called critical (or thermodynamic) regime; see Yogeshwaranet al.(Prob. Theory Relat. Fields167, 2017) and Hiraokaet al.(Ann. Appl. Prob.28, 2018). In this contribution, we derive a strong stabilization property (in the spirit of Penrose and Yukich,Ann. Appl. Prob.11, 2001) of persistent Betti numbers, and we generalize the existing results on their asymptotic normality to the multivariate case and to a broader class of underlying Poisson and binomial processes. Most importantly, we show that multivariate asymptotic normality holds for all pairs (r,s),$$0\le r\le s<\infty$$, and that it is not affected by percolation effects in the underlying random geometric graph.more » « less
-
Abstract We prove the macroscopic cousins of three conjectures: (1) a conjectural bound of the simplicial volume of a Riemannian manifold in the presence of a lower scalar curvature bound, (2) the conjecture that rationally essential manifolds do not admit metrics of positive scalar curvature, (3) a conjectural bound of $$\ell ^2$$ ℓ 2 -Betti numbers of aspherical Riemannian manifolds in the presence of a lower scalar curvature bound. The macroscopic cousin is the statement one obtains by replacing a lower scalar curvature bound by an upper bound on the volumes of 1-balls in the universal cover.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.ESA.2023.41
