An official website of the United States government
.We show the existence of linear bounds on Wall 𝜌-invariants of PL manifolds, employing a new combinatorial concept of 𝐺-colored polyhedra. As an application, we show how the number of h-cobordism classes of manifolds simple homotopy equivalent to a lens space with 𝑉 simplices and the fundamental group of Z n grows in 𝑉. Furthermore, we count the number of homotopy lens spaces with bounded geometry in 𝑉. Similarly, we give new linear bounds on Cheeger–Gromov 𝜌-invariants of PL manifolds endowed with a faithful representation also. A key idea is to construct a cobordism with a linear complexity whose boundary is π 1 -injectively embedded, using relative hyperbolization. As an application, we study the complexity theory of high-dimensional lens spaces. Lastly, we show the density of 𝜌-invariants over manifolds homotopy equivalent to a given manifold for certain fundamental groups. This implies that the structure set is not finitely generated.
more »
« less
On the reduction in accuracy of finite difference schemes on manifolds without boundary
Abstract We investigate error bounds for numerical solutions of divergence structure linear elliptic partial differential equations (PDEs) on compact manifolds without boundary. Our focus is on a class of monotone finite difference approximations, which provide a strong form of stability that guarantees the existence of a bounded solution. In many settings including the Dirichlet problem, it is easy to show that the resulting solution error is proportional to the formal consistency error of the scheme. We make the surprising observation that this need not be true for PDEs posed on compact manifolds without boundary. We propose a particular class of approximation schemes built around an underlying monotone scheme with consistency error $$O(h^{\alpha })$$. By carefully constructing barrier functions, we prove that the solution error is bounded by $$O(h^{\alpha /(d+1)})$$ in dimension $$d$$. We also provide a specific example where this predicted convergence rate is observed numerically. Using these error bounds, we further design a family of provably convergent approximations to the solution gradient.
more »
« less
- Award ID(s):
- 1751996
- PAR ID:
- 10522006
- Publisher / Repository:
- IMA Journal of Numerical Analysis
- Date Published:
- Journal Name:
- IMA Journal of Numerical Analysis
- Volume:
- 44
- Issue:
- 3
- ISSN:
- 0272-4979
- Page Range / eLocation ID:
- 1751 to 1784
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study a class of second-order degenerate linear parabolic equations in divergence form in ( − ∞ , T ) × R + d (-\infty , T) \times {\mathbb {R}}^d_+ with homogeneous Dirichlet boundary condition on ( − ∞ , T ) × ∂ R + d (-\infty , T) \times \partial {\mathbb {R}}^d_+ , where R + d = { x ∈ R d : x d > 0 } {\mathbb {R}}^d_+ = \{x \in {\mathbb {R}}^d: x_d>0\} and T ∈ ( − ∞ , ∞ ] T\in {(-\infty , \infty ]} is given. The coefficient matrices of the equations are the product of μ ( x d ) \mu (x_d) and bounded uniformly elliptic matrices, where μ ( x d ) \mu (x_d) behaves like x d α x_d^\alpha for some given α ∈ ( 0 , 2 ) \alpha \in (0,2) , which are degenerate on the boundary { x d = 0 } \{x_d=0\} of the domain. Our main motivation comes from the analysis of degenerate viscous Hamilton-Jacobi equations. Under a partially VMO assumption on the coefficients, we obtain the well-posedness and regularity of solutions in weighted Sobolev spaces. Our results can be readily extended to systems.more » « less
-
Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L_p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS’13). The non-linearity of L_p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L_p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G(n, d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime.more » « less
-
Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L^p-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of L^p-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L^p-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G(n,d/n), where the previously known algorithms run in time n^O(log d) or applied only to large d. We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d, throughout the uniqueness regime.more » « less
-
Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)Recently, a number of variants of the notion of cut-preserving hypergraph sparsification have been studied in the literature. These variants include directed hypergraph sparsification, submodular hypergraph sparsification, general notions of approximation including spectral approximations, and more general notions like sketching that can answer cut queries using more general data structures than just sparsifiers. In this work, we provide reductions between these different variants of hypergraph sparsification and establish new upper and lower bounds on the space complexity of preserving their cuts. Specifically, we show that: 1) (1 ± ε) directed hypergraph spectral (respectively cut) sparsification on n vertices efficiently reduces to (1 ± ε) undirected hypergraph spectral (respectively cut) sparsification on n² + 1 vertices. Using the work of Lee and Jambulapati, Liu, and Sidford (STOC 2023) this gives us directed hypergraph spectral sparsifiers with O(n² log²(n) / ε²) hyperedges and directed hypergraph cut sparsifiers with O(n² log(n)/ ε²) hyperedges by using the work of Chen, Khanna, and Nagda (FOCS 2020), both of which improve upon the work of Oko, Sakaue, and Tanigawa (ICALP 2023). 2) Any cut sketching scheme which preserves all cuts in any directed hypergraph on n vertices to a (1 ± ε) factor (for ε = 1/(2^{O(√{log(n)})})) must have worst-case bit complexity n^{3 - o(1)}. Because directed hypergraphs are a subclass of submodular hypergraphs, this also shows a worst-case sketching lower bound of n^{3 - o(1)} bits for sketching cuts in general submodular hypergraphs. 3) (1 ± ε) monotone submodular hypergraph cut sparsification on n vertices efficiently reduces to (1 ± ε) symmetric submodular hypergraph sparsification on n+1 vertices. Using the work of Jambulapati et. al. (FOCS 2023) this gives us monotone submodular hypergraph sparsifiers with Õ(n / ε²) hyperedges, improving on the O(n³ / ε²) hyperedge bound of Kenneth and Krauthgamer (arxiv 2023). At a high level, our results use the same general principle, namely, by showing that cuts in one class of hypergraphs can be simulated by cuts in a simpler class of hypergraphs, we can leverage sparsification results for the simpler class of hypergraphs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imanum/drad048
