Complexity and speed of semi-algebraic multi-persistence

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,\dots ,f_p):S\to {\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 $\mathrm{\ell }$ the invariant is encoded by a ${\mathbb{Z}}_{\ge 0}$-valued function $${\mu }_{\mathrm{\ell }}(S,\mathbf{f}):((-1,1{)}^p\times ((-1,1{)}^p\cup \{(1,\dots ,1)\}))\cap \{(\mathbf{a},\mathbf{b})\mid \mathbf{a}⪯\mathbf{b}\}⟶{\mathbb{Z}}_{\ge 0},$$ where $⪯$ denotes the product order on ${\mathrm{R}}^p$. We prove that ${\mu }_{\mathrm{\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 ${\mu }_{\mathrm{\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.