English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We present efficient algorithms for approximately solving systems of linearequations in $1$-Laplacians of well-shaped simplicial complexes up to highprecision. $1$-Laplacians, or higher-dimensional Laplacians, generalize graphLaplacians to higher-dimensional simplicial complexes and play a key role incomputational topology and topological data analysis. Previously, nearly-lineartime approximate solvers were developed for simplicial complexes with knowncollapsing sequences and bounded Betti numbers, such as those triangulating athree-ball in $\mathbb{R}^3$ (Cohen, Fasy, Miller, Nayyeri, Peng, andWalkington [SODA'2014], Black, Maxwell, Nayyeri, and Winkelman [SODA'2022],Black and Nayyeri [ICALP'2022]). Furthermore, Nested Dissection providesquadratic time exact solvers for more general systems with nonzero structuresrepresenting well-shaped simplicial complexes embedded in $\mathbb{R}^3$.  We generalize the specialized solvers for $1$-Laplacians to simplicialcomplexes with additional geometric structures but without collapsing sequencesand bounded Betti numbers, and we improve the runtime of Nested Dissection. Wefocus on simplicial complexes that meet two conditions: (1) each individualsimplex has a bounded aspect ratio, and (2) they can be divided into "disjoint"and balanced regions with well-shaped interiors and boundaries. Our solversdraw inspiration from the Incomplete Nested Dissection for stiffness matricesof well-shaped trusses (Kyng, Peng, Schwieterman, and Zhang [STOC'2018]).

Efficient $1$-Laplacian Solvers for Well-Shaped Simplicial Complexes: Beyond Betti Numbers and Collapsing Sequences