#  Complexity and speed of semi-algebraic multi-persistence

Arindam Banerjee  Department of Mathematics, IIT Kharagpur, Kharagpur, India.
<EMAIL_ADDRESS>and  Saugata Basu  Department of Mathematics, Purdue
University, West Lafayette, IN 47906, U.S.A<EMAIL_ADDRESS>
###### Abstract.

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. We study the poset module structure in homology induced by
the simultaneous filtrations of $S$ by the sub-level sets of the functions
$f_{i}$ from an algorithmic and quantitative point of view. For fixed
dimensional homology we prove a singly exponential upper bound on the
complexity of these modules which are encoded as certain semi-algebraically
constructible functions on $\mathrm{R}^{p}\times\mathrm{R}^{p}$. We also
deduce for semi-algebraic filtrations of bounded complexity, upper bounds on
the number of equivalence classes of finite poset modules that such a
filtration induces – establishing a tight analogy with a well-known graph
theoretical result on the “speed” of algebraically defined graphs.

###### Key words and phrases:

persistent homology, multi-persistence, poset module, semi-algebraic set,
constructible function, speed

###### 1991 Mathematics Subject Classification:

Primary 14F25, 55N31; Secondary 68W30

Banerjee was partially supported by SERB Start Up Research Grant, IIT
Kharagpur Faculty Start Up Research Grant and CPDA of IIT Kharagpur. Basu was
partially supported by NSF grant CCF-1910441.

###### Contents

  1. 1 Introduction
    1. 1.1 Main Results
    2. 1.2 Complexity of semi-algebraic multi-persistence modules
    3. 1.3 Speed of semi-algebraic multi-persistence modules
      1. 1.3.1 Speed of semi-algebraic graphs
    4. 1.4 Algorithm for computing semi-algebraic multi-persistence modules
      1. 1.4.1 Model of computation and definition of complexity
  2. 2 Background, significance and prior work
    1. 2.1 Algorithmic semi-algebraic geometry
    2. 2.2 Complexity – singly vs doubly exponential
      1. 2.2.1 Doubly exponential
      2. 2.2.2 Singly exponential
    3. 2.3 Semi-algebraic persistence: the case $p=1$
    4. 2.4 Significance of Theorems 1 and 4 and Corollary 1
    5. 2.5 Significance of Theorems 2 and 3
      1. 2.5.1 Finite vs infinite
    6. 2.6 Prior work
  3. 3 Proofs of Theorems 1 and 4
    1. 3.1 Algorithmic Preliminaries
      1. 3.1.1 Algorithm for enumerating $\mathrm{Cc}(\mathcal{P})$
      2. 3.1.2 Parametrized versions of algorithms in real algebraic geometry
      3. 3.1.3 Parametrized algorithm for computing semi-algebraic triangulation
    2. 3.2 Outline of the proof
      1. 3.2.1 Algorithm for semi-algebraic multi-persistence using effective semi-algebraic triangulation
    3. 3.3 Proofs of Theorems 1, 4 and Corollary 1
      1. 3.3.1 Parametrized algorithm for computing cover by contractible sets
      2. 3.3.2 Parametrized simplicial replacement algorithm
      3. 3.3.3 Parametrized algorithm for simplicial replacement
  4. 4 Proofs of Theorems 2 and 3

##  1\. Introduction

Persistent homology theory is now a well established sub-field of applied
topology [50, 35, 31]. Initially persistent homology modules were associated
to filtrations of spaces by the sub-level sets of single functions. More
recently, simultaneous filtrations by multiple functions have been studied
driven by applications [28, 27, 22, 30, 29]. More generally, persistent
homology theory over arbitrary posets have been developed extensively in [41].
Study of persistent homology restricted to tame spaces – such as the category
of semi-algebraic sets and maps – is of much recent origin [37, 42, 13] – and
is the topic of this paper.

Let $\mathrm{R}$ be a real closed field and D an ordered domain contained in
$\mathrm{R}$ which we fix for the rest of the paper.

We study in this paper semi-algebraic multi-persistence modules induced by
filtrations of the sublevels sets of continuous semi-algebraic maps
$\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ from a quantitative, as well
algorithmic, point of view.

We address the following problems.

  1. (A)

We consider the problem of defining a data-structure (which turns to be a
semi-algebraically constructible function on
$\mathrm{R}^{p}\times\mathrm{R}^{p}$), so that given any finite subset of
$\mathrm{R}^{p}$, the structure of the induced submodule on the corresponding
finite poset can be read off efficiently (i.e. without any further computation
involving $S$ and $\mathbf{f}$).

  2. (B)

We also consider the problem of designing an efficient algorithm for computing
the constructible function mentioned above.

  3. (C)

Finally, we consider the problem of understanding the whole class of finite
poset modules obtainable from semi-algebraic multi-filtrations of bounded
complexity. Following the spirit of a similar notion in graph theory [45], we
introduce the notion of “speed” of semi-algebraically defined families of
finite poset modules, which counts the number of non-equivalent poset modules
on finite posets belonging to the family. We consider the problem of proving
upper bounds on the speed of semi-algebraic families of poset modules
mirroring the corresponding result in graph theory [45].

###  1.1. Main Results

We prove results in all three directions mentioned above. We prove upper
bounds on the the _complexity_ (Theorem 1) and the _speed_ of semi-algebraic
multi-persistence modules (Theorems 2 and 3) – the notion of complexity and
speed pertaining to semi-algebraic persistence theory are new, and we define
them below. Finally, we describe an algorithm and prove upper bounds on its
complexity for computing these modules (Theorem 4).

In order to get to the main results as quickly as possible, we first state
these in the next three subsections introducing the necessary notation and
background information. In the next section (Section 2) we discuss motivation
behind studying these questions, the significance of our results, and
connections with prior work in both algorithmic semi-algebraic geometry and
persistent homology theory. Finally, we prove our results in Sections 3 and 4.

We assume only basic familiarity with homology theory and some categorical
definitions, but do not assume any specialized knowledge of persistent
homology theory or semi-algebraic geometry (other than the definition of real
closed fields and semi-algebraic sets and maps) in what follows.

###  1.2. Complexity of semi-algebraic multi-persistence modules

In order to state our results we need to recall some basic definitions. Let
$\mathbf{k}$ be a field fixed for the rest of the paper.

We denote by $\mathrm{Vect}_{\mathbf{k}}$ the category of $\mathbf{k}$-vector
spaces and linear maps.

######  Definition 1.1 (Poset modules).

Given a partially ordered set (poset) $(P,\preceq)$, a _poset module over $P$_
is a functor:

$\mathbf{P}:(P,\preceq)\rightarrow\mathrm{Vect}_{\mathbf{k}},$

where we consider $(P,\preceq)$ as a poset category – namely, the category
whose objects are elements $p\in P$, and the set of morphisms
$\mathrm{Hom}_{(P,\preceq)}(p,p^{\prime})$ is empty if $p\not\preceq
p^{\prime}$ and a singleton set, which will denote by “$p\preceq p^{\prime}$”,
otherwise.

######  Definition 1.2 (Isomorphism of poset modules).

We say that two poset modules
$\mathbf{P},\mathbf{P^{\prime}}:P\rightarrow\mathrm{Vect}_{\mathbf{k}}$ are
isomomorphic if there exists a natural transformations $F,G$ as depicted below
which are inverses of each other:

$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathbf{P}}$$\scriptstyle{\mathbf{P}^{\prime}}$$\textstyle{F\Uparrow}$$\textstyle{\mathrm{Vect}_{\mathbf{k}},}$$\textstyle{P\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathbf{P}}$$\scriptstyle{\mathbf{P}^{\prime}}$$\textstyle{\Downarrow
G}$$\textstyle{\mathrm{Vect}_{\mathbf{k}}.}$

We will deal mostly with the poset $(\mathrm{R}^{p},\preceq)$, where the
partial order $\preceq$ is defined coordinate-wise i.e.
$(a_{1},\ldots,a_{p})=\mathbf{a}\preceq\mathbf{b}=(b_{1},\ldots,b_{p})$ if and
only if $a_{i}\leq b_{i},1\leq i\leq p$.

For any poset $(P,\preceq)$, we will denote by
$\mathrm{pairs}(P)=\\{(p,p^{\prime})\;\mid\;p\preceq p^{\prime}\\}$.

In the case $P=\mathrm{R}^{p}$, we will identify
$\mathrm{pairs}(\mathrm{R}^{p})$ with the semi-algebraic subset of
$\mathrm{R}^{p}\times\mathrm{R}^{p}=\mathrm{R}^{2p}$, defined by the
inequalities $Y_{i}-Y_{i}^{\prime}\leq 0,1\leq i\leq p$, where
$(Y_{1},\ldots,Y_{p},Y_{1}^{\prime},\ldots,Y_{p}^{\prime})$ are the
coordinates with respect to the standard basis of $\mathrm{R}^{2p}$.

A key role in what follows will be played by semi-algebraically constructible
functions whose definition we recall below.

######  Definition 1.3.

A _semi-algebraically constructible function_

$F:S\rightarrow\mathbf{k},$

where $S$ is a semi-algebraic set, is a $\mathbf{k}$-linear combination of the
characteristic functions of some finite number of semi-algebraic subsets of
$S$. More generally, we say that a function
$F=(f_{1},\ldots,f_{M}):S\rightarrow\mathbf{k}^{M}$ is semi-algebraically
constructible, if each $f_{i}$ is semi-algebraically constructible.

Clearly, to each semi-algebraically constructible function
$F:S\rightarrow\mathbf{k}^{M}$, there exists a finite partition of $S$ into
semi-algebraic subsets on which $F$ is constant. We will say that such a
partition is _subordinate to $F$_. Clearly, if a partition is subordinate to
$F$, and a finer partition will also be subordinate to $F$.

We will make use of semi-algebraic partitions of a special kind which we
introduce below.

######  Notation 1.1 (Sign conditions, realization, $\mathrm{Cc}(\cdot)$).

For a finite subset $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$ we will
call any element of $\\{0,1,-1\\}^{\mathcal{P}}$ a _sign condition on
$\mathcal{P}$_. We will denote by

${\mathcal{R}}(\sigma)=\\{\mathbf{x}\in\mathrm{R}^{n}\;|\;\mbox{\bf
sign}(P(\mathbf{x}))=\sigma(P),P\in\mathcal{P}\\}.$

We denote by

$\mbox{\rm
Sign}(\mathcal{P})=\\{\sigma\in\\{0,1,-1\\}^{\mathcal{P}}\mid{\mathcal{R}}(\sigma)\neq\emptyset\\},$

and call $\mbox{\rm Sign}(\mathcal{P})$ the set of realizable sign conditions
of $\mathcal{P}$.

We will denote $\mathrm{Cc}(\sigma)$ the set of semi-algebraically connected
components of ${\mathcal{R}}(\sigma)$, and denote

$\mathrm{Cc}(\mathcal{P})=\bigcup_{\sigma\in\mbox{\rm
Sign}(\mathcal{P})}\mathrm{Cc}(\sigma).$

(Note that $\left(C\right)_{C\in\mathrm{Cc}(\mathcal{P})}$ is a finite
partition of $\mathrm{R}^{n}$ into non-empty locally closed semi-algebraic
sets.)

######  Notation 1.2.

For a finite subset $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$, we
will denote $\deg(\mathcal{P})=\max_{P\in\mathcal{P}}\deg(P)$.

We now define a notion of complexity of a semi-algebraically constructible
function in terms of the “complexity” of partitions subordinate to it.

######  Definition 1.4 (Complexity of semi-algebraically constructible
functions).

We will say that _a semi-algebraically constructible function
$F:S\rightarrow\mathbf{k}^{M},S\subset\mathrm{R}^{n}$ has complexity $\leq
D$_, if there exists $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$, such
that the partition $\left(C\right)_{C\in\mathrm{Cc}(\mathcal{P}),C\subset S}$
is subordinate to $F$, and
$\mathrm{card}(\mathcal{P})\cdot\deg(\mathcal{P})\leq D$.

######  Remark 1 (Alternative definitions of complexity).

An alternative definition of the complexity of $F$ would be to say that
complexity of a semi-algebraically constructible function $F$ is $\leq D$ if
there exists $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$ such that the
partition

$\left({\mathcal{R}}(\sigma)\right)_{\sigma\in\mbox{\rm
Sign}(\mathcal{P}),{\mathcal{R}}(\sigma)\subset S}$

is subordinate to $F$, and

$\mathrm{card}(\mathcal{P})\cdot\deg(\mathcal{P})\leq D.$

However, the semi-algebraically connected components of a $\mathcal{P}$-semi-
algebraic set, where $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq
d},\mathrm{card}(\mathcal{P})\leq s$, are all $\mathcal{Q}$-semi-algebraic
sets, for some $\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$, with
$\mathrm{card}(\mathcal{Q})\leq s^{n}d^{O(n^{4})}$ and $\deg(\mathcal{Q})\leq
d^{O(n^{3})}$ [8, Theorem 16.11]. So if the complexity of $F$ is bounded by
$D$ according to Definition 1.4, then it is bounded by $D^{n^{O(1)}}$ by this
alternative definition – and so the asymptotic bounds in this paper, such as
in Theorem 1, is unchanged if we use this alternative definition.

Semi-algebraically constructible functions have been studied from the point of
view computational complexity theory earlier in [11]. In that paper, the
complexity (in terms of formula size) of a semi-algebraically constructible
function is also defined in terms of subordinate partitions [11, Definition
2.16]. However, the definition in [11] is a bit more nuanced than the
definitions given above, since it is aimed at developing a broader theory of
complexity classes of constructible functions (and sheaves) which is not our
aim here. So we do not repeat it here but mention that the upper bound in
Theorem 1 would apply even with the definition given in [11].

We now arrive at one of the central objects of interest in this paper.

######  Definition 1.5 (Semi-algebraically constructible poset modules and
their complexity).

We say that a poset module

$\mathbf{P}:(\mathrm{R}^{p},\preceq)\rightarrow\mathrm{Vect}_{\mathbf{k}},$

is semi-algebraically constructible, if there exists $K\geq 0$, and a semi-
algebraically constructible function

$F:\mathrm{pairs}(\mathrm{R}^{p})\rightarrow\mathbf{k}^{K\times K},$

such that $\mathbf{P}$ is isomorphic (see Definition 1.2) to the poset module

$\widetilde{\mathbf{P}}:(\mathrm{R}^{p},\preceq)\rightarrow\mathrm{Vect}_{\mathbf{k}},$

defined by:

$\displaystyle\widetilde{\mathbf{P}}(\mathbf{y})$ $\displaystyle=$
$\displaystyle\mathbf{k}^{\dim\mathbf{P}(\mathbf{y})},$
$\displaystyle\widetilde{\mathbf{P}}(\mathbf{y}\preceq\mathbf{y}^{\prime})$
$\displaystyle=$ $\displaystyle
L_{\mathrm{Trunc}_{\dim\mathbf{P}(\mathbf{y}^{\prime}),\dim\mathbf{P}(\mathbf{y})}^{K}(F(\mathbf{y},\mathbf{y}^{\prime}))},$

where for $0\leq p,q\leq K$,

$\mathrm{Trunc}_{p,q}^{K}:\mathbf{k}^{K\times K}\rightarrow\mathbf{k}^{p\times
q},$

is the map that extracts the $p\times q$ matrix out of an $K\times K$ matrix
by extracting the first $p$ rows and the first $q$ columns, and for
$M\in\mathbf{k}^{p\times q}$, $L_{M}:\mathbf{k}^{q}\rightarrow\mathbf{k}^{p}$
denotes the homomorphism $\mathbf{x}\mapsto M\cdot\mathbf{x}$.

We will say that $F$ is associated to $\mathbf{P}$, and that $\mathbf{P}$ _has
complexity $\leq D$_, if the semi-algebraically constructible function $F$ has
complexity $\leq D$ (see Definition 1.4).

We finally arrive at the notion of poset modules induced by semi-algebraic
multi-filtrations.

######  Definition 1.6 (Poset modules induced by a semi-algebraic multi-
filtration).

Let $S\subset\mathrm{R}^{n}$ be a closed and bounded semi-algebraic set and
$\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ be a continuous semi-algebraic map.

For $\mathbf{y}\in\mathrm{R}^{p}$, we denote by
$S_{\mathbf{f}\preceq\mathbf{y}}=\\{x\in
S\mid\mathbf{f}(x)\preceq\mathbf{y}\\}$.

For $\ell\geq 0$, we denote by

$\mathbf{P}_{S,\mathbf{f},\ell}:(\mathrm{R}^{p},\preceq)\rightarrow\mathrm{Vect}_{\mathbf{k}}$

the poset module (which we call the _$\ell$ -th multi-persistence module of
the filtration of $S$ by $\mathbf{f}$_) defined by

$\displaystyle\mathbf{P}_{S,\mathbf{f},\ell}(\mathbf{y})$ $\displaystyle=$
$\displaystyle\mbox{\rm H}_{i}(S_{\mathbf{f}\preceq\mathbf{y}}),$
$\displaystyle\mathbf{P}_{S,\mathbf{f},\ell}(\mathbf{y}\preceq\mathbf{y}^{\prime})$
$\displaystyle=$ $\displaystyle\iota_{\mathbf{y},\mathbf{y}^{\prime},\ell},$

where $\mbox{\rm H}_{\ell}(\cdot)$ denotes the $\ell$-th homology group with
coefficients in $\mathbf{k}$, and

$\iota_{\mathbf{y},\mathbf{y}^{\prime},\ell}:\mbox{\rm
H}_{i}(S_{\mathbf{f}\preceq\mathbf{y}})\rightarrow\mbox{\rm
H}_{i}(S_{\mathbf{f}\preceq\mathbf{y}^{\prime}})$

is the homomorphism induced by the inclusion
$S_{\mathbf{f}\preceq\mathbf{y}}\hookrightarrow
S_{\mathbf{f}\preceq\mathbf{y}^{\prime}}$.

The following simple example illustrates Definitions 1.5 and 1.6.

######  Example 1.1.

Figure 1. The subset $D\subset\mathrm{R}^{2}$.

Let $n=2,p=2,\ell=0$, and $S\subset\mathrm{R}^{2}$ be the closed unit disk
defined by $X_{1}^{2}+X_{2}^{2}-1\leq 0$, and $f_{1}=X_{1},f_{2}=X_{2}$. Let
$D=S\cup(\mathrm{R}_{\geq 0}^{2}+(-1,0))\cup(\mathrm{R}_{\geq 0}^{2}+(0,-1))$
(see Figure 1), and let
$F:\mathrm{pairs}(\mathrm{R}^{2})\rightarrow\mathbf{k}$ be the constructible
function defined as follows:

$\displaystyle F(\mathbf{y}_{1},\mathbf{y}_{2})$ $\displaystyle=$
$\displaystyle 1,\mbox{ if $(\mathbf{y}_{1},\mathbf{y}_{2})\in D\times
D\cap\mathrm{pairs}(\mathrm{R}^{2})$,}$ $\displaystyle=$ $\displaystyle
0,\mbox{else}.$

It is easy to check that $F$ is associated to the poset module
$\mathbf{P}_{S,\mathbf{f},0}$ in this example. Moreover, the partition
$(C)_{C\in\mathrm{Cc}(\mathcal{D}),C\subset\mathrm{pairs}(\mathrm{R}^{2})}$ is
subordinate to $F$, where

$\mathcal{D}=\\{Y_{1}^{2}+Y_{2}^{2}-1,Y_{1}+1,Y_{2}+1,Y_{1}^{\prime
2}+Y_{2}^{\prime
2}-1,Y_{1}^{\prime}+1,Y_{2}^{\prime}+1,Y_{1}-Y_{1}^{\prime},Y_{2}-Y_{2}^{\prime}\\}.$

It follows from Definitions 1.4 , 1.5 and 1.6, that the complexity of $F$, and
hence also the complexity of $\mathbf{P}_{S,\mathbf{f},0}$, is
$\leq\mathrm{card}(\mathcal{D})\cdot\deg(\mathcal{D})=8\cdot 2=16$.

Our first theorem (Theorem 1 below) states that the modules
$\mathbf{P}_{S,\mathbf{f},\ell}$ are all semi-algebraically constructible,
with singly exponentially bounded complexity (see Definition 1.5). In order to
make the statement about the complexity precise we need one more notation.

######  Notation 1.3 (Realizations, $\mathcal{P}$-, $\mathcal{P}$-closed semi-
algebraic sets).

For any finite set of polynomials
$\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$, we call any quantifier-
free first order formula $\phi$ with atoms, $P=0,P<0,P>0,P\in\mathcal{P}$, to
be a _$\mathcal{P}$ -formula_. We call the realization of $\phi$:

$\displaystyle{\mathcal{R}}(\phi)$ $\displaystyle:=$
$\displaystyle\\{\mathbf{x}\in\mathrm{R}^{n}\mid\phi(\mathbf{x})\\}$

a _$\mathcal{P}$ -semi-algebraic subset of $\mathrm{R}^{n}$_.

We say that a quantifier-free formula $\phi$ is _closed_ if it is a formula in
disjunctive normal form with no negations, and with atoms of the form $P\geq
0,P\leq 0$, where $P\in\mathrm{R}[X_{1},\ldots,X_{n}]$. If the set of
polynomials appearing in a closed formula is contained in a finite set
$\mathcal{P}$, we will call such a formula a $\mathcal{P}$-closed formula, and
we call the realization, ${\mathcal{R}}\left(\phi\right)$, a _$\mathcal{P}$
-closed semi-algebraic set_.

Similarly, if
$\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p}]$ we a
call map $\mathrm{R}^{n}\rightarrow\mathrm{R}^{p}$ to be a $\mathcal{Q}$-semi-
algebraic (resp. $\mathcal{Q}$-closed semi-algebraic) map if
$\mathrm{graph}(f)\subset\mathrm{R}^{n}\times\mathrm{R}^{p}$ is a
$\mathcal{Q}$-semi-algebraic (resp. $\mathcal{Q}$-closed semi-algebraic) set.

We can now state our first quantitative result.

######  Theorem 1.

Let $S\subset\mathrm{R}^{n}$ be a bounded $\mathcal{P}$-closed semi-algebraic
set, and $\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ be a $\mathcal{Q}$-closed
continuous semi-algebraic map. Then, for each $\ell\geq 0$, the poset module
$\mathbf{P}_{S,\mathbf{f},\ell}$ is semi-algebraically constructible with
complexity bounded by

$(sd)^{(pn)^{O(\ell)}},$

where $s=\mathrm{card}(\mathcal{P})+\mathrm{card}(\mathcal{Q})$, and
$d=\max(\deg(\mathcal{P}),\deg(\mathcal{Q}))$.

######  Remark 2.

Note that the complexity in Theorem 1 is bounded singly exponentially for
every fixed $\ell\geq 0$.

######  Remark 3.

We will discuss the significance of Theorem 1 and its connections with prior
results (particularly, results in [13] where the case $p=1$ is treated) later
in Subsection 2.4. At this point we just note that the singly exponential
bound on the complexity of the semi-algebraically constructible module
$\mathbf{P}_{S,\mathbf{f},\ell}$ implies that given any finite subset
$T\subset\mathrm{R}^{p}$, the poset module
$\mathbf{P}_{S,\mathbf{f},\ell}\restriction_{T}$, obtained by restricting the
functor $\mathbf{P}_{S,\mathbf{f},\ell}$ to $T$, can be described completely
with complexity

$(sd)^{(pn)^{O(\ell)}}\cdot(\mathrm{card}(T))^{2}.$

Once this description is obtained different invariants of the _finite_ poset
module $\mathbf{P}_{S,\mathbf{f},\ell}\restriction_{T}$, can be computed using
algorithms that have been developed for that purpose recently (see for
example, [48, 30, 29]). This computation will not involve any operations in
the ring of coefficients of the polynomials in $\mathcal{P}$ and
$\mathcal{Q}$, but only operations on elements of the field $\mathbf{k}$.

###  1.3. Speed of semi-algebraic multi-persistence modules

Our next result involves the notion of “speed” of semi-algebraic multi-
persistence modules that we introduce in this paper. In order to motivate it
we recall an important notion from graph theory that plays a guiding role.

####  1.3.1. Speed of semi-algebraic graphs

Suppose $F\subset\mathrm{R}^{p}\times\mathrm{R}^{p}$ be a _fixed_ semi-
algebraic relation (i.e. a semi-algebraic subset of
$\mathrm{R}^{p}\times\mathrm{R}^{p}$). A labelled (directed) graph
$(V,E\subset V\times V)$, with $V=\\{1,\ldots,N\\}$ is called an $F$-graph if
there exists $(\mathbf{y}_{1},\ldots,\mathbf{y}_{N})\in(\mathrm{R}^{p})^{N}$,
such that

$(i,j)\in E\Leftrightarrow(\mathbf{y}_{i},\mathbf{y}_{j})\in F.$

Families of $F$-graphs, where $F$ is a semi-algebraic relation, have been
studied in graph theory from several perspectives such as Ramsey theory,
Zarankiewicz problem etc. (see for example, [2, 33]). We will be concerned
with another very well-studied property, called “speed”, of such families.

The function $G_{F}:\mathbb{N}\rightarrow\mathbb{N}$, defined by

$G_{F}(N)=\mbox{ number of $F$-graphs with vertex set $[1,N]$}$

is called the _speed of the family of graphs defined by $F$_.

The following theorem (slightly simplified) is a key result in the theory of
semi-algebraic graphs.

######  Theorem.

[45, Theorem 1.2] For every semi-algebraic relation
$F\subset\mathrm{R}^{p}\times\mathrm{R}^{p}$,

$G_{F}(N)\leq N^{(1+o_{F}(N))pN}$

(where the $o_{F}(N)$ term depends on $F$). 111Theorem 1.2 in [45] is slightly
more general in that it gives a bound on the number of edge-labellings taking
values in some fixed finite set $\Lambda$. The Theorem stated here is the
special case when $\Lambda=\\{0,1\\}$.

There is obviously a compelling analogy between semi-algebraic families of
graphs semi-algebraically defined families of multi-persistence modules –
which leads naturally to the question whether there is an analog of the above
theorem for semi-algebraically defined families of multi-persistence modules
as well. We answer this question positively in this paper.

First, we need to specify when to call two poset modules equivalent.

######  Definition 1.7 (Strong and weak equivalence of poset modules).

We will say that two poset modules,

$\mathbf{P}^{\prime}:(P^{\prime},\preceq^{\prime})\rightarrow\mathrm{Vect}_{\mathbf{k}},\mathbf{P}^{\prime\prime}:(P^{\prime\prime},\preceq^{\prime\prime})\rightarrow\mathrm{Vect}_{\mathbf{k}},$

are _strongly equivalent_ if
$(P^{\prime},\preceq^{\prime})=(P^{\prime\prime},\preceq^{\prime\prime})$ and
the two functors $\mathbf{P}^{\prime},\mathbf{P}^{\prime\prime}$ are
isomorphic (see Definition 1.2).

We will say that two poset modules,

$\mathbf{P}^{\prime}:(P^{\prime},\preceq^{\prime})\rightarrow\mathrm{Vect}_{\mathbf{k}},\mathbf{P}^{\prime\prime}:(P^{\prime\prime},\preceq^{\prime\prime})\rightarrow\mathrm{Vect}_{\mathbf{k}},$

are _weakly equivalent_ if there is a poset isomorphism

$\phi:(P^{\prime},\preceq^{\prime\prime})\rightarrow(P^{\prime\prime},\preceq^{\prime\prime}),$

such that two poset modules

$\mathbf{P}^{\prime},\mathbf{P}^{\prime\prime}\circ\phi:P^{\prime}\rightarrow\mathrm{Vect}_{\mathbf{k}}$

are strongly equivalent.

Clearly, strong equivalence implies weak equivalence but not conversely.

######  Definition 1.8.

Suppose $S$ is a closed and bounded semi-algebraic set and
$\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ a continuous semi-algebraic map.

For $\ell\geq 0$, and any finite tuple

$T=(\mathbf{t}_{1},\ldots,\mathbf{t}_{N})\in(\mathrm{R}^{p})^{N},$

we denote by $\preceq_{T}$ the partial order on $\\{1,\ldots,N\\}$ defined by

$j\preceq_{T}j^{\prime}\Leftrightarrow\mathbf{t}_{j}\preceq\mathbf{t}_{j^{\prime}},$

and we denote

$\mathbf{P}_{S,\mathbf{f},T,\ell}:(\\{1,\ldots,N\\},\preceq_{T})\rightarrow\mathrm{Vect}_{\mathbf{k}}$

the poset module defined by

$\mathbf{P}_{S,\mathbf{f},T,\ell}(j)=\mbox{\rm
H}_{\ell}(S_{\mathbf{f}\preceq\mathbf{t}_{j}}).$

######  Theorem 2 (Speed of semi-algebraic multi-persistence).

Let $S\subset\mathrm{R}^{n}$ be a $\mathcal{P}$-closed bounded semi-algebraic
set and $\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ a $\mathcal{Q}$-closed
continuous semi-algebraic map. Then for every $\ell\geq 0$, and $N>0$ the
number of of strong (and hence also weak) equivalence classes amongst the
poset modules

$\mathbf{P}_{S,\mathbf{f},T,\ell},T\in(\mathrm{R}^{p})^{N}$

is bounded by

(1.1) $\sum_{j=1}^{pN}\binom{C\cdot N^{2}}{j}\cdot C^{pN}=N^{(1+o(N))pN},$

where $C=(sd)^{(np)^{O(\ell)}}$,
$s=\mathrm{card}(\mathcal{P})+\mathrm{card}(\mathcal{Q})$, and
$d=\max(\deg(\mathcal{P}),\deg(\mathcal{Q}))$.

######  Remark 4.

As in the preceding theorem, the $o(N)$ term depends on $S$ and $\mathbf{f}$ –
more precisely, on $s,d,n,\ell$, and $p$.

######  Remark 5.

(Tightness.) The bound in (1.1) is quite tight. Taking $S=[0,1]^{N}$, $p=1$,
$f=X$ and $\ell=0$, it is clear that the number of strong equivalence classes
$\mathbf{P}_{S,f,T,0}$, for $T\in[0,1]^{N}$ with pairwise distinct
coordinates, is $N!=N^{(1-o(1))N}$, since different orders of coordinates of
$T$ will give rise to distinct posets on $\\{1,\ldots,N\\}$ (i.e
$\preceq_{T}=\preceq_{T^{\prime}}$ if and only if $T$ and $T^{\prime}$ are
ordered identically).

The $N!$ is distinct posets are however all isomorphic. So the corresponding
modules all belong to one weak equivalence class. However, taking
$S=[0,1]^{2}$, $p=2$, $\mathbf{f}=(X_{1},X_{2})$ and $\ell=0$, it is not too
difficult to show that the number of weak equivalence classes
$\mathbf{P}_{S,\mathbf{f},T,0}$, for $T\in(\mathrm{R}^{2})^{N}$ is at least
$2^{N-1}$.

The number of distinct poset structures on a set with $N$ elements is known
asymptotically and is equal to $2^{N^{2}/4+o(N^{2}/4)}$ [38], while the number
of these realized as induced poset on an $N$ element subset of
$\mathrm{R}^{p}$ for any fixed $p$ is at most $N^{(1+o(1))pN}$ (consequence of
Theorem 2).

######  Remark 6.

It is instructive to compare Theorem 2 with its graph-theoretic counterpart
stated earlier. The family of $F$-graphs where $F$ is a fixed semi-algebraic
relation can include graphs with cycles, while the underlying graph of a poset
is acyclic. There are obviously fewer acyclic labelled directed graphs on $N$
vertices (or equivalently distinct poset structures) than all possible
labelled directed graphs on the same set of vertices. On the other hand in the
poset module case each directed edge is labelled by a vector space
homomorphism. We show later (see Example 2.1) that the choice of these
homomorphisms can make the number of strong (or even weak) equivalence classes
of poset modules for a fixed finite poset and a fixed upper bound on the
dimensions of the vector spaces allowed to appear, can be infinite even for
very simple posets and allowed dimensions $\leq 2$.

We also have the following uniform version of Theorem 2. While asymptotically
the bound is same, the dependence on the parameters $s,d,n,p$ is worse in the
following theorem compared to Theorem 2.

######  Theorem 3 (Uniform version of Theorem 2).

Let $s,d,n,p>0$ and $\ell\geq 0$ be fixed. Then the number of strong
equivalence classes amongst posets of the form
$\mathbf{P}_{S,\mathbf{f},T,\ell}$, $S$ is a bounded $\mathcal{P}$-closed
semi-algebraic set, and $\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ a
$\mathcal{Q}$-closed continuous semi-algebraic maps, for some

$\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq
d},\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p}]_{\leq
d},$

satisfying $\mathrm{card}(\mathcal{P})+\mathrm{card}(\mathcal{Q})\leq s$, and
$T\in(\mathrm{R}^{p})^{N}$, is bounded by

$N^{(1+o(N))pN}.$

###  1.4. Algorithm for computing semi-algebraic multi-persistence modules

Theorems 1, 2 and 3 will follow from an algorithmic result that we prove in
this paper.

####  1.4.1. Model of computation and definition of complexity

There are several models of computation that one can consider while dealing
with semi-algebraic sets (and also several notions of what constitutes an
algorithm). If the real closed field $\mathrm{R}=\mathbb{R}$, and $\mbox{\rm
D}=\mathbb{Z}$, one can consider these algorithmic problems in the classical
Turing model and measure the bit complexity of the algorithms. In this paper,
we will follow the book [8] and take a more general approach valid over
arbitrary real closed fields. In the particular case, when $\mbox{\rm
D}=\mathbb{Z}$, our method will yield bit-complexity bounds. The precise
notion of complexity that we use is defined in Definition 1.9 below.

We will use the following notion of “complexity” in this paper. We follow the
same definition as used in the book [8].

######  Definition 1.9 (Complexity of algorithms).

In our algorithms we will usually take as input quantifier-free first order
formulas whose terms are polynomials with coefficients belonging to an ordered
domain D contained in a real closed field $\mathrm{R}$. By _complexity of an
algorithm_ we will mean the number of arithmetic operations and comparisons in
the domain D. If $\mbox{\rm D}=\mathbb{R}$, then the complexity of our
algorithm will agree with the Blum-Shub-Smale notion of real number complexity
[21] 222 In case $\mbox{\rm D}=\mathbb{Z}$, it is possible to deduce the bit-
complexity of our algorithms in terms of the bit-sizes of the coefficients of
the input polynomials, and this will agree with the classical (Turing) notion
of complexity. We do not state the bit complexity separately in our
algorithms, but note that it is always bounded by a polynomial in the bit-size
of the input times the complexity upper bound stated in the paper. .

We are now in a position to state the main algorithmic result.

######  Theorem 4.

There exists an algorithm that takes as input:

  1. (a)

finite subsets $\mathcal{P}\subset\mbox{\rm
D}[X_{1},\ldots,X_{n}],\mathcal{Q}\subset\mbox{\rm
D}[X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p}]$;

  2. (b)

a $\mathcal{P}$-closed formula $\Phi$ with ${\mathcal{R}}(\Phi)$ denoted by
$S$;

  3. (c)

a $\mathcal{Q}$-closed formula $\Psi$, with
${\mathcal{R}}(\Psi)=\mathrm{graph}(\mathbf{f})$, where
$\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ a $\mathcal{Q}$-closed continuous
semi-algebraic map;

  4. (d)

$\ell\geq 0$,

and produces as output:

  1. (a)

finite subsets $\mathcal{C}\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p},Y_{1}^{\prime},\ldots,Y_{p}^{\prime}]$,
$\mathcal{D}\subset\mbox{\rm D}[Y_{1},\ldots,Y_{p}]$;

  2. (b)

for each $D\in\mathrm{Cc}(\mathcal{D})$, such that
$D\subset\mathrm{pairs}(\mathrm{R}^{p})$:

    1. (i)

there exists unique $C_{1}(D),C_{2}(D)\in\mathrm{Cc}(\mathcal{C})$, such that
$D\subset C_{1}(D)\times C_{2}(D)$;

    2. (ii)

for each $i,0\leq i\leq\ell$, a homomorphism

$\widetilde{\phi}_{D,i}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D)})\rightarrow\mbox{\rm H}_{i}(\Delta_{C_{2}(D)}).$

The homomorphisms $\widetilde{\phi}_{D,i}$ satisfy the following properties:

  1. 1.

for each $\mathbf{a}\in\mathrm{R}^{p}$, and $0\leq i\leq\ell$, there is an
isomorphism

$\widetilde{\psi}_{\mathbf{a},i}:\mbox{\rm
H}_{i}(S_{\mathbf{f}\preceq\mathbf{a}})\rightarrow\mbox{\rm
H}_{i}(\Delta_{C(\mathbf{a})}),$

where $C(\mathbf{a})\in\mathrm{Cc}(\mathcal{C})$ is the unique element of
$\mathrm{Cc}(\mathcal{C})$ such that $\mathbf{a}\in C(\mathbf{a})$;

  2. 2.

for each $D\in\mathrm{Cc}(\mathcal{D})$, and $(\mathbf{a},\mathbf{b})\in
D\cap\mathrm{pairs}(\mathrm{R}^{p})$, the following diagram commutes:

$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{f}\preceq\mathbf{a}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{\mathbf{a},\mathbf{b},i}}$$\scriptstyle{\widetilde{\psi}_{\mathbf{a},i}}$$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{f}\preceq\mathbf{b}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\psi}_{\mathbf{b},i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C_{1}(D)=C(\mathbf{a})})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\phi}_{k,i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C_{2}(D)=C(\mathbf{b})}).}$

The cardinalities and the degrees of the polynomials contained in them of
$\mathcal{C},\mathcal{D}$, as well as the complexity of this algorithm are
bounded by

$(sd)^{(pn)^{O(\ell)}},$

where $s=\mathrm{card}(\mathcal{P})+\mathrm{card}(\mathcal{Q})$, and
$d=\max(\deg(\mathcal{P}),\deg(\mathcal{Q}))$. Also, the sizes of the
simplicial complexes $\Delta_{C},C\in\mathrm{Cc}(\mathcal{C})$, are bounded by

$(sd)^{n^{O(\ell)}}.$

We obtain as a corollary to Theorem 4 the following algorithmic result that
given the description of a closed and bounded semi-algebraic set $S$, and a
continuous semi-algebraic map $\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ as
input, as well as a finite tuple of points $T\in(\mathrm{R}^{p})^{N}$,
produces an explicit desciption of the poset modules
$\mathbf{P}_{S,\mathbf{f},T,i}$ (see Definition 1.8).

Since we will also need to specify points in $\mathrm{R}^{p}$ which need not
belong to D, we introduce the following representations of such points (see
[8] for more details).

The following definitions are adapted from [8].

We begin with the representations of elements of $\mathrm{R}$ (which are
algebraic over D) as roots of polynomials in $\mbox{\rm D}[X]$ with a given
Thom encoding (cf. Definition 1.10 below).

######  Definition 1.10 (Thom encoding, associated element of $\mathrm{R}$).

For $P\in\mathrm{R}[X]$ we will denote by

${\rm Der}(P)=\left(P,P^{\prime},\ldots,P^{(\deg(P))}\right)$

the list of derivatives of $P$.

We will call a pair $\tau=(P,\sigma)$ with $\sigma\in\\{0,1,-1\\}^{{\rm
Der}(P)}$, the _Thom encoding of $x\in\mathrm{R}$_ 333It is a consequence of
the well-known Thom’s lemma, that the Thom encoding uniquely characterizes a
root in $\mathrm{R}$ of a polynomial in $\mbox{\rm D}[X]$ (see for example,
[8, Proposition 2.27]). , if $\sigma(P)=0$ and $\sigma(P^{(i)})=\mbox{\bf
sign}(P^{(i)}(x))$ for $0\leq i\leq\deg(P)$.

######  Definition 1.11 (Real univariate representations and associated
point).

A _real univariate representation_ $u$ in $\mathrm{R}^{p}$ is a pair
$(F,\sigma)$ where $F=(f,g_{0},g_{1},\ldots,g_{p})\in\mbox{\rm D}[T]$, with
$f(T),g_{0}(T)$ co-prime, and $\sigma$ a Thom encoding of a real root of
$f(T)\in\mathrm{R}[T]$.

We denote by $\mathrm{ass}(u)\in\mathrm{R}^{p}$ the point

(1.2)
$\left(\frac{g_{1}(\mathrm{ass}(\tau))}{g_{0}(\mathrm{ass}(\tau))},\ldots,\frac{g_{p}(\mathrm{ass}(\tau))}{g_{0}(\mathrm{ass}(\tau))}\right)\in\mathrm{R}^{p},$

where $\tau=(f,\sigma)$ (notice that $\tau$ is a Thom encoding), and call
$\mathrm{ass}(u)$ _the point associated to $u$_.

######  Corollary 1 (Algorithmic corollary).

There exists an algorithm that takes as input:

  1. (a)

finite subsets $\mathcal{P}\subset\mbox{\rm
D}[X_{1},\ldots,X_{n}],\mathcal{Q}\subset\mbox{\rm
D}[X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p}]$;

  2. (b)

a $\mathcal{P}$-closed formula $\Phi$ with ${\mathcal{R}}(\Phi)$ denoted by
$S$;

  3. (c)

a $\mathcal{Q}$-closed formula $\Psi$, with
${\mathcal{R}}(\Psi)=\mathrm{graph}(\mathbf{f})$, where
$\mathbf{f}:S\rightarrow\mathrm{R}^{p}$ a $\mathcal{Q}$-closed continuous
semi-algebraic map;

  4. (d)

$\ell\geq 0$;

  5. (e)

a finite tuple $\mathcal{T}$ of real univariate representations with the
corresponding tuple of associated points $T\subset\mathrm{R}^{p}$;

and produces as output: For each $i,0\leq i\leq\ell$,

  1. (a)

for each $\mathbf{t}\in T$, $n_{i,\mathbf{t}}\geq 0$;

  2. (b)

for each pair $\mathbf{p}=(\mathbf{t}_{1},\mathbf{t_{2}})\in T\times
T\cap\mathrm{pairs}(\mathrm{R}^{p})$, a matrix $M_{i,\mathbf{p}}\in
k^{n_{i,\mathbf{t}_{2}}\times n_{i,\mathbf{t}_{1}}}$,

such that $\mathbf{P}_{S,\mathbf{f},T,i}$ is isomorphic to the poset module
$\mathbf{P}_{i}:(T,\preceq|_{T})\rightarrow\mathrm{Vect}_{\mathbf{k}}$,
defined by

$\displaystyle\mathbf{P}_{i}(\mathbf{t})$ $\displaystyle=$
$\displaystyle\mathbf{k}^{n_{i,\mathbf{t}}},$
$\displaystyle\mathbf{P}_{i}(\mathbf{t}_{1}\preceq\mathbf{t_{2}})$
$\displaystyle=$ $\displaystyle L_{M_{i,\mathbf{p}}},$

(where we denote for any $M\in\mathbf{k}^{r\times s}$,
$L_{M}\in\mathrm{Hom}_{\mathbf{k}}(\mathbf{k}^{s},\mathbf{k}^{r})$ the linear
map whose matrix with respect to the standard bases of
$\mathbf{k}^{r},\mathbf{k}^{s}$ is $M$).

The complexity of this algorithm is bounded by
$N^{2}\cdot(sd)^{(pn)^{O(\ell)}}$, where
$s=\mathrm{card}(\mathcal{P})+\mathrm{card}(\mathcal{Q})$, and $d$ is maximum
of $\max(\deg(\mathcal{P}),\deg(\mathcal{Q}))$ and and the degrees of the
polynomials in the real univariate representations $\mathcal{T}$.

In particular, for fixed $s,d,n,p,\ell$ the complexity is bounded by
$O(N^{2})$.

##  2\. Background, significance and prior work

###  2.1. Algorithmic semi-algebraic geometry

The algorithmic problem of computing topological invariants of a given semi-
algebraic set described by a quantifier-free formula, whose atoms are of the
form, $P>0,P\in\mbox{\rm D}[X_{1},\ldots,X_{k}]$ is very well studied. These
include the problems of deciding emptiness, computing the number of semi-
algebraically connected components as as well as the higher Betti numbers, the
Euler-Poincaré characteristic etc. [46, 17, 4, 23, 24, 25]. More recently, in
[13], the authors give algorithms for computing a newer topological invariant
– namely, the _persistent homology barcodes_ of a filtration of a semi-
algebraic set, by the sub-level sets of a given continuous semi-algebraic
function. It is generalization of this latter result and some important
quantitative consequences that is the main topic of the current paper.

###  2.2. Complexity – singly vs doubly exponential

Complexity of algorithms for computing topological invariants will play a key
role in our results. We briefly survey the state-or-the art in the area of
algorithmic complexity of computing topological invariants of semi-algebraic
sets. These algorithms fall into classes.

####  2.2.1. Doubly exponential

First recall that closed and bounded semi-algebraic subsets
$S\subset\mathrm{R}^{n}$ are semi-algebraically triangulable – and moreover
given a description of the semi-algebraic set by a quantifier-free formula,
such a triangulation can be effectively computed with complexity (measured in
terms of the number $s$ of polynomials appearing in the description and their
maximum degree $d$) which is _doubly exponential_ in $n$ – more precisely
$(sd)^{2^{O(n)}}$. Together with standard algorithms of linear algebra, this
gives an algorithm for computing all the Betti numbers 444Here and everywhere
else in the paper all homology groups considered are with coefficients in a
fixed field $\mathbf{k}$. of a given semi-algebraic set with doubly
exponential complexity (we define “complexity of algorithms” more precisely
later in Definition 1.9). Computing Betti numbers of semi-algebraic sets using
the above method is not sensitive to the dimension of the homology – the
doubly exponential complexity persists even if we are interested in computing
the small Betti numbers only, even for example, the zero-th Betti number which
is just the number of semi-algebraically connected components.

####  2.2.2. Singly exponential

Classical bounds coming from Morse theory [44, 49, 43, 3, 34] gives _singly
exponential_ bounds on the Betti numbers of semi-algebraic sets. Additionally,
it is known that the problem of computing the zero-th Betti number of $S$
(i.e. the number of semi-algebraically components of $S$) (using “roadmap”
algorithms [26, 36, 6, 10, 18]), as well as the problem of computing the
Euler-Poincaré characteristic of $S$ (using Morse theory [3, 7]), both admit
single exponential complexity algorithms with complexities bounded by
$(O(sd))^{n^{O(1)}}$. This led to a search for algorithms with similar singly
exponential complexity bounds for computing the higher Betti numbers as well.
The current state of the art is that for each fixed $\ell\geq 0$, there exist
algorithms for computing the first $\ell$ Betti numbers of semi-algebraic sets
with complexity bounded by $(sd)^{n^{O(\ell)}}$ [4, 17, 12]. However, the best
complexity bound for an algorithm for computing all the (possibly non-zero)
Betti numbers of a semi-algebraic set in $\mathrm{R}^{n}$ is doubly
exponential in $n$ (i.e. with complexity $(sd)^{2^{O(n)}}$) [46, 5]. More
recently algorithms with singly exponential complexity has been obtained for
several other problems in semi-algebraic geometry: for computing a semi-
algebraic basis of the first homology group of a semi-algebraic set [16], for
computing the homology functor on diagrams of semi-algebraic sets for fixed
dimensional homology groups [14], and most relevant to this paper – computing
the low dimensional barcodes of filtrations of semi-algebraic sets by semi-
algebraic functions [13]. The importance of developing singly exponential
complexity algorithms is not restricted just to computational considerations.
Efforts towards developing such algorithms often lead to uncovering of
interesting mathematical properties of semi-algebraic sets which are of
independent interest (see Remark 8).

######  Remark 7.

Algorithms for computing the Betti numbers of semi-algebraic sets have also
been developed in other (numerical) models of computations [23, 24, 25] with
precise complexity estimates. However, in these results the complexity depends
on the condition number of the input, and the algorithm will fail for ill-
conditioned input when the condition number becomes infinite. Such algorithms
are also quite distinct from the point of view of techniques from the kind of
algorithms we consider in the current paper, which are supposed to work for
all inputs (and all ordered rings of coefficients, including non-Archimedean
ones) and with uniform complexity upper bounds (i.e. depending only on the
number and degrees of the input polynomials, and independent of their
coefficients). So these approaches are not comparable. There has not been any
attempt to extend the numerical algorithms mentioned above for computing Betti
numbers to computing persistent homology of semi-algebraic filtrations. Such
an extension would necessarily involve defining a good notion of a “condition
number of a semi-algebraic filtration” which has not been attempted to the
best of our knowledge. Moreover, note that numerical algorithms typically do
not produce quantitative mathematical results – for example, Theorems 2 and 3
in the current paper, as well as many other such results (see Remark 8), as
byproducts.

###  2.3. Semi-algebraic persistence: the case $p=1$

Given a closed and bounded semi-algebraic set $S\subset\mathrm{R}^{n}$ and a
continuous semi-algebraic function $f:S\rightarrow\mathrm{R}$ and $\ell\geq
0$, the functor $\mathbf{P}_{S,f,\ell}$ is characterized up to equivalence by
a finite set of intervals $(a,b)$ and associated multiplicities $\mu_{a,b}>0$.
The set of these intervals and their multiplicities is usually called the
$\ell$-dimensional “barcode” of the persistent module $\mathbf{P}_{S,f,\ell}$,
and for each fixed $\ell$, a singly exponential algorithm for computing the
barcode of the $i$-dimensional persistent module for an arbitrary semi-
algebraic filtration is given in [13].

We will not define barcodes for continuous semi-algebraic filtrations
precisely here since they will not play an important role in the current paper
(we refer the interested reader to [13] for an elementary exposition). The
main result of [13] can reformulated to give a particular case of Theorem 4.
Note that in the special case with $p=1$, the partition underlying the
corresponding semi-algebraically constructible function can be taken to be of
a particularly simple kind – namely, a partition of
$\mathrm{pairs}(\mathrm{R})$ into intersection of rectangles in
$\mathrm{R}\times\mathrm{R}$ with $\mathrm{pairs}(\mathrm{R})$. This result
was not stated in terms of constructible functions in [13].

###  2.4. Significance of Theorems 1 and 4 and Corollary 1

Semi-algebraic filtrations appear in many natural applications (see for
example, the applications discussed in [13] and [40] and more recently in [1,
Open Questions (ix), page 433]). It is important in these applications to have
explicit algorithms for obtaining a complete description of the poset module
structure and the reduction to the finite sub-modules. The definition of
complexity of the poset module associated to a semi-algebraic multi-filtration
is an important measure of the inherent complexity of this module, and its
algorithmic significance is explained in the next paragraph. The singly
exponential upper bound on this complexity proved in Theorem 1 is reminiscent
of singly exponential upper bounds on the Betti numbers of semi-algebraic sets
[44, 49, 43, 34]. Similarly, the singly exponential upper bound on the
algorithmic complexity of describing the poset module structure in Theorem 4,
extends to the case $p>1$, the similar result in the case $p=1$ proved in [13]
(as well as singly exponential algorithms for computing Betti numbers of emi-
algebraic sets in the non-persistent setting [12, 17, 4]). It should be noted
that the extension to the case $p>1$ is not an obvious one – since the partial
order $\preceq$ on $\mathrm{R}^{p}$ is not a total order when $p>1$, and as a
result the resulting constructible function on
$\mathrm{pairs}(\mathrm{R}^{p})$, associated to a filtration, is forced to
have a more complicated structure. On the other hand, dealing with multi-
filtrations is quite important in practice [28, 27, 47].

Given a semi-algebraic multi-filtration (which is a poset module on the
infinite poset $\mathrm{R}^{p}$), it becomes an important problem to describe
the structure of the induced sub-poset-module structure on finite subposets of
$\mathrm{R}^{p}$. Corollary 1 implies that this structure can be computed with
complexity only quadratic in the size of the finite poset (assuming that the
complexity of the given filtration to be constant). It is to be noted that
after one application of the algorithm in Theorem 4, for any given tuple of
points $T\in(\mathrm{R}^{p})^{N}$, the computation of the induced poset module
$\mathbf{P}_{S,\mathbf{T},T,\ell}$ involves computations only in
$\mathrm{R}^{p}$ rather in the original ambient space $\mathrm{R}^{n}$. This
is important since in practice $p$ is usually much smaller than $n$.

###  2.5. Significance of Theorems 2 and 3

####  2.5.1. Finite vs infinite

Observe that in the case of (labelled directed) graphs, the number of distinct
graphs with vertex set $\\{1,\ldots,N\\}$ (with possible self loops but no
multiple edges) is clearly finite and equal to $2^{N^{2}}$.

For finite persistence modules, i.e. functors $\mathbf{P}$ from a finite poset
to $\mathrm{Vect}_{\mathbf{k}}$, the situation is a bit nuanced. Suppose that
we fix a finite poset $P$, and restrict the functor
$\mathbf{P}:P\rightarrow\mathrm{Vect}_{\mathbf{k}}$ to only those for which

(2.1) $\dim\mathbf{P}(a)\leq M,a\in P,$

for some fixed $M\geq 0$. Now if $P$ is linearly ordered, then the isomorphism
class of $\mathbf{P}:P\rightarrow\mathrm{Vect}_{\mathbf{k}}$ is determined by
the ranks of the various $\mathbf{P}(a\preceq b)$, and since these ranks can
take values only between $0$ and $M$, the number of isomorphism classes of
functors $\mathbf{P}:P\rightarrow\mathrm{Vect}_{\mathbf{k}}$ satisfying (2.1)
is clearly finite.

However, this finiteness statement is not true for more general poset modules.
Consider the following example.

######  Example 2.1.

Let $\mathbf{k}$ be an infinite field. Consider the poset $P$ with Hasse
diagram:

$\textstyle{v}$$\textstyle{w\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{z\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

Let $a,b\in\mathbf{k}$ not both zero, and consider the poset module
$\mathbf{P}_{a,b}:P\rightarrow\mathrm{Vect}_{\mathbf{k}}$ with

$\mathbf{P}_{a,b}(v)=\mathbf{k}^{2},\mathbf{P}_{a,b}(w)=\mathbf{P}_{a,b}(x)=\mathbf{P}_{a,b}(y)=\mathbf{P}_{a,b}(z)=\mathbf{k},$
$\displaystyle\mathbf{P}_{a,b}(w\rightarrow v)$ $\displaystyle=$
$\displaystyle[1,0]^{t},$ $\displaystyle\mathbf{P}_{a,b}(x\rightarrow v)$
$\displaystyle=$ $\displaystyle[0,1]^{t},$
$\displaystyle\mathbf{P}_{a,b}(y\rightarrow v)$ $\displaystyle=$
$\displaystyle[1,1]^{t},$ $\displaystyle\mathbf{P}_{a,b}(z\rightarrow v)$
$\displaystyle=$ $\displaystyle[a,b]^{t}$

(where the right hand side denotes the matrices of the corresponding elements
of $\mathrm{Hom}_{\mathbf{k}}(\mathbf{k},\mathbf{k}^{2})$ with respect to the
standard bases).

######  Claim 2.1.

If $[a:b]\neq[c:d]$ as points of $\mathbb{P}^{1}_{\mathbf{k}}$, then the poset
modules $\mathbf{P}_{a,b},\mathbf{P}_{c,d}$ are not isomorphic. Thus, there
are infinitely many distinct isomorphic classes of poset modules
$\mathbf{P}:P\rightarrow\mathrm{Vect}_{\mathbf{k}}$, satisfying

$\mathbf{P}(v)=\mathbf{k}^{2},\mathbf{P}(w)=\mathbf{P}(x)=\mathbf{P}(y)=\mathbf{P}(z)=\mathbf{k}.$

###### Proof.

Let $F:\mathbf{P}_{a,b}\rightarrow\mathbf{P}_{c,d}$ be an equivalence, and let
$\tau=F(v)\in\mathrm{Aut}(\mathbf{k}^{2})$. Then $\tau$ must carry the lines
spanned by $(1,0)^{t}$, $(0,1)^{t}$ and $(1,1)^{t}$ to themselves, and so must
be a multiple of the identity. So the line spanned by $(a,b)^{t}$ gets mapped
to the line spanned by $(c,d)^{t}$ by $\tau$ if and only if they are equal
i.e. $[a:b]=[c:d]$. ∎

It follows from Example 2.1 that the number of strong (or even weak)
equivalence classes of poset modules on a fixed poset can be infinitely large
even if we restrict the dimensions of the vector spaces to $\leq 2$.

Thus, even the finiteness of the bound in Theorems 2 and 3 on the speed of
semi-algebraic multi-persistence is not obvious except in the case $p=1$.

Finally, unlike in the case where $p=1$, where we have a classification of all
semi-algebraic persistence modules using the fundamental theorem of finitely
generated $\mathbf{k}[X]$-modules (see for instance, [51]), the situation in
the case $p>1$ is much more complicated, since there is no nice classification
of irreducible modules in these cases. There is a large body of work aimed
towards obtaining computable invariants in the case of multi-parameter
persistent modules over finite posets [41, 30, 29, 22]. In this context it is
important to know that finite poset modules arising from semi-algebraic multi-
filtrations are a very special subclass amongst all poset modules on the same
poset. In analogy with graph theory ([2, 33], it might be interesting to prove
special properties of this sub-class. We do not pursue this problem in this
paper.

######  Remark 8.

We note here that often in algorithmic semi-algebraic geometry, analysing the
complexity of a new algorithm, produces quantitative mathematical results
which are of independent interest For example, this approach has been used to
prove a quantitative curve selection lemma [19], bounds on the radius of a
ball guaranteed to intersect every connected component of a given semi-
algebraic set [9], and more recently effective bounds on the Łojasiewicz’s
exponent [15] amongst other such results. In the same vein, Theorems 2 and 3
of this paper can be viewed as consequences of the main algorithmic result –
namely, Theorem 4 and its corollary, Corollary 1.

###  2.6. Prior work

Persistent homology is a central object in the emerging field of topological
data analysis [31, 50, 35], but has also found applications in diverse areas
of mathematics and computations as well (see for example [32, 39]). One can
associate persistent homology groups to any filtration of topological spaces,
and they generalize ordinary homology groups of a space $X$ – which correspond
to the trivial (i.e. constant) filtration on $X$. Much of the earlier work on
the topic mentioned above are in the case of one parameter persistence.

More recently, study of multi-parameter persistence modules and their
decomposition into irreducible sub-modules of special types have become a very
important object of research and is a very active area of research. The study
of semi-algebraic persistent homology using as tools traditional algorithms in
real algebraic geometry is more recent and originates in [13], where the case
of $1$-parameter persistence in the semi-algebraic setting was investigated
from an algorithmic point of view. A more abstract approach, valid for even
sub-analytic sets and filtrations is taken in [37, 42], where the theory of
constructible sheaves play a crucial role. The results in these papers are
very fundamental but are not quantitative/algorithmic as in the main theorems
of the current paper.

##  3\. Proofs of Theorems 1 and 4

###  3.1. Algorithmic Preliminaries

####  3.1.1. Algorithm for enumerating $\mathrm{Cc}(\mathcal{P})$

One basic algorithm with singly exponential complexity is an algorithm that
given a finite set $\mathcal{P}\subset\mbox{\rm D}[X_{1},\ldots,X_{n}]$ as
input computes a finite set of points guaranteed to intersect every
$C\in\mathrm{Cc}(\mathcal{P})$ (see for example [8, Algorithm 13.2
(Sampling)]). This algorithm in conjunction with an algorithm (see for example
[8, Algorithm 16.4 (Uniform Roadmap)]) for computing roadmaps of semi-
algebraic sets, gives an algorithm for computing exactly one point in every
$C\in\mathrm{Cc}(\mathcal{P})$ – and thus also enumerate the elements of
$\mathrm{Cc}(\mathcal{P})$. Taking into account the complexity of [8,
Algorithm 13.2 (Sampling)]) and [8, Algorithm 16.4 (Uniform Roadmap)]), the
complexity of the resulting algorithm is bounded by $(sd)^{n^{O(1)}}$, where
$s=\mathrm{card}(\mathcal{P})$ and $d=\deg(\mathcal{P})$. We are going to use
this algorithm for enumerating the elements of $\mathrm{Cc}(\mathcal{P})$ and
computing exactly one point in each $C\in\mathrm{Cc}(\mathcal{P})$ implicitly
without mentioning in the description of the more complicated algorithms that
we describe later.

####  3.1.2. Parametrized versions of algorithms in real algebraic geometry

Many algorithms in real algebraic geometry (see for example [8, Chapters
13-16]) have the following form. They take as input a finite set $\mathcal{P}$
of polynomials with coefficients in an ordered domain D contained in a real
closed field $\mathrm{R}$, and also a $\mathcal{P}$-formula, and produces as
output discrete objects (for example, a list of sign conditions on a set of
polynomials, or a simplicial complex etc. or some topological invariant like
the Betti numbers of the $\mathcal{P}$-semi-algebraic set specified in the
input etc.), as well as some algebraically defined objects, such as set of
points represented by real univariate representations, or a set of semi-
algebraic curves represented by parametrized real univariate representations,
or even more generally semi-algebraic maps whose graphs are described by
formulas. We will refer to these parts as discrete and the algebraic parts of
the output.

Each step of the algorithm consists of performing an arithmetic operation in
$D$ or testing the sign of an element of D.

We will need to use _parametrized versions_ of three different algorithms.

By parametrized version of a given algorithm $\mathbf{A}$ with parameters
$Y=(Y_{1},\ldots,Y_{p})$ we mean an algorithm that takes as input a finite set
$\mathcal{P}$ of polynomials with coefficients in $\mbox{\rm
D}[Y_{1},\ldots,Y_{p}]$ (instead of D). The output of the algorithm consists
of two parts.

  1. (a)

A finite set $\mathcal{F}\subset\mbox{\rm D}[Y_{1},\ldots,Y_{p}]$, having the
property that for each $C\in\mathrm{Cc}(\mathcal{F})$, the discrete part of
the output of the Algorithm $\mathbf{A}$, with input
$\mathcal{P}(\mathbf{y},\cdot)$, is the same for all $\mathbf{y}\in C$;

  2. (b)

For each $C\in\mathrm{Cc}(\mathcal{F})$:

    1. (1)

the discrete part of the output of Algorithm $\mathbf{A}$ with input
$\mathcal{P}(\mathbf{y},\cdot)$ some (or all) $\mathbf{y}\in C$ (so this is
constant as $\mathbf{y}$ varies over $C$);

    2. (2)

the (varying) algebraic part of the output of Algorithm $\mathbf{A}$
parametrized by $Y$, given by formula(s), $\psi_{C}(Y)$ so that for all
$\mathbf{y}\in C$, the output of Algorithm $\mathbf{A}$ with input
$\mathcal{P}(\mathbf{y},\cdot)$ is obtained by specializing $Y$ to
$\mathbf{y}$ i.e. is equal to $\psi_{C}(\mathbf{y})$.

######  Example 3.1 (Basic example 1: $\mathrm{Elim}_{X}$).

Let $\mathcal{P}\subset\mbox{\rm D}[Y_{1},\ldots,Y_{p},X]_{\leq d}$ and

$\phi(Y_{1},\ldots,Y_{p},X)$

be a $\mathcal{P}$-closed formula so that ${\mathcal{R}}(\phi(\mathbf{y},X)$
is bounded for all $\mathbf{y}\in\mathrm{R}^{p}$. We consider the problem of
parametrized triangulation of
${\mathcal{R}}(\phi(\mathbf{y},X))\subset\mathrm{R}$ as $\mathbf{y}$ varies
over $Y$. Let $\mathcal{F}=\mathrm{Elim}_{X}(\mathcal{P})\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p}]$ where $\mathrm{Elim}_{X}(\mathcal{P})$ is defined in
[8, Notation 5.15]. The for each $C\in\mathrm{Cc}(\mathcal{F})$, there exists
continuous semi-algebraic functions
$\xi_{1},\ldots,\xi_{M_{C}}:C\rightarrow\mathrm{R}$, with
$\xi_{1}<\ldots<\xi_{M_{C}}$, and such that for each $\mathbf{y}\in C$,
$\xi_{1}(\mathbf{y})<\cdots<\xi_{M_{C}}(\mathbf{y})$ are the ordered set of
real roots of all the polynomials in $\mathcal{P}(\mathbf{y},X)$ which are not
identically $0$ on $C$ [8, Theorem 5.16]. Thus, one obtains a triangulation
(i.e. closed intervals and their end-points) of
${\mathcal{R}}(\phi(\mathbf{y},X))$ which has the same combinatorial structure
for all $\mathbf{y}\in C$.

It follows from the definition of $\mathcal{F}$ that
$\mathrm{card}(\mathcal{F})\leq sd^{O(1)}$, and $\deg(\mathcal{F})\leq
d^{O(1)}$. Finally, the complexity of the parametrized algorithm for
triangulating a semi-algebraic subset of $\mathrm{R}$, is bounded by
$(sd)^{O(p)}$.

####  3.1.3. Parametrized algorithm for computing semi-algebraic triangulation

The technique described in Example 3.1 can be extended iteratively (see [8,
Chapter 5]) to obtain an algorithm for triangulating closed and bounded semi-
algebraic sets in higher dimensions. More precisely, we will use a
parametrized version of the following algorithm.

Algorithm 1 (Triangulation of semi-algebraic sets)

1:

2:

  1. (a)

a finite set of $s$ polynomials ${\mathcal{P}}\subset\mbox{\rm
D}[X_{1},\ldots,X_{n}]$;

  2. (b)

${\mathcal{P}}$-formulas $\phi_{1},\ldots,\phi_{N}$ such that for each
$i,1\leq i\leq N$, ${\mathcal{R}}(\phi)$ is a closed and bounded semi-
algebraic set.

3:

4:

  1. (a)

A finite set of polynomials
$\mathcal{Q}\subset\mathrm{R}[X_{1},\ldots,X_{n}]$;

  2. (b)

a finite simplicial complex $K$, and subcomplexes $K_{1},\ldots,K_{N}\subset
K$;

  3. (c)

a $\mathcal{Q}$-formula, $\psi$, such that ${\mathcal{R}}(\psi)$ is the graph
of a semi-algebraic homeomorphism $h:|K|\rightarrow\bigcup_{i=1}^{N}S_{i}$,
which restricts to a semi-algebraic homeomorphisms
$h_{i}=h|_{|K|}:|K_{i}|\rightarrow{\mathcal{R}}(\phi_{i})$.

5:The complexity of the algorithm is bounded by $N(sd)^{2^{O(n)}}$, and the
size of the simplicial complex $\Delta$ is also bounded by $(sd)^{2^{O(n)}}$.

The parametrized version of Algorithm 1 will output a finite subset

$\mathcal{F}\subset\mbox{\rm D}[Y_{1},\ldots,Y_{p}],$

with

$\mathrm{card}(\mathcal{F})\leq(sd)^{2^{O(n)}},\deg(\mathcal{F})\leq
d^{2^{O(n)}},$

as well as a finite set of polynomials
$\mathcal{Q}\subset\mathrm{R}[Y_{1},\ldots,Y_{p},X_{1},\ldots,X_{n}]$, and for
each $C\in\mathrm{Cc}(\mathcal{F})$,

  1. (a)

a finite simplicial complex $K_{C}$, and subcomplexes
$K_{C,1},\ldots,K_{C,N}\subset K_{C}$;

  2. (b)

a $\mathcal{Q}$-formula, $\psi_{C}$, such that
${\mathcal{R}}(\psi_{C}(\mathbf{y},X)$ is the graph of a semi-algebraic
homeomorphism
$h_{C}:|K_{C}|\rightarrow\bigcup_{i=1}^{N}{\mathcal{R}}(\phi_{i}(\mathbf{y},X))$,
which restricts to a semi-algebraic homeomorphisms
$h_{C,i}=h|_{|K_{C}|}:|K_{C,i}|\rightarrow{\mathcal{R}}(\phi_{i}(\mathbf{y},X))$.

The complexity of this parametrized algorithm is bounded by

(3.1) $(sd)^{2^{O(n)}p^{O(1)}}.$

The parametrized version (with parameters $Y=(Y_{1},\ldots,Y_{p})$) is
obtained by following the same algorithm as the unparametrized case with $n+p$
variables, applying the $\mathrm{Elim}_{X_{i}}$ operator successively for
$i=n,n-1,\ldots,1$ and taking $\mathcal{F}\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p}]$ the resulting family of polynomials. In order to
obtain a triangulation one needs to make also a linear change in the
$X$-coordinates which we are overlooking here ([8, Chapter 5] for details).
The complexity of the algorithm is obtained by tracking the degree and the
cardinality of the sets of polynomials obtained after applying the
$\mathrm{Elim}_{X_{i}}$ operators, and these square at each step leading to a
doubly exponential (in $n$) complexity.

######  Example 3.2 (Basic Example 2: $\mathrm{BElim}_{X}$).

The method of applying the $\mathrm{Elim}_{X}$ operator explained in Example
3.1 one variable at a time leads to doubly exponential complexity. There is a
more efficient algorithm which is the basis of all singly exponential
algorithm, which is based on the “critical point method” that is used to
eliminate a block of variables at one time.

Given $\mathcal{P}\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p},X_{1},\ldots,X_{n}]_{\leq d}$, there exists a finite set

$\mathcal{F}:=\mathrm{BElim}_{X}(\mathcal{P})\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p}]$

(see [8, Algorithm 14.1] for a precise definition) such that for each
$C\in\mathrm{Cc}(\mathcal{F})$, the set $\mbox{\rm
Sign}(\mathcal{P}(\mathbf{y},X))$ stay invariant as $\mathbf{y}$ varies of $C$
[8]. Moreover, $\mathrm{card}(\mathcal{F})\leq s^{n+1}d^{O(n)}$,
$\deg(\mathcal{F})\leq d^{O(n)}$. While the property ensured by
$\mathrm{BElim}_{X}$ is weaker than that in the case of repeated application
of $\mathrm{Elim}_{X}$, it is still the basis of (the parametrized versions)
of several singly exponential complexity algorithms that we will use later
(Algorithms 3 and 4).

###  3.2. Outline of the proof

In order to explain the idea behind the proof of Theorem 4 better, we first
describe an algorithm that satisfies the requirements of Theorem 4, except
that its complexity is bounded by $(sd)^{2^{O(n)}p^{O(1)}}$ which is doubly
exponential – rather than $(sd)^{(pn)^{O(\ell)}}$ as in Theorem 4. The doubly
exponential complexity arises from using a semi-algebraic triangulation
algorithm which has inherently doubly exponential complexity (but is easier to
understand). Later we will replace the triangulation by a weaker construction
– namely, parametrized algorithm for simplicial replacement ( Algorithm 4)
which is sufficient for our purposes and has the right complexity, but more
difficult to visualize.

We also need the following basic facts from algebraic topology.

######  Definition 3.1 (Closed cover associated to a triangulation).

Given a semi-algebraic triangulation $h:|\Delta|\rightarrow S$, where $S$ is a
closed and bounded semi-algebraic set, we denote by $\mathrm{Cov}(h)$ the
covering of $S$ by the images of the closed simplices of $|\Delta|$.

######  Definition 3.2 (Nerve of a closed cover).

Given a cover $C$ of a closed and bounded semi-algebraic set $S$, we denote by
$\mathcal{N}(C)$, the nerve complex of $C$. We say that $C$ is a good cover if
each element of $C$ is semi-algebraically contractible. In particular, if
$h:|\Delta|\rightarrow S$ is a semi-algebraic triangulation then,
$\mathrm{Cov}(h)$ is a good cover.

The following proposition is classical (see for example [20]).

######  Proposition 3.1 (Nerve Lemma).

If $C$ is a good cover of $S$, then there is a canonical isomorphism
$\psi_{C}:\mbox{\rm H}_{*}(\mathcal{N}(C))\rightarrow\mbox{\rm H}_{*}(S)$.

One immediate corollary is the following.

######  Corollary 2.

There is a canonical isomorphism

$\psi_{\mathrm{Cov}(h)}:\mbox{\rm
H}_{*}(\mathcal{N}(\mathrm{Cov}(h)))\rightarrow\mbox{\rm H}_{*}(S).$

###### Proof.

Follows from Definitions 3.1and 3.2, and Proposition 3.1. ∎

######  Proposition 3.2.

If $C^{\prime}\subset C$ are two good covers of a closed and bounded semi-
algebraic set $S$, then $\mathcal{N}(C^{\prime})\subset\mathcal{N}(C)$, and
the induced map $\mbox{\rm H}_{*}(\mathcal{N}(C^{\prime}))\rightarrow\mbox{\rm
H}_{*}(\mathcal{N}(C))$ is an isomorphism.

###### Proof.

We have the following commutative diagram

$\textstyle{\mbox{\rm
H}_{*}(\mathcal{N}(C^{\prime}))\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{C^{\prime}}}$$\textstyle{\mbox{\rm
H}_{*}(\mathcal{N}(C))\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi_{C}}$$\textstyle{\mbox{\rm
H}_{*}(S)}$

where the $\psi_{C}^{\prime},\psi_{C}$ are isomorphisms using Proposition 3.1.
This implies that the horizontal arrow is an isomorphism as well. ∎

######  Definition 3.3 (Refinement of a semi-algebraic triangulation).

Given two semi-algebraic triangulations $h_{1}:|\Delta_{1}|\rightarrow S$,
$h_{2}:|\Delta_{2}|\rightarrow S$, we say that $h_{2}$ is a refinement of
$h_{1}$, if the image by $h_{2}$ of every closed simplex of $|\Delta_{2}|$ is
contained in the image by $h_{1}$ of some some closed simplex of $\Delta_{1}$.

######  Proposition 3.3.

Suppose $h_{1},h_{2}$ are two triangulations of a closed and bounded semi-
algebraic set $S$ such that $h_{2}$ is a refinement of $h_{1}$. Then,
$\mathrm{Cov}(h_{1})\cup\mathrm{Cov}(h_{2})$ is s good cover of $S$, and the
following diagram, where the vertical arrow is induced by inclusion is
commutative and all arrows are isomorphisms:

$\textstyle{\mathcal{N}(\mathrm{Cov}(h_{1})\cup\mathrm{Cov}(h_{2}))\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\;\;\Psi_{\mathrm{Cov}(h_{1})\cup\mathrm{Cov}(h_{2})}}$$\textstyle{\mbox{\rm
H}_{*}(S)}$$\textstyle{\mathcal{N}(\mathrm{Cov}(h_{1}))\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\Psi_{\mathrm{Cov}(h_{1})}}$

###### Proof.

Follows from Propositions 3.1 and 3.2. ∎

####  3.2.1. Algorithm for semi-algebraic multi-persistence using effective
semi-algebraic triangulation

We first outline the main idea.

We first obtain a semi-algebraic partition of $\mathrm{R}^{p}$, and over each
element (say $C$) of the partition, a simplicial complex $K_{C}$, such that
for all $\mathbf{y}\in C$, $S_{\mathbf{y}}$ is semi-algebraically homeomorphic
to $|K_{C}|$ (we denote by $|\cdot|$ the geometric realization of a simplicial
complex as a polyhedron in some $\mathrm{R}^{N}$). This first step uses
parametrized version of Algorithm 1(Semi-algebraic triangulation) and is
implemented in Line 8. We work with the $(\ell+1)$-skeleton of the nerve
complex of the induced closed covering – and we denote this simplicial complex
by $\Delta_{C}$ (Line 10). There is thus (using Proposition 3.1) a canonical
isomorphism $\widetilde{\psi}_{C,\mathbf{y},i}:\mbox{\rm
H}_{i}(S_{\mathbf{y}})\rightarrow\mbox{\rm H}_{i}(\Delta_{C})$ for all
$\mathbf{y}\in C$ and $0\leq i\leq\ell$.

For $(\mathbf{y},\mathbf{y}^{\prime})\in C\times
C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})$, there is _does not exist_ any
canonically defined homomorphism $\widetilde{\phi}_{C,C^{\prime},i}:\mbox{\rm
H}_{i}(\Delta_{C})\rightarrow\mbox{\rm H}_{i}(\Delta_{C^{\prime}})$ such that
the following diagram commutes for every $(\mathbf{y},\mathbf{y}^{\prime})\in
C\times C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})$:

$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{y}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{\mathbf{y},\mathbf{y}^{\prime},i}}$$\scriptstyle{\widetilde{\psi}_{\mathbf{y},i}}$$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{y}^{\prime}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\psi}_{\mathbf{y}^{\prime},i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\phi}_{C,C^{\prime},i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C^{\prime}})}$

In order to obtain homomorphisms between $\mbox{\rm H}_{*}(C)$ and $\mbox{\rm
H}_{*}(\Delta_{C^{\prime}})$ making the above diagram to commute, we further
partition semi-algebraically $C\times
C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})$. Our tool is again the
parametrized version of Algorithm 1. Using it we obtain parametrically with
$(\mathbf{y},\mathbf{y}^{\prime})\in C\times
C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})$ as parameter, refinement of the
triangulations $K_{C},K_{C^{\prime}}$. This leads to a further partition of
$C\times C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})$, so that in each part
$D$ of this partition, and $(\mathbf{y},\mathbf{y}^{\prime})\in D$, we have a
triangulation of $S_{\mathbf{y}^{\prime}}$ which is a refinement of the
triangulation of $C^{\prime}$ obtained in the previous step, and also its
restriction to $C$ is a refinement of the triangulation obtained in the
previous step. Denoting the $(\ell+1)$-skeleton of the nerve complex of the
cover induced by this new triangulation $\Delta_{D}$, we have that both
$\Delta_{C}$ and $\Delta_{C^{\prime}}$ are in a natural way sub-complexes of
$\Delta_{D}$, and there are canonical isomorphisms (using Proposition 3.3),
$\mbox{\rm H}_{i}(S_{\mathbf{y}})\rightarrow\mbox{\rm H}(\Delta_{D}^{0})$,
$\mbox{\rm H}_{i}(S_{\mathbf{y}^{\prime}})\rightarrow\mbox{\rm H}(\Delta_{D})$
(where $\Delta_{D}^{0}\subset\Delta_{D}$ is the subcomplex corresponding to
the inclusion $S_{\mathbf{y}}\subset S_{\mathbf{y}^{\prime}}$). This step is
implemented in Line 11 of the algorithm.

Notice, that now we also have canonically defined _isomorphisms_ , $\mbox{\rm
H}_{i}(\Delta_{C})\rightarrow\mbox{\rm H}_{i}(\Delta_{D}^{0})$, $\mbox{\rm
H}_{i}(\Delta_{C^{\prime}})\rightarrow\mbox{\rm H}_{i}(\Delta_{D})$, induced
by the inclusion of a subcomplex in another, and also a canonically defined
homomorphism, $\mbox{\rm H}_{i}(\Delta_{D}^{0})\rightarrow\mbox{\rm
H}_{i}(\Delta_{D})$ (also induced by inclusion) that depends on $D$ but is
independent of the choice of $(\mathbf{y},\mathbf{y}^{\prime})\in D$. In short
we have, for all $(\mathbf{y},\mathbf{y}^{\prime})\in D$, a commutative
diagram where all solid arrows are canonically defined:

(3.2) $\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{y}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{\mathbf{y},\mathbf{y}^{\prime},i}}$$\scriptstyle{\cong}$$\scriptstyle{\widetilde{\psi}_{\mathbf{y},i}}$$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{y}^{\prime}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\cong}$$\scriptstyle{\widetilde{\psi}_{\mathbf{y}^{\prime},i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{D}^{0})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\cong}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{D})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\cong}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\phi}_{C,C^{\prime},D,i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C^{\prime}})}$

The dotted arrow is then uniquely defined as the one which makes the whole
diagram commute – and we define it to be the homomorphism
$\widetilde{\phi}_{C,C^{\prime},D,i}$ (Line 14). Notice that for all
$\mathbf{y}\preceq\mathbf{y}^{\prime}\preceq\mathbf{y}^{\prime\prime}$, with
$\mathbf{y}\in C,\mathbf{y}^{\prime}\in
C^{\prime},\mathbf{y}^{\prime\prime}\in C^{\prime\prime}$, and
$(\mathbf{y},\mathbf{y}^{\prime})\in
D,(\mathbf{y}^{\prime},\mathbf{y}^{\prime\prime})\in
D^{\prime},(\mathbf{y}^{\prime},\mathbf{y}^{\prime\prime})\in
D^{\prime\prime}$ we have the commutative diagram:

$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{y}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{\mathbf{y},\mathbf{y}^{\prime},i}}$$\scriptstyle{\widetilde{\psi}_{\mathbf{y}}}$$\scriptstyle{\iota_{\mathbf{y},\mathbf{y}^{\prime\prime},i}}$$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{y}^{\prime}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\iota_{\mathbf{y}^{\prime},\mathbf{y}^{\prime\prime},i}}$$\scriptstyle{\widetilde{\psi}_{\mathbf{y}^{\prime}}}$$\textstyle{\mbox{\rm
H}_{i}(S_{\mathbf{y}^{\prime\prime}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\psi}_{\mathbf{y}^{\prime\prime}}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\phi}_{C,C^{\prime},D,i}}$$\scriptstyle{\widetilde{\phi}_{C,C^{\prime\prime},D^{\prime\prime},i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C^{\prime}})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\widetilde{\phi}_{C^{\prime},C^{\prime\prime},D^{\prime},i}}$$\textstyle{\mbox{\rm
H}_{i}(\Delta_{C^{\prime\prime}})}$

These are the key steps. The rest of the steps of the algorithm consists of
using standard algorithms from linear algebra to compute bases of the various
$\mbox{\rm H}_{i}(\Delta_{C})$, $\mbox{\rm H}_{i}(\Delta_{C^{\prime}})$
$\mbox{\rm H}_{i}(\Delta_{D}^{0})$, $\mbox{\rm H}_{i}(\Delta_{D})$, and the
matrices with respect to these bases of the maps between these spaces induced
by refinements and inclusions (the solid arrows in the bottom square of the
commutative diagram (3.2)), and finally the matrices of the maps
$\widetilde{\phi}_{C,C^{\prime},D,i}$ (shown by the dotted arrow in (3.2)).

The complexity of the above algorithm is dominated by the complexity of the
calls to the parametrized version of the semi-algebraic triangulation
algorithm. Each such call costs $(sd)^{2^{O(n)}p^{O(1)}}$ – and which is also
asymptotically an upper bound on the total complexity.

Notice that the upper bound on the complexity is doubly exponential in $n$ and
independent of $\ell$.

We now describe more formally the algorithm outlined above.

Algorithm 2 (Semi-algebraic multi-persistence using triangulations)

1:

2: As stated in Theorem 4.

3:

4: As stated in Theorem 4.

5:

6: Denote  $\displaystyle\widetilde{S}$ $\displaystyle=$
$\displaystyle\\{(\mathbf{x},\mathbf{y})\in\mathrm{R}^{n}\times\mathrm{R}^{p}\mid\mathbf{x}\in
S,\mathbf{f}(\mathbf{x})\preceq\mathbf{y}\\}.$

7: Let $\widetilde{S}={\mathcal{R}}(\widetilde{\phi})$, where
$\widetilde{\phi}$ is a closed formula which is obtained from the closed
formulas describing $S$ and $\mathrm{graph}(\mathbf{f})$ in a straightforward
way.

8: Using the parametrized version of Algorithm 1, with
$Y=(Y_{1},\ldots,Y_{p})$ as parameters and the formula
${\mathcal{R}}(\widetilde{\phi})$ as input to obtain:

  1. (a)

a finite set of polynomials $\mathcal{C}\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p}]$;

  2. (b)

for each $C\in\mathrm{Cc}(\mathcal{C})$:

    1. (i)

a simplicial complex $K_{C}$;

    2. (ii)

a formula $\Phi_{C}(Y,\cdot)$, such that for each $\mathbf{y}\in C$,
${\mathcal{R}}(\Phi(\mathbf{y},\cdot))$ equals the graph of a semi-algebraic
homeomorphism

$h_{C,\mathbf{y}}:|K_{C}|\rightarrow\widetilde{S}_{\mathbf{y}}.$

9: For each simplex $\tau$ of $K_{C}$, denote by $\Psi_{C,\tau}(Y,X)$, the
formula obtained in an obvious way from $\Phi_{C}$, such that for each
$\mathbf{y}\in C$,
${\mathcal{R}}(\Psi_{C,\tau}(\mathbf{y},X))=h_{C,\mathbf{y}}(|\tau|)$.

10: For each $\mathbf{y}\in C,C\in\mathrm{Cc}(\mathcal{C})$, denote
$\Delta_{C}=\mathrm{sk}_{\ell+1}(\mathcal{N}(\mathrm{Cov}(h_{C},\mathbf{y}))),$
noting that this definition depends only on $C$ and independent of the choice
of $\mathbf{y}\in C$. $\triangleright$ Note that, for $\mathbf{y}\in C$, and
$0\leq i\leq\ell$, there is a isomorphism (depending only on
$h_{C,\mathbf{y}}$)  $\widetilde{\psi}_{C,\mathbf{y},i}:\mbox{\rm
H}_{i}(\widetilde{S}_{\mathbf{y}})\rightarrow\mbox{\rm H}_{i}(\Delta_{C}).$

11: For each pair $C,C^{\prime}\in\mathrm{Cc}(\mathcal{C})$, such that
$C\times C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})\neq\emptyset,$ using
parametrized version of Algorithm 1 again, with parameters
$(Y,Y^{\prime})=(Y_{1},\ldots,Y_{p},Y_{1}^{\prime},\ldots,Y_{p}^{\prime}),$
and input  $(\Psi_{C,\tau})_{\tau\in
K_{C}}\cup(\Psi_{C^{\prime},\tau})_{\tau\in K_{C^{\prime}}},$ obtain:

  1. (a)

a finite set of polynomials $\mathcal{D}_{C,C^{\prime}}\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p},Y_{1}^{\prime},\ldots,Y_{p}^{\prime}]$, (we will also
assume without loss of generality, by including them if necessary, that the
polynomials $Y_{i}^{\prime}-Y_{i},1\leq i\leq p$ belong to
$\mathcal{D}_{C,C^{\prime}}$);

  2. (b)

for each $E\in\mathrm{Cc}(\mathcal{D}_{C,C^{\prime}})$ such that

$C\times C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})\cap E\neq\emptyset,$

a formula

$\Phi_{C,C^{\prime},E}(Y,Y^{\prime},\cdot),$

such that for each $(\mathbf{y},\mathbf{y}^{\prime})\in C\times
C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})\cap E$,

${\mathcal{R}}(\Phi_{C,C^{\prime},E}(\mathbf{y},\mathbf{y}^{\prime},\cdot))$

equals the graph of a semi-algebraic triangulation

$h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}:|K_{C,C^{\prime},E}|\rightarrow\widetilde{S}_{\mathbf{y}^{\prime}}.$

Moreover, $h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}$ refines the
semi-algebraic triangulation $h_{C,\mathbf{y}^{\prime}}$, and the restriction,
$h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}^{0}$, of
$h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}$ to
$h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}^{-1}(\widetilde{S}_{\mathbf{y}})$,
is a refinement of the triangulation $h_{C,\mathbf{y}}$.

$\triangleright$ Note that the simplicial complexes
$\mathcal{N}(\mathrm{Cov}(h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}^{0}))\subset\mathcal{N}(\mathrm{Cov}(h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}))$
are independent of the choice of $\mathbf{y},\mathbf{y}^{\prime}$.) Denote
$\Delta_{C,C^{\prime},E}^{0}=\mathrm{sk}_{\ell+1}(\mathcal{N}(\mathrm{Cov}(h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}^{0}))),$
$\Delta_{C,C^{\prime},E}^{0}=\mathrm{sk}_{\ell+1}(\mathcal{N}(\mathrm{Cov}(h_{C,C^{\prime},E,\mathbf{y},\mathbf{y}^{\prime}}^{0}))),$
noting that $\Delta_{C,C^{\prime},D}^{0}\subset\Delta_{C,C^{\prime},D}$.

12: Denote
$\mathcal{D}=\mathcal{C}(Y)\cup\mathcal{C}(Y^{\prime})\cup\bigcup_{(C,C^{\prime})}\mathcal{D}_{C,C^{\prime}},$
where the last union is taken over all $(C,C^{\prime})$ such that $C\times
C\cap\mathrm{pairs}(\mathrm{R}^{p})\neq\emptyset$. Note that for each
$D\in\mathrm{Cc}(\mathcal{D})$, there exists, uniquely defined
$C_{1}(D),\mathrm{C}_{2}(D)\in\mathrm{Cc}(\mathcal{C})$, and
$E(D)\in\mathrm{Cc}(\mathcal{D}_{\sigma,\sigma^{\prime}})$ such that
$D\subset\mathrm{C}_{1}(D)\times C_{2}(D)\cap E(D)$.

13: For each $D\in\mathrm{Cc}(\mathcal{D})$, such that
$D\subset\mathrm{pairs}(\mathrm{R}^{p})$, and for $0\leq i\leq\ell$, let
$\phi_{D,i,0}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)}^{0})\rightarrow\mbox{\rm
H}_{i}(\Delta_{C_{1}(D)}),$ and  $\phi_{D,i,1}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)})\rightarrow\mbox{\rm
H}_{*}(\Delta_{C_{2}(D)}),$ denote the canonical isomorphisms induced by
refinement, and  $\iota_{D,i}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)}^{0})\rightarrow\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)})$ the homomorphism induced by
inclusion.

14: Denote
$\widetilde{\phi}_{D,i}:=\phi_{D,i,1}\circ\iota_{D,i}\circ\phi_{D,i,0}^{-1}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D))})\rightarrow\mbox{\rm H}_{i}(\Delta_{C_{2}(D)}).$

15: Output bases of the finite dimensional vector spaces  $\mbox{\rm
H}_{i}(\Delta_{C}),C\in\mathrm{Cc}(\mathcal{C}),0\leq i\leq\ell,$ and matrices
with respect to the above bases for the linear maps  $\widetilde{\phi}_{D,i},$
$D\in\mathrm{Cc}(\mathcal{D})$, such that
$D\subset\mathrm{pairs}(\mathrm{R}^{p})$, and $0\leq i\leq\ell$.

16:The complexity of the algorithm is bounded by  $(sd)^{2^{O(n)}p^{O(1)}}.$
Moreover, the cardinalities and the degrees of the polynomials in them, of
$\mathcal{C},\mathcal{D}$, are all bounded by  $(sd)^{2^{O(n)}p^{O(1)}}.$

######  Proposition 3.4.

The sets $\mathcal{C},\mathcal{D}$, and the homomorphisms
$\widetilde{\psi}_{C,\mathbf{y},i},\widetilde{\phi}_{D,i}$ computed by
algorithm described above satisfy the conditions (1) and (2) of Theorem 4. The
complexity of the algorithm is bounded by $(sd)^{2^{O(n)}p^{O(1)}}$, where
$s=\mathrm{card}(\mathcal{P})+\mathrm{card}(\mathcal{Q})$, and
$d=\max(\deg(\mathcal{P}),\deg(\mathcal{Q}))$.

###### Proof.

The claims on the conditions (1) and (2) follow from the commutativity of the
diagram (3.2), which in turn follows from the definitions of the homomorphisms
$\widetilde{\psi}_{\mathbf{y},i}$ and $\widetilde{\phi}_{C,C^{\prime},D,i}$
and the correctness of the parametrized version of Algorithm 1.

The complexity bound follows from the complexity of Algorithm 1 given in
(3.1). ∎

###  3.3. Proofs of Theorems 1, 4 and Corollary 1

As noted above the bound on the complexity of Algorithm 2 is doubly
exponential in $n$ (and independent of $\ell$). We will now describe a more
refined version of Algorithm 2 whose complexity for any fixed $\ell$ is only
singly exponential in $n$.

The main new ingredient is to use a different algorithm – namely, a
parametrized version of the _simplicial replacement algorithm_ which is
described in [12] instead of the parametrized version of the semi-algebraic
triangulation algorithm. The main advantage of using the simplicial
replacement algorithm is that its complexity for any fixed $\ell$ is only
singly exponential in $n$ (unlike the semi-algebraic triangulation algorithm).

In order to apply the simplicial replacement algorithm we first rely on
another algorithm – namely an algorithm for computing a cover by contractible
semi-algebraic sets described in [12] (Algorithm 1).

####  3.3.1. Parametrized algorithm for computing cover by contractible sets

To a first approximation this algorithm takes as input the description of a
closed and bounded semi-algebraic set and produces as output descriptions of
closed semi-algebraic sets, whose union is the given set and each of whom is
semi-algebraically contractible. However, for technical reasons (explained in
detail in [12]) the algorithm only succeeds in producing a cover by semi-
algebraically contractible sets of an infinitesimally larger set than the
given one – which nonetheless has the same homotopy type.

In order to describe more precisely the output of this algorithm because of
this unfortunate complication we need a technical detour.

#####  _Real closed extensions and Puiseux series_.

We will need some properties of Puiseux series with coefficients in a real
closed field. We refer the reader to [8] for further details.

######  Notation 3.1.

For $\mathrm{R}$ a real closed field we denote by
$\mathrm{R}\left\langle{\varepsilon}\right\rangle$ the real closed field of
algebraic Puiseux series in ${\varepsilon}$ with coefficients in $\mathrm{R}$.
We use the notation
$\mathrm{R}\left\langle{\varepsilon}_{1},\ldots,{\varepsilon}_{m}\right\rangle$
to denote the real closed field
$\mathrm{R}\left\langle{\varepsilon}_{1}\right\rangle\left\langle{\varepsilon}_{2}\right\rangle\cdots\left\langle{\varepsilon}_{m}\right\rangle$.
Note that in the unique ordering of the field
$\mathrm{R}\left\langle{\varepsilon}_{1},\ldots,{\varepsilon}_{m}\right\rangle$,
$0<{\varepsilon}_{m}\ll{\varepsilon}_{m-1}\ll\cdots\ll{\varepsilon}_{1}\ll 1$.

######  Notation 3.2.

For elements $x\in\mathrm{R}\left\langle{\varepsilon}\right\rangle$ which are
bounded over $\mathrm{R}$ we denote by $\lim_{{\varepsilon}}x$ to be the image
in $\mathrm{R}$ under the usual map that sets ${\varepsilon}$ to $0$ in the
Puiseux series $x$.

######  Notation 3.3.

If $\mathrm{R}^{\prime}$ is a real closed extension of a real closed field
$\mathrm{R}$, and $S\subset\mathrm{R}^{k}$ is a semi-algebraic set defined by
a first-order formula with coefficients in $\mathrm{R}$, then we will denote
by ${\rm ext}(S,\mathrm{R}^{\prime})\subset\mathrm{R}^{\prime k}$ the semi-
algebraic subset of $\mathrm{R}^{\prime k}$ defined by the same formula. It is
well known that ${\rm ext}(S,\mathrm{R}^{\prime})$ does not depend on the
choice of the formula defining $S$ [8, Proposition 2.87].

######  Notation 3.4.

Suppose $\mathrm{R}$ is a real closed field, and let $X\subset\mathrm{R}^{k}$
be a closed and bounded semi-algebraic subset, and
$X^{+}\subset\mathrm{R}{\langle}{\varepsilon}{\rangle}^{k}$ be a semi-
algebraic subset bounded over $\mathrm{R}$. Let for $t\in\mathrm{R},t>0$,
$\widetilde{X}^{+}_{t}\subset\mathrm{R}^{k}$ denote the semi-algebraic subset
obtained by replacing ${\varepsilon}$ in the formula defining $X^{+}$ by $t$,
and it is clear that for $0<t\ll 1$, $\widetilde{X}^{+}_{t}$ does not depend
on the formula chosen. We say that $X^{+}$ is _monotonically decreasing to
$X$_, and denote $X^{+}\searrow X$ if the following conditions are satisfied.

  1. (a)

for all $0<t<t^{\prime}\ll 1$,
$\widetilde{X}^{+}_{t}\subset\widetilde{X}^{+}_{t^{\prime}}$;

  2. (b)

$\bigcap_{t>0}\widetilde{X}^{+}_{t}=X;$

or equivalently $\lim_{\varepsilon}X^{+}=X$.

More generally, if $X\subset\mathrm{R}^{k}$ be a closed and bounded semi-
algebraic subset, and
$X^{+}\subset\mathrm{R}{\langle}{\varepsilon}_{1},\ldots,{\varepsilon}_{m}{\rangle}^{k}$
a semi-algebraic subset bounded over $\mathrm{R}$, we will say $X^{+}\searrow
X$ if and only if

$X^{+}_{m+1}=X^{+}\searrow X^{+}_{m},\;X^{+}_{m}\searrow
X^{+}_{m-1},\ldots,X^{+}_{2}\searrow X^{+}_{1}=X,$

where for $i=1,\ldots,m$, $X^{+}_{i}=\lim_{{\varepsilon}_{i}}X^{+}_{i+1}$.

The unparametrized version of the algorithm for computing a cover by
contractible sets, takes as input a closed formula $\phi$, such that
${\mathcal{R}}(\phi)$ is bounded, and produces as output a tuple
$\Phi=(\phi_{1},\ldots,\phi_{M})$ of closed formulas with coefficients in
$\mbox{\rm D}[\bar{\varepsilon}]$, such that
${\mathcal{R}}(\phi_{j})\subset\mathrm{R}{\langle}\bar{\varepsilon}{\rangle}^{n},j\in[1,M]$
are semi-algebraically contractible, and
${\mathcal{R}}(\phi)=\searrow\bigcup_{j}{\mathcal{R}}(\phi_{j})$.

We list the input and output and complexity of the parametrized version. The
complexity statement follows from an analysis of the complexity of the
unparametrized version [8, Algorithm 16.14], and also a careful analysis of
[8, Algorithm 16.5 (Parametrized bounded connecting)] that it relies on, which
in turn relies on the $\mathrm{BElim}_{X}$ operator whose properties were
discussed earlier (Example 3.2).

Algorithm 3 (Parametrized algorithm for computing cover by contractible sets )

1:

2:

  1. (a)

An element $R\in\mbox{\rm D},R>0$;

  2. (b)

a finite set $\mathcal{P}\subset\mbox{\rm
D}[X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p}]_{\leq d}$;

  3. (c)

a $\mathcal{P}$-closed formula $\phi(X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p})$,
such that for each $\mathbf{y}\in\mathrm{R}^{p}$,
${\mathcal{R}}(\phi(X,\mathbf{y}))\subset\overline{B_{n}(0,R)}$.

3:

4:

  1. (a)

a finite subset $\mathcal{F}\subset\mbox{\rm D}[Y_{1},\ldots,Y_{p}]$;

  2. (b)

for each realizable sign condition $\sigma\in\\{0,1,-1\\}^{\mathcal{F}}$, a
tuple $\Phi_{\sigma}=(\phi_{\sigma,1},\ldots,\phi_{\sigma,M_{\sigma}})$, and
where each
$\phi_{\sigma,j}=\phi_{\sigma,j}(X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p})$ is a
closed formulas with free variables $X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p}$,
with coefficients in $\mbox{\rm D}[\bar{\varepsilon}]$, such that for each
$\mathbf{y}\in{\mathcal{R}}(\sigma)$, and $j\in J$,
${\mathcal{R}}(\phi_{\sigma,j}(X_{1},\ldots,X_{n},\mathbf{y}))$ is semi-
algebraically contractible, and
${\mathcal{R}}(\phi_{\sigma})=\searrow\bigcup_{j}{\mathcal{R}}(\phi_{\sigma,j})$.

5:The complexity of the algorithm is bounded by $(sd)^{(pn)^{O(1)}}$, where
$s=\mathrm{card}(\mathcal{P})$.

####  3.3.2. Parametrized simplicial replacement algorithm

In order to describe the input and output of the simplicial replacement
algorithm we need a few preliminary definitions. In the following we will
restrict ourselves to the category of closed and bounded semi-algebraic sets
and semi-algebraic continuous maps between them.

######  Definition 3.4 (Semi-algebraic homological $\ell$-equivalences).

We say that a semi-algebraic continuous map $f:X\rightarrow Y$ between two
closed and bounded semi-algebraic sets is a semi-algebraic homological
$\ell$-equivalence, if the induced homomorphisms between the homology groups
$f_{*}:\mbox{\rm H}_{i}(X)\rightarrow\mbox{\rm H}_{i}(Y)$ are isomorphisms for
$0\leq i\leq\ell$.

The relation of semi-algebraic homological $\ell$-equivalence as defined above
is not an equivalence relation since it is not symmetric. In order to make it
symmetric one needs to “formally invert” semi-algebraic homological
$\ell$-equivalences.

######  Definition 3.5 (Semi-algebraically homologically $\ell$-equivalent).

We will say that _$X$ is semi-algebraically homologically $\ell$-equivalent to
$Y$_ (denoted $X\sim_{\ell}Y$), if and only if there exists closed and bounded
semi-algebraic sets, $X=X_{0},X_{1},\ldots,X_{n}=Y$ and semi-algebraic
homological $\ell$-equivalences $f_{1},\ldots,f_{n}$ as shown below:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
8.93471pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 32.93471pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
9.17047pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
8.93472pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
62.3878pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
74.80412pt\raise-30.6848pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
80.73883pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 116.67354pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
92.9093pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
92.67355pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
145.34354pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{4}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
158.54295pt\raise-32.37524pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
158.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
233.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{X_{n-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
208.64914pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n-1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
209.54295pt\raise-32.77734pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
266.66278pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
280.64037pt\raise-30.98157pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
286.85573pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-8.93471pt\raise-39.0pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{0}}$}}}}}}}{\hbox{\kern
38.86942pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
74.80412pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{2}}$}}}}}}}{\hbox{\kern
122.60825pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
158.54295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
242.09166pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
280.64037pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{n}}$}}}}}}}{\hbox{\kern
323.07109pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

It is clear that $\sim_{\ell}$ is an equivalence relation.

We now extend Definition 3.4 to semi-algebraic continuous maps between closed
and bounded semi-algebraic sets.

######  Definition 3.6 (Homological $\ell$-equivalence between semi-algebraic
maps).

Let $f_{1}:X_{1}\rightarrow Y_{1},f_{2}:X_{2}\rightarrow Y_{2}$ be continuous
semi-algebraic maps between closed and bounded semi-allgebraic sets. A semi-
algebraic homological $\ell$-equivalence from $f_{1}$ to $f_{2}$ is then a
pair $\phi=(\phi^{(1)},\phi^{(2)})$ where $\phi^{(1)}:X_{1}\rightarrow
X_{2},\phi^{(2)}:Y_{1}\rightarrow Y_{2}$ are semi-algebraic homological
$\ell$-equivalences, and such that $f_{2}\circ\phi_{1}=\phi_{2}\circ f_{1}$.

We will say that a semi-algebraic map $f$ is semi-algebraically homologically
$\ell$-equivalent to a semi-algebraic map $g$ (denoted as before by
$f\sim_{\ell}g$), if and only if there exists semi-algebraic continuous maps
$f=f_{0},f_{1},\ldots,f_{n}=g$ between closed and bounded semi-algebraic sets,
and semi-algebraic homological $\ell$-equivalences $\phi_{1},\ldots,\phi_{n}$
as shown below:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
7.38612pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 31.38612pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{f_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
7.21529pt\raise-13.42471pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{\phi_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
7.38614pt\raise-31.57059pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
58.15837pt\raise-13.42471pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{\phi_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
70.15837pt\raise-31.57782pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
74.5445pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 108.93062pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{f_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
84.75978pt\raise-13.42471pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{\phi_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
84.93063pt\raise-31.57059pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
135.3848pt\raise-13.5202pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{\phi_{4}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
147.70287pt\raise-32.10498pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
147.70287pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
185.20287pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
222.70287pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{f_{n-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
196.76454pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{\phi_{n-1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
198.70287pt\raise-32.54004pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
253.1313pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{\phi_{n}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
266.70311pt\raise-31.83487pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
271.36989pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-7.38612pt\raise-39.0pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{f_{0}}$}}}}}}}{\hbox{\kern
35.77225pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
70.15837pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{f_{2}}$}}}}}}}{\hbox{\kern
113.31674pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
147.70287pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
185.20287pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
229.70299pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
266.70311pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{f_{n}}$}}}}}}}{\hbox{\kern
306.03667pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

It is clear that $\sim_{\ell}$ is an equivalence relation.

######  Definition 3.7 (Diagrams of closed and bounded semi-algebraic sets).

A diagram of closed and bounded semi-algebraic sets is a functor,
$X:J\rightarrow\mathbf{SA}$, from a small category $J$ to the category of
closed and bounded semi-algebraic sets and continuous semi-algebraic maps
between them.

We extend Definition 3.4 to diagrams of closed and bounded semi-algebraic
sets. We denote by $\mathbf{SA}_{\mathrm{R}}$ the category of closed and
bounded semi-algebraic subsets of $\mathrm{R}^{n},n>0$ and continuous semi-
algebraic maps between them.

######  Definition 3.8 (Semi-algebraic homological $\ell$-equivalence between
diagrams of closed and bounded semi-algebraic sets).

Let $J$ be a small category, and $X,Y:J\rightarrow\mathbf{SA}_{\mathrm{R}}$ be
two functors. We say a natural transformation $f:X\rightarrow Y$ is an semi-
algebraic homological $\ell$-equivalence, if the induced maps,

$f(j)_{*}:\mbox{\rm H}_{i}(X(j))\rightarrow\mbox{\rm H}_{i}(Y(j))$

are isomorphisms for all $j\in J$ and $0\leq i\leq\ell$.

We will say that _a diagram $X:J\rightarrow\mathbf{SA}_{\mathrm{R}}$ is
$\ell$-equivalent to the diagram $Y:J\rightarrow\mathbf{SA}_{\mathrm{R}}$_
(denoted as before by $X\sim_{\ell}Y$), if and only if there exists diagrams
$X=X_{0},X_{1},\ldots,X_{n}=Y:J\rightarrow\mathbf{SA}_{\mathrm{R}}$ and semi-
algebraic homological $\ell$-equivalences $f_{1},\ldots,f_{n}$ as shown below:

$\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
8.93471pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 32.93471pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
9.17047pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
8.93472pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
62.3878pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{2}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
74.80412pt\raise-30.6848pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
80.73883pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 116.67354pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{3}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
92.9093pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{3}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
92.67355pt\raise-30.67606pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
145.34354pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{4}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
158.54295pt\raise-32.37524pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
158.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
233.54295pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{X_{n-1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
208.64914pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n-1}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
209.54295pt\raise-32.77734pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
266.66278pt\raise-13.3889pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{f_{n}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
280.64037pt\raise-30.98157pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}{\hbox{\kern
286.85573pt\raise 0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-8.93471pt\raise-39.0pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{X_{0}}$}}}}}}}{\hbox{\kern
38.86942pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
74.80412pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{2}}$}}}}}}}{\hbox{\kern
122.60825pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
158.54295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
196.04295pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{\cdots}$}}}}}}}{\hbox{\kern
242.09166pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
280.64037pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{X_{n}}$}}}}}}}{\hbox{\kern
323.07109pt\raise-39.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}\ignorespaces}}}}\ignorespaces.$

It is clear that $\sim_{\ell}$ is an equivalence relation.

One particular diagram will be important in what follows.

######  Notation 3.5 (Diagram of various unions of a finite number of
subspaces).

Let $J$ be a finite set, $A$ a closed and bounded semi-algebraic set, and
$\mathcal{A}=(A_{j})_{j\in J}$ a tuple of closed and bounded semi-algebraic
subsets of $A$ indexed by $J$.

For any subset $J^{\prime}\subset J$, we denote

$\displaystyle\mathcal{A}^{J^{\prime}}$ $\displaystyle=$
$\displaystyle\bigcup_{j^{\prime}\in J^{\prime}}A_{j^{\prime}},$
$\displaystyle\mathcal{A}_{J^{\prime}}$ $\displaystyle=$
$\displaystyle\bigcap_{j^{\prime}\in J^{\prime}}A_{j^{\prime}},$

We consider $2^{J}$ as a category whose objects are elements of $2^{J}$, and
whose only morphisms are given by:

$\displaystyle 2^{J}(J^{\prime},J^{\prime\prime})$ $\displaystyle=$
$\displaystyle\emptyset\mbox{ if }J^{\prime}\not\subset J^{\prime\prime},$
$\displaystyle 2^{J}(J^{\prime},J^{\prime\prime})$ $\displaystyle=$
$\displaystyle\\{\iota_{J^{\prime},J^{\prime\prime}}\\}\mbox{ if
}J^{\prime}\subset J^{\prime\prime}.$

We denote by
$\mathbf{Simp}^{J}(\mathcal{A}):2^{J}\rightarrow\mathbf{SA}_{\mathrm{R}}$ the
functor (or the diagram) defined by

$\mathbf{Simp}^{J}(\mathcal{A})(J^{\prime})=\mathcal{A}^{J^{\prime}},J^{\prime}\in
2^{J},$

and $\mathbf{Simp}^{J}(\mathcal{A})(\iota_{J^{\prime},J^{\prime\prime}})$ is
the inclusion map
$\mathcal{A}^{J^{\prime}}\hookrightarrow\mathcal{A}^{J^{\prime\prime}}$.

####  3.3.3. Parametrized algorithm for simplicial replacement

The original (i.e. unparametrized) algorithm takes as input a tuple of closed
formulas, $\Phi=(\phi_{1},\ldots,\phi_{M})$, such that the realizations,
${\mathcal{R}}(\phi_{j})\subset\mathrm{R}^{n},j\in J=[0,M]$ are all semi-
algebraically contractible, and $m\geq 0$. It produces as output a simplicial
complex $\Delta=\Delta^{J}$, having a subcomplex $\Delta^{J^{\prime}}$ for
each $J^{\prime}\subset J$, with
$\Delta^{J^{\prime}}\subset\Delta^{J^{\prime\prime}}$ whenever
$J^{\prime}\subset J^{\prime\prime}\subset J$, and such that the diagram of
inclusions

$(|\Delta^{J^{\prime}}|\hookrightarrow|\Delta^{J^{\prime\prime}}|)_{J^{\prime}\subset
J^{\prime\prime}\subset J}$

is homologically $m$-equivalent to the diagram of inclusions

$({\mathcal{R}}(\Phi^{J^{\prime}})\hookrightarrow{\mathcal{R}}(\Phi^{J^{\prime\prime}}))_{J^{\prime}\subset
J^{\prime\prime}\subset J}$

where for $J^{\prime}\subset J$, $\Phi^{J^{\prime}}=\bigvee_{j\in
J^{\prime}}\phi_{j}$.

We will need a _parametrized version_ of the above algorithm which we will
call the parametrized algorithm for simplicial replacement. We describe the
input, output and the complexity of this algorithm below.

The complexity of the parametrized version follows from analysing the
complexity analysis of the unparametrized version in [12], which has a
recursive structure of depth $O(\ell)$. At each level of the recursion, there
are calls to (the unparametrized version of) Algorithm 3, on certain
intersections of sets computed in the previous steps of the recursion. The
complexity bound of the parametrized version now follows using the complexity
bound, $(sd)^{(pn)^{O(1)}}$, of Algorithm 3 (parametrized algorithm for
computing cover by contractible sets), noting that the depth of the recursion
in Algorithm 4 is $O(\ell)$, instead of using that of the the unparametrized
version Algorithm 3 as is done in [12]. We omit the details since they are
quite tedious.

Algorithm 4 (Parametrized algorithm for simplicial replacement)

1:

2:

  1. (a)

$\ell\geq 0$;

  2. (b)

An element $R\in\mbox{\rm D},R>0$;

  3. (c)

a finite set $\mathcal{P}\subset\mbox{\rm
D}[X_{1},\ldots,X_{n},Y_{1},\ldots,Y_{p}]_{\leq d}$;

  4. (d)

For each $j,1\leq j\leq M$, a $\mathcal{P}$-formula $\phi_{j}$, such that
${\mathcal{R}}(\phi_{j},\overline{B_{k}(0,R)})$ is closed and bounded, and
semi-algebraically contractible.

3:

4:

  1. (a)

a finite subset $\mathcal{F}\subset\mbox{\rm D}[Y_{1},\ldots,Y_{p}]$;

  2. (b)

for each $C\in\mathrm{Cc}(\mathcal{F})$, A simplicial complex $\Delta_{C}$,
and subcomplexes $\Delta_{C,J^{\prime}},J^{\prime}\subset J=[1,M]$, such that
for each $J^{\prime}\subset J^{\prime\prime}\subset J$,
$\Delta_{\sigma,J^{\prime}}\subset\Delta_{C,J^{\prime\prime}}$ and the diagram
of inclusions
$|\Delta_{C,J^{\prime}}|\hookrightarrow|\Delta_{C,J^{\prime\prime}}|,J^{\prime}\subset
J^{\prime\prime}\subset J$ is semi-algebraically homologically
$\ell$-equivalent to $\mathbf{Simp}^{J}({\mathcal{R}}(\Phi))$, where $\Phi$ is
defined by $\Phi(j)=\phi_{j},j\in[1,M]$.

5:The complexity of the algorithm is bounded by $(sd)^{(pn)^{O(\ell)}}$, where
$s=\mathrm{card}(\mathcal{P})$.

We now return to the proof of Theorem 4. We will prove the theorem by
describing an algorithm with input and output as specified by the theorem and
then proving its correctness and upper bounds on the complexity. The following
algorithm will avoid using the semi-algebraic triangulation algorithm (and its
inherently doubly exponential complexity). Instead, we will use the
parametrized algorithm for simplicial replacement (Algorithm 4) described
above.

Algorithm 5 (Semi-algebraic multi-persistence using simplicial replacement)

1:

2: As stated in Theorem 4.

3:

4: As stated in Theorem 4.

5:

6: Denote  $\displaystyle\widetilde{S}$ $\displaystyle=$
$\displaystyle\\{(\mathbf{x},\mathbf{y})\in\mathrm{R}^{n}\times\mathrm{R}^{p}\mid\mathbf{x}\in
S,\mathbf{f}(\mathbf{x})\preceq\mathbf{y}\\}.$

7: Let $\widetilde{S}={\mathcal{R}}(\widetilde{\phi})$, where
$\widetilde{\phi}$ is a closed formula which is obtained from the closed
formulas describing $S$ and $\mathrm{graph}(\mathbf{f})$ in a straightforward
way.

8: Treating $Y_{1},\ldots,Y_{p}$ as parameters, use the parametrized algorithm
for computing contractible covers using the formula $\widetilde{\phi}$ as
input to obtain the finite set $\mathcal{F}\subset\mbox{\rm
D}[Y_{1},\ldots,Y_{p}]$ and the tuples
$\Phi_{C},C\in\mathrm{Cc}(\mathcal{F})$.

9: Now use $(\mathcal{F},(\Phi_{C})_{C\in\mathrm{Cc}(\mathcal{F}}))$ as input
to Algorithm 4(parametrized algorithm for simplicial replacement) to obtain a
finite set $\mathcal{G}\subset\mbox{\rm D}[Y_{1},\ldots,Y_{p}]$ and for each
$C\in\mathrm{Cc}(\mathcal{F}\cup\mathcal{G})$ a simplicial complex
$\Delta_{C}$ with property described earlier. Let
$\mathcal{C}=\mathcal{F}\cup\mathcal{G}$.

10: For each $C,C^{\prime}\in\mathrm{Cc}(\mathcal{C})$, we obtain a semi-
algebraic partition of $C\times C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})$
as follows. Call Algorithm 4(parametrized algorithm for simplicial
replacement) with input
$\mathcal{C}(Y)\cup\mathcal{C}(Y^{\prime}),(\Phi_{C}(X,Y)\mid\Phi_{C^{\prime}}(X,Y^{\prime})))$
with parameters $Y,Y^{\prime}$, and where $\mid$ denotes concatenation. Let
$\mathcal{D}_{C,C^{\prime}}\subset\mbox{\rm D}[Y,Y^{\prime}]$ denote the
finite set of polynomials in the output, and for each
$E\in\mathrm{Cc}(\mathcal{D}_{C,C^{\prime}})$, a simplicial complex
$\Delta_{C,C^{\prime},E}$, and observe that $\Delta_{C},\Delta_{C^{\prime}}$
are both subcomplexes of the simplicial complex
$\Delta^{\prime}_{C,C^{\prime},E}$. Moreover, there is a subcomplex
$\Delta^{0}_{C,C^{\prime},E}$ containing $\Delta_{C}$ as a subcomplex, such
that the inclusion $|\Delta_{C}|\rightarrow|\Delta^{0}_{C,C^{\prime},E}|$ is a
homological $\ell$-equivalence.

11: Denote
$\mathcal{D}=\mathcal{C}(Y)\cup\mathcal{C}(Y^{\prime})\cup\bigcup_{(C,C^{\prime})}\mathcal{D}_{C,C^{\prime}},$
where the last union is taken over all
$(C,C^{\prime})\in\mathrm{Cc}(\mathcal{C})\times\mathrm{Cc}(\mathcal{C}^{\prime})$
such that $C\times C^{\prime}\cap\mathrm{pairs}(\mathrm{R}^{p})\neq\emptyset$.
Note that for each $D\in\mathrm{Cc}(\mathcal{D})$, there exists uniquely
defined
$C_{1}(D)\in\mathrm{Cc}(\mathcal{C}),C_{2}(D)\in\mathrm{Cc}(\mathcal{C})$, and
$E(D)\in\mathrm{Cc}(\mathcal{D}_{C,C^{\prime}})$ such that $D\subset
C_{1}(D))\times C_{2}(D))\cap E(D)$.

12: For each $D\in\mathrm{Cc}(\mathcal{D})$, such that
$D\subset\mathrm{pairs}(\mathrm{R}^{p})$, and for $0\leq i\leq\ell$, let
$\phi_{D,i,0}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)}^{0})\rightarrow\mbox{\rm
H}_{i}(\Delta_{C_{1}(D)}),$ and  $\phi_{D,i,1}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)})\rightarrow\mbox{\rm
H}_{*}(\Delta_{C_{2}(D)}),$ denote the canonical isomorphisms induced by
refinement, and  $\iota_{D,i}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)}^{0})\rightarrow\mbox{\rm
H}_{i}(\Delta_{C_{1}(D),C_{2}(D),E(D)})$ the homomorphism induced by
inclusion.

13: Denote
$\widetilde{\phi}_{D,i}:=\phi_{D,i,1}\circ\iota_{D,i}\circ\phi_{D,i,0}^{-1}:\mbox{\rm
H}_{i}(\Delta_{C_{1}(D))})\rightarrow\mbox{\rm H}_{i}(\Delta_{C_{2}(D)}).$

14: Output bases of the finite dimensional vector spaces  $\mbox{\rm
H}_{i}(\Delta_{C}),C\in\mathrm{Cc}(\mathcal{C}),0\leq i\leq\ell,$ and matrices
with respect to the above bases for the linear maps  $\widetilde{\phi}_{D,i},$
$D\in\mathrm{Cc}(\mathcal{D})$, such that
$D\subset\mathrm{pairs}(\mathrm{R}^{p})$, and $0\leq i\leq\ell$.

15:The complexity of the algorithm is bounded by  $(sd)^{(pn)^{O(\ell)}}.$
Moreover,
$\mathrm{card}(\mathcal{C}),\mathrm{card}(\mathcal{D}),\deg(\mathcal{C}),\deg(\mathcal{D})$
are all bounded by  $(sd)^{(pn)^{O(\ell)}}.$

###### Proof of correctness and complexity analysis of Algorithm 5.

The correctness of the algorithm follows from the correctness of Algorithms 3
and 4, and the same arguments as in the proof correctness of Algorithm 2.

The complexity bound follows from the complexity of Algorithms 3 and 4. ∎

###### Proof of Theorem 4.

Follows from the proof of correctness and complexity analysis of Algorithm 5.
∎

###### Proof of Theorem 1.

Follows immediately from Theorem 4. ∎

###### Proof of Corollary 1.

We first call Algorithm 5 with $\mathcal{P},\mathcal{Q},\Phi,\Psi,\ell$ as
input, and then enumerate the elements of $\mathrm{Cc}(\mathcal{D})$ by
computing a unique point $\mathbf{d}_{D}$(represented by a real univariate
representation) in each $D\in\mathcal{D}$. It then suffices to check for each
pair $(\mathbf{t},\mathbf{t}^{\prime})\in T\times
T\cap\mathrm{pairs}(\mathrm{R}^{p})$, the unique
$D\in\mathrm{Cc}(\mathcal{D})$ such that $(\mathbf{t},\mathbf{t}^{\prime})\in
D$ or equivalently if $(\mathbf{t},\mathbf{t}^{\prime})$ and $\mathbf{d}_{D}$
belong to the same element of $\mathrm{Cc}(\mathcal{D})$. This can be decided
using the uniform roadmap algorithm [8, Algorithm 16.4]. The complexity bound
follows from the complexity of Algorithm 5 and that of the uniform road
algorithm which has singly exponential complexity. ∎

##  4\. Proofs of Theorems 2 and 3

In the proofs of Theorems 2 and 3 we will need the following basic result from
real algebraic geometry giving an upper bound on the sum of the (zero-th)
Betti numbers of the realizations of all realizable sign conditions of a
finite set of polynomials.

######  Theorem 5.

[8, Theorem 7.30] Let $\mathcal{P}\subset\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq
d}$ with $\mathrm{card}(\mathcal{P})=s$. Then,

$\mathrm{card}(\mathrm{Cc}(\mathcal{P}))\leq\sum_{j=1}^{n}\binom{s}{j}4^{j}d(2d-1)^{n-1}.$

###### Proof of Theorem 2.

Using Theorem 1 we have that the poset module $\mathbf{P}_{S,\mathbf{f},\ell}$
is semi-algebraically constructible (recall Definition 1.5). Thus, there exist
$M>0$, and a semi-algebraically constructible function
$F:\mathrm{pairs}(\mathrm{R}^{p})\rightarrow\mathbf{k}^{M\times M}$ associated
to $\mathbf{P}_{S,\mathbf{f},\ell}$. Moreover, since by Theorem 1, the
complexity of $\mathbf{P}_{S,\mathbf{f},\ell}$ is bounded by
$(sd)^{(np)^{O(\ell)}}$, we can assume that there exists a finite set of
polynomials,
$\mathcal{D}\subset\mathrm{R}[Y_{1},\ldots,Y_{p},Y_{1}^{\prime},\ldots,Y_{p}]$,
such that the partition
$(D)_{D\in\mathrm{Cc}(\mathcal{D}),D\subset\mathrm{pairs}(\mathrm{R}^{p})}$ is
subordinate to $F$, with

(4.1)
$C^{\prime}:=\max(\mathrm{card}(\mathcal{D}),\deg(\mathcal{D}))\leq(sd)^{(np)^{O(\ell)}}.$

Now let

$\widetilde{\mathcal{D}}\subset\mathrm{R}[Y_{1,1},\ldots,Y_{1,p},\ldots,Y_{N,1},\ldots,Y_{N,p}]$

be defined as follows.

$\widetilde{\mathcal{D}}:=\bigcup_{1\leq i,j\leq
N}\\{P(Y_{i,1},\ldots,Y_{i,p},Y_{j,1},\ldots,Y_{j,p})\mid P\in\mathcal{D}\\}.$

Then,

$\mathrm{card}(\widetilde{\mathcal{D}})\leq C^{\prime}\cdot N^{2},$
$\deg(\widetilde{\mathcal{D}})\leq C^{\prime},$

and the number of variables in the polynomials in $\widetilde{\mathcal{D}}$ is
$pN$.

It follows from the fact that $F$ is associated to the poset module
$\mathbf{P}_{S,\mathbf{f},\ell}$, and that the partition
$(D)_{D\in\mathrm{Cc}(\mathcal{D})}$ is subordinate to $F$, that for each
$T=(\mathbf{y}_{1},\ldots,\mathbf{y}_{N})\in(\mathrm{R}^{p})^{N}$, the strong
equivalence class of the finite poset module
$\mathbf{P}_{S,\mathbf{f},T,\ell}$ is determined by the map

$\\{(i,j)\mid\mathbf{y}_{i}\preceq\mathbf{y}_{j}\\}\rightarrow\mathrm{Cc}(\mathcal{D}),(i,j)\mapsto
D(\mathbf{y}_{i},\mathbf{y}_{j}),$

where $D(\mathbf{y}_{i},\mathbf{y}_{j})$ is the unique element of
$\mathrm{Cc}(\mathcal{D})$ containing $(\mathbf{y}_{i},\mathbf{y}_{j})$.

Let $\widetilde{D}_{T}\in\mathrm{Cc}(\widetilde{\mathcal{D}})$ such that
$(\mathbf{y}_{1},\ldots,\mathbf{y}_{N})\in\widetilde{D}_{T}$. Denote by
$\pi_{i,j}:(\mathrm{R}^{p})^{N}\rightarrow\mathrm{R}^{p}\times\mathrm{R}^{p}$
the projection map on to the $(i,j)$-th coordinate (tuples).

Then, for each $i,j$ with $\mathbf{y}_{i}\preceq\mathbf{y}_{j}$,
$\pi_{ij}(\widetilde{D}(T))=D(\mathbf{y}_{i},\mathbf{y}_{j})$.

Thus, the strong equivalence class of $\mathbf{P}_{S,\mathbf{f},T,\ell}$ is
determined by $\widetilde{D}_{T}$, and hence the number of possibilities for
the strong equivalence class of $\mathbf{P}_{S,\mathbf{f},T,\ell}$ is bounded
by $\mathrm{card}(\mathrm{Cc}(\widetilde{\mathcal{D}}))$.

Using Theorem 5 and (4.1) we obtain

$\displaystyle\mathrm{card}(\mathrm{Cc}(\widetilde{\mathcal{D}}))$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{pN}\binom{C^{\prime}N^{2}}{j}\cdot 4^{j}\cdot
C^{\prime}(2C^{\prime}-1)^{pN-1}$ $\displaystyle\leq$
$\displaystyle\sum_{j=1}^{pN}\binom{CN^{2}}{j}\cdot C^{pN}$

with $C=8C^{\prime}=(sd)^{(np)^{O(\ell)}}$ (using (4.1)).

In order to get the asymptotic upper bound observe that

$\displaystyle\sum_{j=1}^{pN}\binom{CN^{2}}{j}\cdot C^{pN}$
$\displaystyle\leq$ $\displaystyle(pN)\cdot\binom{CN^{2}}{pN}\cdot C^{pN}$
$\displaystyle\leq$
$\displaystyle(pN)\cdot\left(\frac{eCN^{2}}{pN}\right)^{pN}\cdot C^{pN}$
$\displaystyle\leq$
$\displaystyle(pN)\cdot\left(\frac{eC^{2}}{p}\right)^{pN}\cdot N^{pN}$
$\displaystyle=$ $\displaystyle\left(N^{o(1)pN}\right)\cdot N^{pN}$
$\displaystyle=$ $\displaystyle N^{(1+o(1))pN},$

where in the second step we have used the inequality

$\binom{m}{k}\leq\left(\frac{em}{k}\right)^{k}$

valid for all $m,k$ with $0\leq k\leq m$.

∎

###### Proof of Theorem 3.

For $s,d,n>0$, let

$M(s,d,n):=s\times\binom{n+d}{d},$

denote the number of monomials in $s$ polynomials in $n$ variables of degree
$d$.

Let $(A_{i},A_{i}^{\prime})_{1\leq i\leq
s^{\prime}},(B_{i},B_{i}^{\prime})_{1\leq i\leq s^{\prime\prime}}$ denote
Boolean variables, with $s^{\prime}+s^{\prime\prime}=s$, and let

$\widetilde{\Phi}(A_{1},A_{1}^{\prime}\ldots,A_{s^{\prime}},A_{s^{\prime}}^{\prime}),\widetilde{\Psi}(B_{1},B_{1}^{\prime},\ldots,B_{s^{\prime\prime}},B_{s^{\prime\prime}}^{\prime})$

denote two Boolean formulas.

Notice that there as most $2^{2^{2s}}$ many non-equivalent Boolean formulas in
$2s$ Boolean indeterminates.

Now given,

$\mathcal{P}=(P_{1},\ldots,P_{s^{\prime}})\in(\mathrm{R}[X_{1},\ldots,X_{n}])^{s^{\prime}},$

and

$\mathcal{Q}=(Q_{1},\ldots,Q_{s^{\prime\prime}})\in(\mathrm{R}[Y_{1},\ldots,Y_{p},Y_{1}^{\prime},\ldots,Y_{p}^{\prime}])^{s^{\prime\prime}},$

we will denote by $\widetilde{\Phi}(\mathcal{P})$ (resp.
$\widetilde{\Psi}(\mathcal{Q})$) the formulas obtained by substituting in
$\widetilde{\Phi}$ (resp. $\widetilde{\Psi})$, $A_{i}$ by $P_{i}\geq 0$,
$A_{i}^{\prime}$ by $P_{i}\leq 0$, (resp. $B_{i}$ by $Q_{i}\geq 0$,
$B_{i}^{\prime}$ by $Q_{i}\leq 0$).

For

$\mathcal{P}\in(\mathrm{R}[X_{1},\ldots,X_{n}]_{\leq d})^{s^{\prime}}$

and

$\mathcal{Q}\in(\mathrm{R}[Y_{1},\ldots,Y_{p},X_{1},\ldots,X_{n}]_{\leq