Complexity and speed of semi-algebraic multi-persistence
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918267528937472 |
|---|---|
| author | Banerjee, Arindam Basu, Saugata |
| author_facet | Banerjee, Arindam Basu, Saugata |
| contents | Let $\mathrm{R}$ be a real closed field, $S \subset \mathrm{R}^n$ a closed and bounded semi-algebraic set, and $\mathbf{f}=(f_1,\ldots,f_p):S \rightarrow \mathrm{R}^p$ a continuous semi-algebraic map inducing a $p$-parameter semi-algebraic filtration by sublevel sets. We introduce a barcode invariant for such filtrations that directly extends the classical ($p=1$) barcode. After scaling of the parameter space, in each homological degree $\ell$ the invariant is encoded by a $\mathbb{Z}_{\ge 0}$-valued function \[ μ_\ell(S,\mathbf{f}):\ \Big(({-}1,1)^p\times(({-}1,1)^p \cup\{(1,\ldots,1)\}) \Big)\ \cap\ \{(\mathbf a,\mathbf b)\mid \mathbf a\preceq \mathbf b\} \ \longrightarrow\ \mathbb{Z}_{\ge 0}, \] where $\preceq$ denotes the product order on $\mathrm{R}^p$. We prove that $μ_\ell(S,\mathbf{f})$ is semi-algebraically constructible and establish a singly exponential upper bound on its description complexity. Moreover, we give a singly exponential-time algorithm to compute $μ_\ell(S,\mathbf{f})$, extending to arbitrary $p$ the corresponding result for $p=1$ by Basu and Karisani. Finally, for semi-algebraic filtrations of bounded description complexity we bound the number of equivalence classes of finite poset modules realizable in this way, yielding a tight analogue of "speed" bounds for algebraically defined graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_13586 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity and speed of semi-algebraic multi-persistence Banerjee, Arindam Basu, Saugata Algebraic Topology Primary 14F25, 55N31, Secondary 68W30 Let $\mathrm{R}$ be a real closed field, $S \subset \mathrm{R}^n$ a closed and bounded semi-algebraic set, and $\mathbf{f}=(f_1,\ldots,f_p):S \rightarrow \mathrm{R}^p$ a continuous semi-algebraic map inducing a $p$-parameter semi-algebraic filtration by sublevel sets. We introduce a barcode invariant for such filtrations that directly extends the classical ($p=1$) barcode. After scaling of the parameter space, in each homological degree $\ell$ the invariant is encoded by a $\mathbb{Z}_{\ge 0}$-valued function \[ μ_\ell(S,\mathbf{f}):\ \Big(({-}1,1)^p\times(({-}1,1)^p \cup\{(1,\ldots,1)\}) \Big)\ \cap\ \{(\mathbf a,\mathbf b)\mid \mathbf a\preceq \mathbf b\} \ \longrightarrow\ \mathbb{Z}_{\ge 0}, \] where $\preceq$ denotes the product order on $\mathrm{R}^p$. We prove that $μ_\ell(S,\mathbf{f})$ is semi-algebraically constructible and establish a singly exponential upper bound on its description complexity. Moreover, we give a singly exponential-time algorithm to compute $μ_\ell(S,\mathbf{f})$, extending to arbitrary $p$ the corresponding result for $p=1$ by Basu and Karisani. Finally, for semi-algebraic filtrations of bounded description complexity we bound the number of equivalence classes of finite poset modules realizable in this way, yielding a tight analogue of "speed" bounds for algebraically defined graph classes. |
| title | Complexity and speed of semi-algebraic multi-persistence |
| topic | Algebraic Topology Primary 14F25, 55N31, Secondary 68W30 |
| url | https://arxiv.org/abs/2407.13586 |