# Computing Generalized Ranks of Persistence Modules via Unfolding to Zigzag
Modules

Tamal K. Dey
<EMAIL_ADDRESS>&Cheng Xin
<EMAIL_ADDRESS>This research is supported by NSF grants CCF 2049010 and
2301360

(Department of Computer Science
Purdue University)

###### Abstract

For a $P$-indexed persistence module $\mathbb{M}$, the (generalized) rank of
$\mathbb{M}$ is defined as the rank of the limit-to-colimit map for the
diagram of vector spaces of $\mathbb{M}$ over the poset $P$. For $2$-parameter
persistence modules, recently a zigzag persistence based algorithm has been
proposed that takes advantage of the fact that generalized rank for
$2$-parameter modules is equal to the number of _full_ intervals in a zigzag
module defined on the boundary of the poset. Analogous definition of boundary
for $d$-parameter persistence modules or general $P$-indexed persistence
modules does not seem plausible. To overcome this difficulty, we first
_unfold_ a given $P$-indexed module $\mathbb{M}$ into a zigzag module
$\mathbb{M}_{ZZ}$ and then check how many full interval modules in a
decomposition of $\mathbb{M}_{ZZ}$ can be _folded back_ to remain _full_ in a
decomposition of $\mathbb{M}$. This number determines the generalized rank of
$\mathbb{M}$. For special cases of degree-$d$ homology for $d$-complexes, we
obtain a more efficient algorithm including a linear time algorithm for
degree-$1$ homology in graphs.

##  1 Introduction

It is well known that one parameter persistence modules decompose into
interval modules that constitute the _persistence diagram_ , or equivalently
the _barcode_ of the given module, a fundamental object of study in
topological data analysis [6, 15, 17, 31]. There are many situations where the
persistence modules are parameterized over more than one parameter [5, 9, 18,
25, 29]. Unfortunately, such _multiparameter persistence modules_ do not
necessarily admit a nice decomposition into intervals only. Instead, they may
decompose into indecomposables that are more complicated [9]. To overcome this
difficulty, inspired by the work of Patel [32], Kim and Mémoli [23] proposed a
decomposition of poset-indexed modules (satisfying some mild condition) into
_signed_ interval modules. In analogy to the one parameter case, the supports
of these signed interval modules with the multiplicity are called the _signed
barcode_ of the given module [3]. The multiplicity of the intervals are given
by the Möbius inversion of a rank invariant function; see [23, 32]. Botnan,
Oppermann, and Oudot [3] recently showed that a unique minimal signed barcode
of a given persistence module in terms of rectangles can be computed
efficiently and raised the question of efficient computation of other types of
signed barcodes.

At the core of computing these signed barcodes for a persistence module
$\mathbb{M}$ sits the problem of computing the generalized rank for an
interval $I$ which is defined as the rank of the limit-to-colimit map for the
diagram of vector spaces of the restricted module $\mathbb{M}|_{I}$; see [23].
Recently, Dey, Kim, Mémoli [14] showed that, for a $2$-parameter persistence
module, this generalized rank is given by the number of _full_ intervals in
the decomposition of a zigzag module $\mathbb{M}_{ZZ}$ that is a submodule of
$\mathbb{M}$. This becomes immediately useful because there are efficient
algorithms known for computing the barcode of a zigzag module [13, 28, 30].
However, this result is limited to $2$-parameter persistence modules because
the zigzag module needs to be defined on the boundary of a “two dimensional”
interval. Beyond $2$-parameter, this boundary does not remain to be a path and
hence poses a challenge in defining an appropriate zigzag module.

In this paper, we address the above problem and present an algorithm to
compute generalized rank efficiently for finite dimensional modules indexed by
finite posets. The approach uses the idea of straightening up the input
persistence module into a module defined over a zigzag path. We call the
process unfolding the module. We compute a decomposition of the resulting
zigzag module into interval modules using a known algorithm. Then, we design
an algorithm that aims to _fold_ the full interval modules (supported on
entire zigzag path) in the decomposition of the zigzag module back to the
original module. The ones which fold successfully to a full interval summand
(supported on the entire poset) in the original module gives us the
generalized rank according to a result of Chamber and Letscher [11].

A viable approach to compute generalized rank would be to compute the limit
and colimit of a given persistence module separately, say with the recent
algorithm in [33], and then compute the rank of the limit-to-colimit map.
Finding an efficient implementation of this approach remains open. Each of the
computations for limit, colimit, and then the rank of the map between them may
incur considerable computational cost in practice. Our approach also has three
distinct computations, unfolding the module, then computing a zigzag
persistence followed by a folding process. Among these the first one is done
by a simple graph traversal, the second one can be done with recent efficient
practical zigzag persistence algorithms [13, 15, 28]. The folding process is
the only costly step for which we provide an efficient algorithm.

One could also argue that a full decomposition algorithm such as the one in
[16] or the well known Meataxe algorithm can be used to compute generalized
rank because they compute all full interval summands. However, the algorithm
in [16] does not work for non-distinctly graded modules and the Meataxe
algorithm has a high time complexity ($O(t^{18})$, $t$ is maximum of poset and
filtration sizes), as pointed out in [16]). Furthermore, these algorithms
expect the input in matrix forms (presentations or linear maps) instead of
filtrations that are common in practice. We alleviate these issues; more
precisely, highlights of our approach are:

  * •

It introduces an unfolding/folding technique for $P$-modules, that is, finite
dimensional persistence modules defined on a finite poset $P$, which may be of
independent interest.

  * •

It provides an algorithm that, given a simplicial $P$-filtration of a
simplicial complex inducing a $P$-module $\mathbb{M}$ by homology functor,
computes the generalized rank ${\sf{rk}}(\mathbb{M})$ in $O(t^{\omega+2})$
time, $\omega<2.373$, where the description size of $P$ and the given
filtration is at most $t$ (see Eq. (5) and Theorem 5.2). The algorithm does
not need to go through an extra step of computing a presentation of
$\mathbb{M}$ from its inducing $P$-filtration. In fact, currently all
published efficient algorithms for computing presentations work for
$2$-parameter modules ($P\subseteq\mathbb{R}^{2},\mathbb{Z}^{2}$) [22, 26] and
not for a general $P$-module indexed by a finite poset $P$.

  * •

It computes full interval summands of $\mathbb{M}$ representing its “global
sections" supported on $P$.

  * •

It gives a more efficient $O(t^{\omega})$ algorithm for the special cases of
degree $d$-homology for $d$-complexes and a linear time algorithm for
degree-$1$ homology in graphs.

All missing proofs and details are given in the Appendix.

##  2 Persistence modules and generalized rank

###  2.1 Persistence modules

We consider finite dimensional persistence modules indexed by connected finite
posets.

######  Definition 2.1.

For a poset $P$, let $\leq_{P}$ denote the partial order defining it. We also
treat $P$ as a category with every $p\in P$ as its object and $\leq_{P}$
inducing the morphisms between them. Two points $p\leq_{P}q$ in $P$ are called
_immediate_ and written $p\rightarrow q$ or $q\leftarrow p$ if and only if
there is no $r\in P$, $r\not\in\\{p,q\\}$, satisfying $p\leq_{P}r\leq_{P}q$.
We also write $p\leftrightarrow q$ to denote that either $p\rightarrow q$ or
$p\leftarrow q$.

######  Definition 2.2.

An _interval_ $I$ of a poset $P$ is a non-empty subset $I\subseteq P$ so that
(i) $I$ is convex with the partial order of $P$, that is, if $p,q\in I$ and
$p\leq_{P}r\leq_{P}q$, then $r\in I$ ; (ii) $I$ is _connected_ , that is, for
any $p,q\in I$, there is a sequence $p=p_{0},p_{2},\cdots,p_{m}=q$ of elements
of $I$ with $p_{i}\leftrightarrow p_{i+1}$ for $i\in\\{0,\cdots,m-1\\}$.
Assuming $P$ is finite and connected, $P$ is also an interval called the _the
full interval_.

######  Definition 2.3.

Given a poset $P$, we define a $P$-module to be a functor
$\mathbb{M}:P\rightarrow\mathbf{vec}_{\mathbb{F}}$ where
$\mathbf{vec}_{\mathbb{F}}$ is the category of finite dimensional vector
spaces over a fixed field $\mathbb{F}$ with the morphisms being the linear
maps among them. For two points $p\leq_{P}q$, we also write
$\mathbb{M}(p\leq_{P}q)$ to denote the morphisms of $\mathbb{M}$.

######  Definition 2.4.

A $P$-module $\mathbb{M}$ is called indecomposable if there is no direct sum
$\mathbb{M}\cong\mathbb{M}_{1}\oplus\mathbb{M}_{2}$ so that both
$\mathbb{M}_{1}$ and $\mathbb{M}_{2}$ are non-zero $P$-modules.

Any (pointwise) finite dimensional $P$-module is a direct sum of
indecomposables with local endomorphism ring [12]; see also [4]. Such a
decomposition is essentially unique up to automorphism according to Azumaya-
Krull-Remak-Schmidt theorem [1]: (Also see [24, Theorem 1.11]).

######  Theorem 2.1.

Every $P$-module has a unique decomposition up to isomorphism
$\mathbb{M}\cong\mathbb{M}_{1}\oplus\cdots\oplus\mathbb{M}_{k}$ where each
$\mathbb{M}_{i}$ is an indecomposable module.

For a decomposable module $\mathbb{M}$, there exist submodules
$\mathbb{M}_{i}$, $i\in[k]$, of $\mathbb{M}$ with inclusions
$j_{i}:\mathbb{M}_{i}\rightarrow\mathbb{M}$ so that
$(j_{i}:\mathbb{M}_{i}\rightarrow\mathbb{M})_{i\in[k]}$ make $\mathbb{M}$ the
direct sum of $\mathbb{M}_{i}$s written as
$\mathbb{M}=\mathbb{M}_{1}\oplus\cdots\oplus\mathbb{M}_{k}$. In light of this,
we replace the isomorphism in Theorem 2.1
$\mathbb{M}\cong\mathbb{M}_{1}\oplus\cdots\oplus\mathbb{M}_{k}$ with equality
$\mathbb{M}=\mathbb{M}_{1}\oplus\cdots\oplus\mathbb{M}_{k}$ where each
$\mathbb{M}_{i}$ is indecomposable and is a _submodule_ of $\mathbb{M}$; see
Figure 1. We call such a decomposition an _internal direct decomposition_ or
simply _direct decomposition_ denoted $\mathcal{D}:=\mathcal{D}(\mathbb{M})$.
Notice that the uniqueness of such a decomposition is up to automorphisms of
$\mathbb{M}$ (and permutations of $\mathbb{M}_{i}$s). This aspect plays an
important role in our algorithm to follow.

For an interval $I$ of $P$, any module
$\mathbb{I}^{I}:P\rightarrow\mathbf{vec}_{\mathbb{F}}$ is an _interval module_
if:

$\mathbb{I}^{I}(p)\cong\begin{cases}\mathbb{F}&\mbox{if}\ p\in I,\\\
0&\mbox{otherwise,}\end{cases}\hskip
42.67912pt\mathbb{I}^{I}(p\leq_{P}q)\cong\begin{cases}\mathrm{id}_{\mathbb{F}}&\mbox{if}\,\,p,q\in
I,\ p\leq_{P}q,\\\ 0&\mbox{otherwise.}\end{cases}$

######  Definition 2.5.

An interval module $\mathbb{I}^{P}$ with support on $P$ is a _full interval
module_(Figure 1).

Figure 1: (left) A $P$-module with a basis for vector spaces at the points of
$P$ (arrows represent the partial order) with internal maps as matrices;
(right) a direct decomposition that contains two full interval modules
(top,middle) and another interval module (bottom) which is not full.

###  2.2 Generalized rank: limit-to-colimit rank

A $P$-module $\mathbb{M}$ with $P$ being finite and connected admits a limit
$\mathsf{lim}\,\mathbb{M}=(L,(\pi_{p}:L\rightarrow\mathbb{M}(p))_{p\in P})$
and a colimit $\mathsf{colim}\,\mathbb{M}=(C,(i_{p}:\mathbb{M}(p)\rightarrow
C)_{p\in P})$; we refer to [14, 23] for these definitions and reproduce them
from [14] in Appendix A for convenience of the reader. These definitions imply
that, for every $p\leq_{P}q$ in $P$,
$\mathbb{M}(p\leq_{P}q)\circ\pi_{p}=\pi_{q}\ \ \mbox{and }\
i_{q}\circ\mathbb{M}(p\leq_{P}q)=i_{p}$, which in turn imply
$i_{p}\circ\pi_{p}=i_{q}\circ\pi_{q}:L\rightarrow C$ for any $p,q\in P$.

######  Definition 2.6 ([23]).

The _canonical limit-to-colimit map
$\psi_{\mathbb{M}}:\mathsf{lim}\,\mathbb{M}\rightarrow\mathsf{colim}\,\mathbb{M}$_
is the linear map $i_{p}\circ\pi_{p}$ for _any_ $p\in P$. The _generalized
rank_ of $\mathbb{M}$ is
${\sf{rk}}(\mathbb{M}):=\mathrm{rank}(\psi_{\mathbb{M}})$.

The following result allows us to compute ${\sf{rk}}(\mathbb{M})$ as the
number of the full interval modules in a direct decomposition of $\mathbb{M}$.

######  Theorem 2.2 ([11, Lemma 3.1]).

The rank ${\sf{rk}}(\mathbb{M})$ is equal to the number of full interval
modules in a direct decomposition of $\mathbb{M}$.

##  3 Idea using zigzag module

The overall idea of our approach is to “straighten up” the given $P$-module
$\mathbb{M}$ into a zigzag module $\mathbb{M}_{ZZ}$ which is a zigzag module
defined over a linear poset $P_{ZZ}$. It is well known that a zigzag module
like $\mathbb{M}_{ZZ}$ decomposes into interval modules and efficient
algorithms for computing them exist. After computing these interval modules,
we attempt to fold back the full interval modules in this decomposition of
$\mathbb{M}_{ZZ}$ to full interval summands of the original module
$\mathbb{M}$. We know that full interval modules that are submodules of
$\mathbb{M}$ unfolds into full interval modules that are submodules of
$\mathbb{M}_{ZZ}$. However, the converse may not hold, that is, not all full
interval submodules $\mathbb{M}_{ZZ}$ fold back to full interval submodules of
$\mathbb{M}$. So, the main challenge becomes to determine which full interval
modules in the computed decomposition of $\mathbb{M}_{ZZ}$ do indeed fold back
(possibly with some modifications) to full interval summands of $\mathbb{M}$.

Figure 2: Unfolding two modules (defined over $\mathbb{Z}_{2}$) on the same
poset into zigzag modules; hollow circles represent zero vectors. (top row)
Decomposition of the zigzag module folds back to two interval modules, one
with support on the entire poset giving rise to a generalized rank equal to
one, and the other with support on $D$. (bottom row) Full interval module in
the decomposition of the zigzag module does not fold back to a full interval
module (attempted folding shows the discrepancy at point $D$), giving rise to
generalized rank equal to zero.

Figure 2 illustrates this idea. The module $\mathbb{M}$ is defined on a four
point poset $P=\\{A,B,C,D\\}$ shown on left. Bases of the vector spaces are
shown in open brackets ‘$()$’ and linear maps in these bases are shown in
matrices. The poset is straightened into a zigzag path $A\rightarrow
D\rightarrow C\leftarrow D\leftarrow B$. One way to look at this straightening
is to view $P$ as a directed graph and to traverse all its vertices and edges
sequentially possibly with repetition. Starting from the vertex $A$ and moving
to an adjacent node disregarding the direction while noting down the visited
node and the directed edge produces the zigzag path. This process of unfolding
a poset into a zigzag path is formalized in section 4.2. The module
$\mathbb{M}$ is unfolded into the zigzag module $\mathbb{M}_{ZZ}$ by copying
the vector spaces and linear maps at vertices and edges respectively into
their unfolded versions. For the module shown on the top, we get three
interval modules (bars) in a decomposition of $\mathbb{M}_{ZZ}$, the full
interval module supported on $[A,B]$ and the other two supported on two copies
of $D$ respectively. Bases of one dimensional vector spaces for the interval
modules are indicated beneath them. When we fold back $P_{ZZ}$ to $P$
(reversing the process of unfolding) sending $\mathbb{M}_{ZZ}$ to
$\mathbb{M}$, the full interval module does fold back to a full interval
module because the vectors $v_{1}+v_{2}$111this is a vector addition, not a
direct sum at two copies of $D$ are the same and hence map to the same vector
in $\mathbb{M}(D)$. The other two single-point interval modules in the
decomposition of $\mathbb{M}_{ZZ}$ also fold back to a submodule generated by
the vector $v_{2}$ at $D$ and zero everywhere else in $\mathbb{M}$.

The case for the module shown in the bottom row of Figure 2 is not the same.
In this case, $\mathbb{M}_{ZZ}$ also decomposes into the same three intervals,
but the corresponding interval modules are not the same. The full interval
module in this case has different vector spaces spanned by $v_{1}$ and $v_{2}$
respectively at the two copies of $D$. Thus, this interval module does not
fold into a full interval submodule in $\mathbb{M}$ as an attempt on right
indicates. We can determine such full interval modules in a decomposition of
the zigzag module by checking if the vectors at the copied vertices are the
same or not. However, even if this check fails, it may be possible to change
the full interval module to have the vectors at the copied vertices to be the
same. Figure 4 in section 4.1 illustrates such an example. Determining such
cases and taking actions accordingly are key aspects of our algorithm.

###  3.1 Zigzag module

######  Definition 3.1.

A poset $P$ is called a _zigzag_ poset iff there is a linear ordering
$p_{0},\ldots,p_{m}$ of the points in $P$, called the _zigzag_ path, so that
for $i\in\\{0,1,\ldots,m-1\\}$, $p_{i}\leftrightarrow p_{i+1}$ are the only
and all immediate pairs in $P$, i.e., zigzag path represents the Hasse diagram
of $P$. We write $[p_{i},p_{j}]$ to denote an interval $I\subseteq P$ with the
zigzag path $p_{i},p_{i+1},\cdots,p_{j}$.

######  Definition 3.2.

A zigzag module $\mathbb{M}_{ZZ}:P_{ZZ}\rightarrow\mathbf{vec}_{\mathbb{F}}$
is a persistence module where the poset $P_{ZZ}$ is a zigzag poset. Assuming
that $p_{0},p_{1},\ldots,p_{m}$ is the zigzag path for $P_{ZZ}$, we write the
zigzag module as:

$\displaystyle\mathbb{M}_{ZZ}:V_{p_{0}}\stackrel{{\scriptstyle\phi_{0}}}{{\longleftrightarrow}}\ldots\stackrel{{\scriptstyle\phi_{i-1}}}{{\longleftrightarrow}}V_{p_{i}}\stackrel{{\scriptstyle\phi_{i}}}{{\longleftrightarrow}}V_{p_{i+1}}\stackrel{{\scriptstyle\phi_{i+1}}}{{\longleftrightarrow}}\ldots\stackrel{{\scriptstyle\phi_{m-1}}}{{\longleftrightarrow}}V_{p_{m}}$
(1)

where $V_{p_{i}}=\mathbb{M}_{ZZ}(p_{i})$ denote the vector spaces and
$\phi_{i}=\mathbb{M}_{ZZ}(p_{i}\leq_{P}p_{i+1})$ or
$\mathbb{M}_{ZZ}(p_{i+1}\leq_{P}p_{i})$, $i\in\\{0,1,\ldots,m-1\\}$, denote
the morphisms (linear maps).

We will be interested in interval submodules $\mathbb{I}^{[b_{i},d_{i}]}$ of
$\mathbb{M}_{ZZ}$. Such an interval module is either full or can be of four
types determined by the types of its end points. The point $b_{i}$ is called
open (closed) if $b_{i}\not=0$ and the arrow between $b_{i-1},b_{i}$ is a
backward arrow ‘$\leftarrow$’ (resp. forward arrow ‘$\rightarrow$’).
Similarly, the point $d_{i}$ is called open (closed) if $d_{i}\not=m$ and the
arrow between $d_{i},d_{i+1}$ is a forward arrow (resp. backward arrow). The
interval module $\mathbb{I}^{[b_{i},d_{i}]}$ is called open-open, open-closed,
closed-open, or closed-closed depending on whether $b_{i}$ and $d_{i}$ are
both open, $b_{i}$ is open and $d_{i}$ closed, $b_{i}$ is closed and $d_{i}$
is open, or both $b_{i}$ and $d_{i}$ are closed respectively.

By Theorem 2.1, a zigzag module
$\mathbb{M}_{ZZ}:P_{ZZ}\rightarrow\mathbf{vec}_{\mathbb{F}}$ over a finite
zigzag poset $P_{ZZ}$ also decomposes uniquely into indecomposables. By quiver
theory [19, 31], these indecomposables are interval modules, that is,
$\mathbb{M}_{ZZ}=\mathbb{I}_{1}\oplus\cdots\oplus\mathbb{I}_{k}$ where each
$\mathbb{I}_{i}:=\mathbb{I}^{I_{i}}$ is an interval module defined over an
interval $I_{i}:=[p_{b_{i}},p_{d_{i}}]$.

The following definition helps defining limit modules that generalize some
special types of interval modules.

######  Definition 3.3 (Limit representative).

Let $\mathbb{M}_{ZZ}:P_{ZZ}\rightarrow\mathbf{vec}_{\mathbb{F}}$ be a zigzag
module where the zigzag path for $P_{ZZ}$ is $p_{0},p_{2},\ldots,p_{m}$ with
$V_{i}=\mathbb{M}_{ZZ}({p_{i}})$ as given in Eq. (1). A sequence of vectors
(possibly zero) $v_{p_{0}},\ldots,v_{p_{m}}$ is called a _limit
representative_ iff for every $i\in\\{0,\ldots,m-1\\}$, $v_{p_{i}}\in
V_{p_{i}}$ and either $\phi_{i}(v_{p_{i}})=v_{p_{i+1}}$ if $p_{i}\rightarrow
p_{i+1}$ or $\phi_{i}(v_{p_{i+1}})=v_{p_{i}}$ if $p_{i}\leftarrow p_{i+1}$.

The reader can observe that limit representatives are elements of
$\mathsf{lim}\,\mathbb{M}_{ZZ}$.

######  Definition 3.4 (Limit module).

A submodule $\mathbb{I}\subseteq\mathbb{M}_{ZZ}$ is called a _limit module_ if
there is a limit representative (or simply called representative)
$v_{p_{0}},\ldots,v_{p_{m}}$ so that for every $i\in\\{0,\ldots,m\\}$,
$v_{p_{i}}$ spans $\mathbb{I}(p_{i})$.

The following observations about limit modules help understand the roles they
play in the rest of the paper.

First, observe that a limit module $\mathbb{I}$, in general, can be either a
full module or a direct sum of one or more non-overlapping open-open interval
modules such as the ones separated by the red arrows in (2) below:

$\displaystyle
0\leftrightarrow\cdots{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{0\leftarrow}}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v_{p_{b_{i}}}\leftrightarrow\cdots\leftrightarrow
v_{p_{d_{i}}}}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\rightarrow
0}\leftrightarrow\cdots\leftrightarrow{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}0\leftarrow}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}v_{p_{b_{j}}}\leftrightarrow\cdots\leftrightarrow
v_{p_{d_{j}}}}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\rightarrow
0}\leftrightarrow\cdots\leftrightarrow 0$ (2)

Second, observe that some of the interval modules in a direct decomposition of
$\mathbb{M}_{ZZ}=\bigoplus_{i}\mathbb{I}_{i}$ may be limit modules.

Third, if $v_{p_{0}},\ldots,v_{p_{m}}$ is a representative of a limit module
$\mathbb{I}$, then $\alpha v_{p_{0}},\ldots,\alpha v_{p_{m}}$ is also a
representative of $\mathbb{I}$ for any scalar $0\neq\alpha\in\mathbb{F}$. In
regard to this fact, we assume the following.

For a limit module $\mathbb{I}\subseteq\mathbb{M}_{ZZ}$, let ${\sf
b}^{\mathbb{I}}:{\sf b}^{\mathbb{I}}_{p_{0}},\ldots,{\sf
b}^{\mathbb{I}}_{p_{m}}$ denote a chosen representative for $\mathbb{I}$ and
for $0\not=\alpha\in\mathbb{F}$, let $\alpha{\sf b}^{\mathbb{I}}$ denote the
representative $\alpha{\sf b}^{\mathbb{I}}_{p_{0}},\ldots,\alpha{\sf
b}^{\mathbb{I}}_{p_{m}}$.

The reader may realize that a chosen representative of a limit module
$\mathbb{I}$ is an element in $\mathsf{lim}\,\mathbb{I}$ representing a global
section of $\mathbb{M}_{ZZ}$. They can be added to produce other sections.
This addition is given by pointwise vector addition which should not be
confused with direct sums.

######  Observation 3.1 (representative sums).

For two limit modules $\mathbb{I}$ and $\mathbb{I}^{\prime}$ and for
$\alpha,\alpha^{\prime}\in\mathbb{F}$, the sequence of vectors $(\alpha{\sf
b}^{\mathbb{I}}_{p_{0}}+\alpha^{\prime}{\sf
b}^{\mathbb{I}^{\prime}}_{p_{0}}),\ldots,(\alpha{\sf
b}^{\mathbb{I}}_{p_{m}}+\alpha^{\prime}{\sf b}^{\mathbb{I}^{\prime}}_{p_{m}})$
is a representative. We denote the representative as the sum $\alpha{\sf
b}^{\mathbb{I}}+\alpha^{\prime}{\sf b}^{\mathbb{I}^{\prime}}$.

The representative $\alpha{\sf b}^{\mathbb{I}}+\alpha^{\prime}{\sf
b}^{\mathbb{I}^{\prime}}$ can be viewed as an element in the space
$\mathsf{lim}\,\mathbb{I}\oplus\mathsf{lim}\,\mathbb{I}^{\prime}$ obtained by
fixing an element ${\sf b}^{\mathbb{I}}$ in $\mathsf{lim}\,\mathbb{I}$ and
${\sf b}^{\mathbb{I}^{\prime}}$ in $\mathsf{lim}\,\mathbb{I}^{\prime}$ and
mapping them to the direct sum by inclusions.

The following proposition says that in a sense any representative of a full
interval submodule of $\mathbb{M}_{ZZ}$ is in the span of the representatives
of the limit modules present in any direct decomposition of $\mathbb{M}_{ZZ}$.

######  Proposition 3.1.

Let $L$ be the set of limit modules in a direct decomposition $\mathcal{D}$ of
$\mathbb{M}_{ZZ}$. For any full interval module
$\mathbb{I}\subseteq\mathbb{M}_{ZZ}$, there exist unique
$\alpha_{i}\in\mathbb{F}$ so that ${\sf
b}^{\mathbb{I}}=\sum_{\mathbb{I}_{i}\in L}\alpha_{i}{\sf b}^{\mathbb{I}_{i}}$
where the sum is defined as in Observation 3.1.

###### Proof.

Let $\mathbb{I}_{1},\ldots,\mathbb{I}_{k}$ be the set of all interval modules
in the direct decomposition $\mathcal{D}$ of the $P_{ZZ}$-module
$\mathbb{M}_{ZZ}$. For any $p\in P_{ZZ}$, since
$\mathbb{M}_{ZZ}(p)=\text{span}({\sf b}^{\mathbb{I}_{1}}_{p},\cdots,{\sf
b}^{\mathbb{I}_{k}}_{p})$, there exist uniquely determined
$\alpha^{p}_{i}\in\mathbb{F}$ so that ${\sf
b}^{\mathbb{I}}_{p}=\sum_{i}\alpha^{p}_{i}{\sf b}^{\mathbb{I}_{i}}_{p}$ where
$\alpha_{i}^{p}$ is taken to be zero if ${\sf b}^{\mathbb{I}_{i}}_{p}=0$. Let
$L_{p}=\\{\mathbb{I}_{i}\,|\,\alpha^{p}_{i}\not=0\\}$ and
$L^{\prime}=\cup_{p}L_{p}$. It is not difficult to show that
$\alpha^{p}_{i}=\alpha^{q}_{i}:=\alpha_{i}$ for any two points $p,q$ in the
support of $\mathbb{I}_{i}$. Then, we can write
$L^{\prime}=\\{\mathbb{I}_{i}\,|\,\alpha_{i}\not=0\\}$. We claim that
$L^{\prime}$ is a subset of limit modules (open-open) in $\mathcal{D}$, that
is, $L^{\prime}\subseteq L$. If not, there is an interval module
$\mathbb{I}^{\prime}\in L^{\prime}$ that is not a limit module, that is,
$\mathbb{I}^{\prime}$ has an end point $p_{j}\not\in\\{p_{0},p_{m}\\}$
satisfying either of the following two cases: (i) the arrow for
$\phi_{p_{j-1}}$ is forward and the cokernel of $\phi_{p_{j-1}}$ restricted to
$\mathbb{I}^{\prime}(p_{j-1})$ is non-zero. It follows that the cokernel of
$\phi_{p_{j-1}}$ restricted to $\mathbb{I}(p_{j-1})$ is also non-zero. This is
impossible as $\mathbb{I}$ is a full interval module and
$p_{j}\not\in\\{p_{0},p_{m}\\}$, (ii) the arrow for $\phi_{p_{j}}$ is
backward: again, we reach an impossibility with a similar argument. So,
$L^{\prime}\subseteq L$ and it follows that ${\sf
b}^{\mathbb{I}}=\sum_{\mathbb{I}_{i}\in L}\alpha_{i}{\sf b}^{\mathbb{I}_{i}}$
where $\alpha_{i}=0$ for $\mathbb{I}_{i}\in L\setminus L^{\prime}$
establishing the claim of the proposition. ∎

##  4 Folding and Unfolding

In this section, we introduce formal definitions of two main constructs called
_folding_ and _unfolding_ and their properties.

######  Definition 4.1.

Let $Q$ be a finite poset. A poset $\mathrm{Fld}_{s}Q$ is a _folded_ poset of
$Q$ if there exists a surjection $s:Q\rightarrow\mathrm{Fld}_{s}Q$, which (i)
preserves order, that is, $p\leq_{Q}q$ only if
$s(p)\leq_{\mathrm{Fld}_{s}Q}s(q)$ for all $p,q\in Q$, and (ii) surjects also
on the Hasse diagram of $\mathrm{Fld}_{s}Q$, that is, for every immediate pair
$u\rightarrow v$ in $\mathrm{Fld}_{s}Q$, there is a pair $p\leq_{Q}q$ where
$s(p)=u$ and $s(q)=v$. We say $s$ is a folding of $Q$ and $Q$ is an _unfolded_
poset of $\mathrm{Fld}_{s}Q$.

A folding $s:Q\rightarrow\mathrm{Fld}_{s}Q$ can be viewed as a functor from
$Q$ to $\mathrm{Fld}_{s}Q$.

######  Definition 4.2.

Let $P=\mathrm{Fld}_{s}Q$ and $\mathbb{M}:P\to\mathbf{vec}_{\mathbb{F}}$ be a
$P$-module and $\mathbb{N}:Q\to\mathbf{vec}_{\mathbb{F}}$ be a $Q$-module. We
say $\mathbb{M}$ is an $s$-folding of $\mathbb{N}$ $(\mathbb{N}$ $s$-folds or
simply folds into $\mathbb{M})$ and $\mathbb{N}$ is an $s$-unfolding of
$\mathbb{M}$ $(\mathbb{M}$ $s$-unfolds or simply unfolds into $\mathbb{N})$ if
$\mathbb{M}\circ s=\mathbb{N}$, or equivalently the following diagram
commutes:

${P}$${Q}$${{\mathbf{vec}_{\mathbb{F}}}}$$\scriptstyle{s}$$\scriptstyle{N}$$\scriptstyle{M}$

We write $\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{N})$ and
$\mathbb{N}=\mathrm{Fld}_{s}^{-1}(\mathbb{M})$.

Writing the commutativity condition explicitly, we see that a module
$P$-module $\mathbb{M}$ is an _$s$ -folding_ of a $Q$-module $\mathbb{N}$ if
there is a folding $s:Q\rightarrow P$ so that

$\mathbb{N}(q)=\mathbb{M}(s(q))\,~{}(equality~{}as~{}sets)~{}\forall q\in
Q\,;\,\mathbb{N}(p\leq_{Q}q)=\mathbb{M}(s(p)\leq_{P}s(q))\,\forall(p\leq_{Q}q).$
(3)

######  Remark 4.1.

Observe that for a given folding $s:Q\to P$, a $P$-module $\mathbb{M}$ always
has an induced $s$-unfolding $\mathbb{M}\circ s$ by pre-composition with $s$.
However, for a given $Q$-module $\mathbb{N}$, an $s$-folding may not exist
because it may happen that $\mathbb{N}(q)\not=\mathbb{N}(q^{\prime})$ where
$s(q^{\prime})=s(q)$, or $\mathbb{N}(q_{1}\rightarrow
q_{2})\not=\mathbb{N}(q_{1}^{\prime}\rightarrow q_{2}^{\prime})$ where
$s(q_{1})=s(q_{1}^{\prime})$ and $s(q_{2})=s(q_{2}^{\prime})$.

An interesting and important fact is that two isomorphic modules may have
different $s$-foldings. Figure 2 shows such an example. Two zigzag modules
shown in the middle are isomorphic (barcode decompositions are the same), but
they are not exactly the same as modules (even though vector spaces are
pointwise equal, morphisms are not). So, even if they are isomorphic, they
fold to different modules as shown in left. Nevertheless, if a folding exists,
a module necessarily folds to a _unique_ module as Proposition B.1 (Appendix
B) states.

######  Definition 4.3.

Let $\mathbb{M}_{1}$ and $\mathbb{M}_{2}$ be two summands so that
$\mathbb{M}=\mathbb{M}_{1}\oplus\mathbb{M}_{2}$. Then, $\mathbb{M}_{2}$ is
called a complement summand of $\mathbb{M}_{1}$ and is denoted as
$\overline{\mathbb{M}_{1}}$. Observe that $\overline{\mathbb{M}_{1}}$ is not
necessarily unique though for a given decomposition, it is uniquely
identified.

######  Definition 4.4.

For a folding $s:Q\rightarrow\mathrm{Fld}_{s}(Q)$ and a $Q$-module
$\mathbb{N}$, we say $\mathbb{N}$ is $s$-_foldable_ $($or simply foldable$)$
if $\mathbb{N}(q)=\mathbb{N}(q^{\prime})$ for every pair $q,q^{\prime}\in Q$
where $s(q)=s(q^{\prime})$.

Foldability of a summand and its complement in a module guarantees that they
remain summands after the folding of the module as the next Theorem states
(Appendix B).

######  Theorem 4.1.

Let $\mathbb{M}$ be a $P$-module and $\mathbb{N}$ be a $Q$-module where
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{N})$ for some folding $s:Q\rightarrow P$.

  1. 1.

If $\mathbb{N}=\mathbb{N}_{1}\oplus\overline{\mathbb{N}_{1}}$ and both
$\mathbb{N}_{1}$ and $\overline{\mathbb{N}_{1}}$ are foldable, then
$\mathrm{Fld}_{s}(\mathbb{N}_{1})$ and
$\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})$ exist and
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{N}_{1})\oplus\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})$.

  2. 2.

Conversely, if $\mathbb{M}=\mathbb{M}_{1}\oplus\overline{\mathbb{M}_{1}}$,
then $\mathrm{Fld}_{s}^{-1}(\mathbb{M}_{1})$ and
$\mathrm{Fld}_{s}^{-1}(\overline{\mathbb{M}_{1}})$ necessarily exist and
$\mathbb{N}=\mathrm{Fld}_{s}^{-1}(\mathbb{M}_{1})\oplus\mathrm{Fld}_{s}^{-1}(\overline{\mathbb{M}_{1}})$.

  3. 3.

If $\mathbb{N}=\mathbb{N}_{1}\oplus\overline{\mathbb{N}_{1}}$ and
$\mathbb{N}_{1}$ is a foldable full interval module where
$\mathrm{Fld}_{s}(\mathbb{N}_{1})$ is a summand of $\mathbb{M}$, then
$\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})$ necessarily exists and is a
summand of $\mathbb{M}$ as well.

In Figure 2 (top-middle), the red interval is foldable and its complement
(direct sum of two blue intervals) is foldable. So, the red interval and its
complement fold into summands whereas in Figure 3, none of the interval
modules folds into a summand because even if the blue one is foldable, its
complement is not.

Figure 3: (left) $\mathbb{M}$, (right) $\mathbb{M}_{ZZ}$: the blue interval
module is foldable whereas its complement (red) is not.

###  4.1 Complete and limit modules

Our aim is to unfold a $P$-module $\mathbb{M}$, $P$ being finite and
connected, to a zigzag module $\mathbb{M}_{ZZ}$ defined over a zigzag poset
$P_{ZZ}$ and then use Theorem 4.1 on a direct decomposition of
$\mathbb{M}_{ZZ}$ to fold back some of its full interval modules. Consider a
direct decomposition $\mathbb{M}_{ZZ}=\bigoplus_{i}\mathbb{I}_{i}$ of
$\mathbb{M}_{ZZ}$ into interval modules. Such a decomposition may not be
unique because different basis (representative) vectors may be used to define
the interval modules over the same (multi)set of intervals. To apply Theorem
4.1(1), the full interval modules in a decomposition of $\mathbb{M}_{ZZ}$ that
we try to fold back should themselves and their complements be foldable. Our
goal is to determine the maximum number of such full interval modules over all
decompositions of $\mathbb{M}_{ZZ}$. The following definition is introduced
keeping this in mind.

######  Definition 4.5.

Let $P=\mathrm{Fld}_{s}P_{ZZ}$ where $P_{ZZ}$ is a zigzag poset (path) and
$\mathbb{M}_{ZZ}:P_{ZZ}\rightarrow\mathbf{vec}_{\mathbb{F}}$ be a zigzag
module. Furthermore, let $\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{M}_{ZZ})$ exist.
An interval module $\mathbb{I}$ in a direct decomposition
$\mathcal{D}:\bigoplus_{i}\mathbb{I}_{i}$ of $\mathbb{M}_{ZZ}$ is called _$s$
-complete_ if and only if (i) $\mathbb{I}$ is a full interval module and (ii)
both $\mathbb{I}$ and its complement $\overline{\mathbb{I}}$ are foldable. Let
$\kappa(\mathcal{D})$ denote the number of $s$-complete interval modules in
the decomposition $\mathcal{D}$. We call $\mathcal{D}$ _$s$ -complete_ if
$\kappa(\mathcal{D})={\sf{rk}}(\mathbb{M})$.

Theorem 4.1 helps us to prove the following Proposition which guarantees that
$\mathbb{M}_{ZZ}$ has an $s$-complete decomposition (Appendix B).
Additionally, it states that no direct decomposition of $\mathbb{M}_{ZZ}$ can
have more $s$-complete intervals than an $s$-complete decomposition.

######  Proposition 4.1.

Let $P=\mathrm{Fld}_{s}P_{ZZ}$ be a folded poset of a finite zigzag poset
$P_{ZZ}$. Let $\mathbb{M}_{ZZ}:P_{ZZ}\rightarrow\mathbf{vec}_{\mathbb{F}}$ be
a zigzag module and assume that the $s$-folding
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{M}_{ZZ})$ exists. Then, an $s$-complete
decomposition of $\mathbb{M}_{ZZ}$ exists. Furthermore, any direct
decomposition $\mathcal{D}$ of $\mathbb{M}_{ZZ}$ has
$\kappa(\mathcal{D})\leq{\sf{rk}}(\mathbb{M})$.

###### Proof.

First, we prove the second conclusion. If a direct decomposition $\mathcal{D}$
of $\mathbb{M}_{ZZ}$ had $\kappa(\mathcal{D})>{\sf{rk}}(\mathbb{M})$, then
$\mathcal{D}$ would have more than ${\sf{rk}}(\mathbb{M})$ $s$-complete
interval modules as its summand each of which would fold to a full interval
summand of $\mathbb{M}$ (Theorem 4.1(1)). This is not possible because in that
case $\mathbb{M}$ would have more than ${\sf{rk}}(\mathbb{M})$ summands that
are full intervals, an impossibility according to Theorem 2.2.

Next, we show the first conclusion. Consider a direct decomposition
$\mathbb{M}=\mathbb{I}_{1}\oplus\cdots\oplus\mathbb{I}_{r}\oplus\mathbb{M}^{\prime}_{1}\oplus\cdots\oplus\mathbb{M}^{\prime}_{k}$
where $\mathbb{I}_{1},\ldots,\mathbb{I}_{r}$ are full interval modules. By
Theorem 2.2, $r={\sf{rk}}(\mathbb{M})$. Then, there is a direct decomposition
$\mathcal{D}:\mathrm{Fld}_{s}^{-1}(\mathbb{I}_{1})\oplus\cdots\oplus\mathrm{Fld}_{s}^{-1}(\mathbb{I}_{r})\oplus\mathrm{Fld}_{s}^{-1}(\mathbb{M}^{\prime}_{1})\oplus\cdots\oplus\mathrm{Fld}_{s}^{-1}(\mathbb{M}^{\prime}_{k})$
of $\mathbb{M}_{ZZ}$ by Theorem 4.1(2). Furthermore, each of
$\mathrm{Fld}_{s}^{-1}(\mathbb{I}_{i})$, $1\leq i\leq r$, is a full module
because each $\mathbb{I}_{i}$ is so. By definition, both
$\mathrm{Fld}_{s}^{-1}(\mathbb{I}_{i})$ and its complement are foldable.
Therefore, each $\mathrm{Fld}_{s}^{-1}(\mathbb{I}_{i})$ is $s$-complete. The
direct decomposition $\mathcal{D}$ is an $s$-complete decomposition of
$\mathbb{M}_{ZZ}$ because it has $r={\sf{rk}}(\mathbb{M})$ $s$-complete
interval modules and it cannot have any more $s$-complete interval modules as
$\kappa(\mathcal{D})\leq{\sf{rk}}(\mathbb{M})$. ∎

Proposition 4.1 suggests the following approach to compute the generalized
rank of a given $P$-module $\mathbb{M}$: first unfold $P$ into a zigzag poset
(path) $P_{ZZ}$ and construct a zigzag module $\mathbb{M}_{ZZ}$ that is an
$s$-unfolding of $\mathbb{M}$. It follows that
$\mathrm{Fld}_{s}(\mathbb{M}_{ZZ})$ exists and
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{M}_{ZZ})$ as required by Proposition 4.1.
Then, after computing a direct decomposition of $\mathbb{M}_{ZZ}$ with a
zigzag persistence algorithm, convert it to an $s$-complete decomposition and
determine how many full interval modules (if any) in this decomposition are
$s$-complete.

Figure 4: The full red interval module in $\mathbb{M}_{ZZ}$ as shown in top-
middle does not fold to a full interval module in $\mathbb{M}$ because the
vectors at $D$ mismatch (top-right), but after adding the blue interval module
(limit module), it is converted to a full interval module as shown in bottom-
middle that folds back to a full interval module (pink) in $\mathbb{M}$
(bottom-right).

Consider the $P$-module $\mathbb{M}$ shown in Figure 4 (left). After unfolding
the module to a zigzag module (middle), suppose we get a decomposition into
interval modules as indicated in the middle-top picture. Just like the example
in Figure 2 (bottom), the full interval module in this decomposition of
$\mathbb{M}_{ZZ}$ does not fold into a full interval submodule of $\mathbb{M}$
because the representative vectors at the two copies of $D$ do not match. In
the example of Figure 2, we could not repair this deficiency. However, now we
can do so using the limit modules. Observe that the open-open interval module
(blue) supported on $D\rightarrow C\leftarrow D$ is a limit module. We can add
its representative to the representative of the full interval module to obtain
a new representative for the full interval module shown in middle-bottom
picture. This new full interval module is complete because it and its
complement are foldable and thus the module folds into a full interval summand
of $\mathbb{M}$ (Theorem 4.1(1)). Observe that any of the other two limit
modules (grey) could also serve the purpose. The algorithm GenRank in section
5 essentially determines whether a full interval module in the current
decomposition of $\mathbb{M}_{ZZ}$ is complete, and if not, whether it can be
_converted_ to one by adding the chosen representatives of a set of limit
modules.

It is instructive to point out that the blue module which is not a full module
can also be made foldable by adding the representative of one of the grey
modules, say the left one, to its representative, which has been done to
obtain the decomposition shown on bottom right in Figure 4. Our algorithm does
not do this because we are interested only on folding full interval modules.

###  4.2 Unfolding to a zigzag path and zigzag module

A finite poset $P$ is represented with a directed (acyclic) graph $G=(P,E(P))$
where (i) every directed edge $(p,q)\in E(P)$ satisfies $p\leq_{P}q$ and (ii)
every immediate pair $p\rightarrow q$ in $P$ must correspond to an edge
$(p,q)\in E(P)$. The size of the poset $|P|$ with such a representation is
measured as the total number of vertices and edges in $G$. Given a directed
graph $G=(P,E(P))$ for a finite poset $P$, we construct a zigzag poset
$P_{ZZ}$ using the concept of Eulerian tour in graphs so that
$G=(P_{ZZ},E(P_{ZZ}))$ represents the zigzag path for $P_{ZZ}$ and
$P=\mathrm{Fld}_{s}P_{ZZ}$ for some folding $s$.

Figure 5: Unfolding $P$ (left) to a zigzag poset $P_{ZZ}$; wrapping a thread
around (right) gives a zigzag path (bottom) in $P_{ZZ}$

Given a connected graph $G=(V,E)$, an Eulerian tour in $G$ is an ordered
sequence of its vertices, possibly with repetitions,
$u_{0},\ldots,u_{i},u_{i+1},\ldots u_{t}=u_{0}$ so that every edge $(p,q)\in
E$ appears exactly once as a consecutive pair $(p=u_{i},u_{i+1}=q)$ of
vertices in the sequence. It is known that if $G$ has even degree at every
vertex, then $G$ necessarily has an Eulerian tour which can be computed in
$O(|V|+|E|)$ time. We consider the undirected version $\overline{G}=(P,E(P))$
of the poset graph $G=(P,E(P))$ and straighten it up using an Eulerian tour,
see Figure 5. However, the graph $\overline{G}$ may not satisfy the vertex
degree requirement. So, we double every edge, that is, put a parallel edge in
the graph for every edge (this is equivalent to wrapping a thread around as
shown in Figure 5). The modified graph $\overline{G}$ then has only even-
degree vertices. We compute an Eulerian tour $T$ in $\overline{G}$ and for
every adjacent pair of vertices $p,q$ in the tour representing an edge $(p,q)$
in $\overline{G}$ we impose the order $p\leq_{T}q$ if and only if the directed
edge $(p,q)\in G$. The poset $(T,\leq_{T})$ is taken as the zigzag poset
$P_{ZZ}$ and the tour (zigzag path) as its representation. Clearly, the number
of edges in the tour (immediate pairs in $P_{ZZ}$) is at most twice the number
of edges in $G$ and the number of vertices in $P_{ZZ}$ is one more than that
number. We have

######  Fact 4.1.

$P=\mathrm{Fld}_{s}P_{ZZ}$ for some folding $s$ where $|P_{ZZ}|\leq 2|P|+1$.

In our algorithm, we assume that $\mathbb{M}$ is implicitly given by a
$P$-filtration: A $P$-filtration $F(K)$ of a simplicial complex $K$ is a
family of subcomplexes $F(K)=\\{K_{p}\subseteq K\\}_{p\in P}$ so that
$K_{p}\subseteq K_{q}$ if $p\leq_{P}q$. We assume that both $K$ and $P$ are
finite. Applying the homology functor $H_{k}(\cdot)$ to the filtration $F(K)$,
one obtains a module $\mathbb{M}:=\mathbb{M}_{F(K)}$ in degree $k$ where
$\mathbb{M}(p)=H_{k}(K_{p})$ and
$\mathbb{M}(p\leq_{P}q):H_{k}(K_{p})\rightarrow H_{k}(K_{q})$ induced by the
inclusion $K_{p}\subseteq K_{q}$.

First, we unfold the poset $P$ into a zigzag poset $P_{ZZ}$ using the method
described before. Let $s$ be the resulting folding given by Fact 4.1. To
unfold $\mathbb{M}:P\rightarrow\mathbf{vec}_{\mathbb{F}}$ into a zigzag module
$\mathbb{M}_{ZZ}:P_{ZZ}\rightarrow\mathbf{vec}_{\mathbb{F}}$, we build a
zigzag filtration $F_{ZZ}=\\{K_{p}\\}_{p\in P_{ZZ}}$ by assigning
$K_{p}:=K_{s(p)}$. To check that $F_{ZZ}$ is indeed a zigzag filtration,
observe that $K_{p}\subseteq K_{q}$ for every $p\leq_{P_{ZZ}}q$ because (i)
$s(p)\leq_{P}s(q)$ by definition of folding $s$ and (ii) $K_{s(p)}\subseteq
K_{s(q)}$ by definition of the filtration $F(K)$. It can be easily verified
that applying the homology functor on $F_{ZZ}$, we get the $s$-unfolding
$\mathbb{M}_{ZZ}:P_{ZZ}\rightarrow\mathbf{vec}_{\mathbb{F}}$ of $\mathbb{M}$.

##  5 Algorithm

The algorithm (GenRank in pseudocode) takes a $P$-fitration $F$ and a degree
$k$ for the homology group. First, it $s$-unfolds $P$ to a zigzag path of
$P_{ZZ}$ and computes the filtration $F_{ZZ}$ (Step 1). Let $\mathbb{M}$ and
$\mathbb{M}_{ZZ}$ be the modules obtained by applying the homology functor in
degree $k$ on $F$ and $F_{ZZ}$ respectively as described above. We need to
compute a _barcode_ from $F_{ZZ}$ that represents a direct decomposition of
$\mathbb{M}_{ZZ}$, i.e., we need a zigzag persistence algorithm that computes
the intervals in the barcode with a _representative_ (step 3). A sequence of
$k$-cycles $z_{b},\ldots,z_{d}$ constitutes a representative of a limit module
$\mathbb{I}:=\mathbb{I}^{[p_{b},p_{d}]}$ if $[z_{i}]$ is chosen as ${\sf
b}^{\mathbb{I}}_{p_{i}}$ for $p_{i}\in[p_{b},p_{d}]$. The zigzag persistence
algorithms in [28] and in [15, Chapter 4] can be adapted to compute these
representatives though with some added cost. Next, the algorithm checks how
many interval modules in the computed decomposition of $\mathbb{M}_{ZZ}$ can
be converted to $s$-complete modules which provides ${\sf{rk}}(\mathbb{M})$
according to the definition of $s$-completeness.

Next proposition tells us that it is sufficient to check only the full
interval modules in a direct decomposition of $\mathbb{M}_{ZZ}$ if they can be
converted to $s$-complete modules.

######  Proposition 5.1.

Let $\mathbb{M}_{ZZ}$ be an $s$-unfolding of $\mathbb{M}$ and
$\mathbb{I}_{1},\ldots,\mathbb{I}_{\ell}$ be the set of limit modules in a
direct decomposition $\mathcal{D}$ of $\mathbb{M}_{ZZ}$. There exist unique
$\alpha_{i}\in\mathbb{F}$, $i\in[\ell]$, so that every $s$-complete interval
module $\mathbb{I}$ in any direct decomposition $\mathcal{D}^{\prime}$ of
$\mathbb{M}_{ZZ}$ satisfies that ${\sf
b}^{\mathbb{I}}=\sum_{i=1}^{\ell}\alpha_{i}{\sf b}^{\mathbb{I}_{i}}$ where for
at least one $i\in[\ell]$, $\mathbb{I}_{i}$ is a full interval module and
$\alpha_{i}\not=0$.

The above proposition suggests that we try to convert every full interval
module $\mathbb{I}$ in a direct decomposition of $\mathbb{M}_{ZZ}$ to a
foldable module first, and then check if the complement module
$\overline{\mathbb{I}}$ given by
$\mathbb{M}_{ZZ}=\mathbb{I}\oplus\overline{\mathbb{I}}$ is foldable.

######  Definition 5.1.

Let $\mathbb{M}_{ZZ}$ be an $s$-unfolding of $\mathbb{M}$. We say a full
interval module $\mathbb{I}$ in a direct decomposition $\mathcal{D}$ of
$\mathbb{M}_{ZZ}$ is _convertible_ in $\mathcal{D}$ if either (i) $\mathbb{I}$
is foldable, or (ii) there exists a set of limit modules
$\\{\mathbb{I}_{i}\\}$ in $\mathcal{D}$ none of which is equal to $\mathbb{I}$
so that $\mathbb{I}^{\prime}$ with representative ${\sf
b}^{\mathbb{I}^{\prime}}:={\sf b}^{\mathbb{I}}+\sum_{i}\alpha_{i}{\sf
b}^{\mathbb{I}_{i}}$, $0\not=\alpha_{i}\in\mathbb{F}$, is foldable.

Following notations help stating our results, which provide the theoretical
support for the algorithm GenRank.

######  Notation 5.1.

Let $\mathbb{M}_{ZZ}$ be an $s$-unfolding of $\mathbb{M}$ and $\mathcal{D}$ be
any of its direct decomposition. Denote by $\tau(\mathcal{D})$ the number of
interval modules $\mathbb{I}$ in $\mathcal{D}$ that are convertible and
$\overline{\mathbb{I}}$ is foldable. Observe that
$\kappa(\mathcal{D})\leq\tau(\mathcal{D})$ by definition.

######  Proposition 5.2.

$\kappa(\mathcal{D})\leq{\sf{rk}}(\mathbb{M})\leq\tau(\mathcal{D})$.

###### Proof.

It follows from Proposition 4.1 that
$\kappa(\mathcal{D})\leq{\sf{rk}}(\mathbb{M})$. So, we only show
${\sf{rk}}(\mathbb{M})\leq\tau(\mathcal{D})$. Observe that if
${\sf{rk}}(\mathbb{M})=0$ there is nothing to prove since $\tau(\mathcal{D})$
is non-negative by definition, so assume ${\sf{rk}}(\mathbb{M})\not=0$.
Consider an $s$-complete decomposition $\mathcal{D}^{*}$ of $\mathbb{M}_{ZZ}$
which exists according to Proposition 4.1. Let
$\mathbb{J}_{1},\ldots,\mathbb{J}_{r}$, $r={\sf{rk}}(\mathbb{M})$, denote the
set of these $s$-complete modules in $\mathcal{D}^{*}$. We show by induction
that there is a set of full modules $\mathbb{I}_{1},\ldots,\mathbb{I}_{r}$ in
the direct decomposition $\mathcal{D}$ of $\mathbb{M}_{ZZ}$ so that
$\mathbb{I}_{i}$ is convertible to $\mathbb{J}_{i}$, $i\in[r]$, and
$\overline{\mathbb{I}_{i}}$ is foldable establishing the claim.

For the base case, consider $\mathbb{J}_{1}$. By Proposition 5.1, there is a
set of limit modules $\mathbb{I}^{\prime}_{i}$ in $\mathcal{D}$ so that there
exist unique $0\not=\alpha_{i}\in\mathbb{F}$ giving ${\sf
b}^{\mathbb{J}_{1}}=\sum_{i}\alpha_{i}{\sf b}^{\mathbb{I}^{\prime}_{i}}$.
Choose any full module among $\mathbb{I}_{i}^{\prime}$s as $\mathbb{I}_{1}$
which is guaranteed to exist by Proposition 5.1. Then, consider the
decomposition $\mathcal{D}_{1}$ that only replaces $\mathbb{I}_{1}$ with
$\mathbb{J}_{1}$ in $\mathcal{D}_{0}=\mathcal{D}$. Observe that,
$\mathbb{M}_{ZZ}=\mathbb{J}_{1}\oplus\overline{\mathbb{I}_{1}}$. Applying
Theorem 4.1(3), we get that $\mathrm{Fld}_{s}(\overline{\mathbb{I}_{1}})$
exists because $\mathrm{Fld}_{s}(\mathbb{J}_{1})$ exists and is a summand of
$\mathbb{M}$ by definition of $s$-completeness and Theorem 4.1(1). We conclude
that $\overline{\mathbb{I}_{1}}$ is foldable.

To complete the induction, assume that, for $1\leq j<r$, we already have that
$\mathbb{I}_{1},\ldots,\mathbb{I}_{j}$ are convertible to
$\mathbb{J}_{1},\ldots,\mathbb{J}_{j}$ and
$\overline{\mathbb{I}_{1}},\ldots,\overline{\mathbb{I}_{j}}$ are foldable.
Also, we have the decompositions $\mathcal{D}_{0},\ldots,\mathcal{D}_{j}$ of
$\mathbb{M}_{ZZ}$ where $\mathcal{D}_{i}$ is obtained inductively from
$\mathcal{D}_{i-1}$ by replacing $\mathbb{I}_{i}$ with $\mathbb{J}_{i}$. By
Proposition 5.1, we have ${\sf b}^{\mathbb{J}_{j+1}}=\sum_{i}\alpha_{i}{\sf
b}^{\mathbb{I}^{\prime}_{i}}$, $\alpha_{i}\in\mathbb{F}$, for some limit
modules in $\mathcal{D}_{j}$. We claim that the collection
$\\{\mathbb{I}^{\prime}_{i}\\}$ includes a full module other than
$\mathbb{J}_{1},\ldots,\mathbb{J}_{j}$. If not, we have ${\sf
b}^{\mathbb{J}_{j+1}}=(\sum_{i}\gamma_{i}{\sf
b}^{\mathbb{J}_{i}})+(\sum_{k}\gamma^{\prime}_{k}{\sf
b}^{\mathbb{I}^{\prime}_{k}})$ for
$\gamma_{i},\gamma^{\prime}_{k}\in\mathbb{F}$ where none of
$\\{\mathbb{I}^{\prime}_{k}\\}$ is full. Then, ${\sf
b}^{\mathbb{J}_{j+1}}+\sum_{i}\gamma_{i}{\sf
b}^{\mathbb{J}_{i}}=\sum_{k}\gamma^{\prime}_{k}{\sf
b}^{\mathbb{I}^{\prime}_{k}}$. The LHS gives a representative of an
$s$-complete module which is a sum of representatives of limit modules(RHS)
none of which is full contradicting Proposition 5.1. Thus, the set
$\\{\mathbb{I}^{\prime}_{i}\\}$ includes a full module other than
$\mathbb{J}_{1},\ldots,\mathbb{J}_{j}$. Let $\mathbb{I}_{j+1}$ in
$\mathcal{D}_{j}$ be any such full module. Observe that $\mathbb{I}_{j+1}$ is
also in $\mathcal{D}$. It follows that $\mathbb{I}_{j+1}$ in $\mathcal{D}$ is
convertible to $\mathbb{J}_{j+1}$. Also, with the same reasoning as in the
base case, one can check that $\overline{\mathbb{I}_{j+1}}$ in $\mathcal{D}$
is foldable. ∎

######  Theorem 5.1.

Let $\mathbb{M}_{ZZ}$ be an $s$-unfolding of $\mathbb{M}$ and $\mathcal{D}$ be
any of its direct decompositions.

  * •

If every convertible full module $\mathbb{I}$ in $\mathcal{D}$ where
$\overline{\mathbb{I}}$ is foldable is $s$-complete, then
$\kappa(\mathcal{D})={\sf{rk}}(\mathbb{M})$ ($\mathcal{D}$ is $s$-complete)
else

  * •

Let $\mathcal{D}^{\prime}$ be the direct decomposition obtained from
$\mathcal{D}$ by replacing a convertible module $\mathbb{I}$ where
$\overline{\mathbb{I}}$ is foldable with the converted module
$($$\mathrm{Convert}(\mathbb{I})$ in step 4 of GenRank$)$, then
$\kappa(\mathcal{D}^{\prime})=\kappa(\mathcal{D})+1$.

###### Proof.

For (i), observe that, $\kappa(\mathcal{D})=\tau(\mathcal{D})$ in this case
implying $\kappa(\mathcal{D})={\sf{rk}}(\mathbb{M})=\tau(\mathcal{D})$ due to
Proposition 5.2.

For (ii), observe that an interval module $\mathbb{J}\neq\mathbb{I}$ in
$\mathcal{D}$ is foldable iff it is foldable in $\mathcal{D}^{\prime}$ because
the only affected module in $\mathcal{D}$ is $\mathbb{I}$. We claim that
$\overline{\mathbb{J}}$ is foldable in $\mathcal{D}$ if and only if it remains
so in $\mathcal{D}^{\prime}$. It follows that, compared to $\mathcal{D}$, the
decomposition $\mathcal{D}^{\prime}$ has exactly one more foldable module,
namely $\mathrm{Convert}(\mathbb{I})$, with its complement being foldable.
Hence $\kappa(\mathcal{D}^{\prime})=\kappa(\mathcal{D})+1$.

To prove the claim, first assume that $\overline{\mathbb{J}}$ is foldable in
$\mathcal{D}$. Then, for any two points $p$ and $p^{\prime}$ in $P_{ZZ}$ with
$s(p)=s(p^{\prime})$,
$\overline{\mathbb{J}}(p)=\overline{\mathbb{J}}(p^{\prime})$ in $\mathcal{D}$.
Since $\overline{\mathbb{J}}(p)=\mathrm{span}({\sf
b}^{\mathbb{I}_{1}}_{p},\ldots,{\sf b}^{\mathbb{I}_{s}}_{p})$ where
$\mathbb{I}_{1},\ldots,\mathbb{I}_{s}$ is the set of interval modules in
$\mathcal{D}$ other than $\mathbb{J}$, we have $\mathrm{span}({\sf
b}^{\mathbb{I}_{1}}_{p},\ldots,{\sf
b}^{\mathbb{I}_{s}}_{p})=\mathrm{span}({\sf
b}^{\mathbb{I}_{1}}_{p^{\prime}},\ldots,{\sf
b}^{\mathbb{I}_{s}}_{p^{\prime}})$. After converting $\mathbb{I}$, these spans
can change only if the vector ${\sf b}^{\mathbb{I}}_{p}$ changes to ${\sf
b}^{\mathbb{I}}_{p}+{\sf b}^{\mathbb{J}}_{p}$ and the vector ${\sf
b}^{\mathbb{I}}_{p^{\prime}}$ changes to ${\sf
b}^{\mathbb{I}}_{p^{\prime}}+{\sf b}^{\mathbb{J}}_{p^{\prime}}$. Since
$\mathbb{J}$ is foldable in $\mathcal{D}$, we have ${\sf
b}^{\mathbb{J}}_{p}={\sf b}^{\mathbb{J}}_{p^{\prime}}$ and thus the new spans
of the basis vectors at $p$ and $p^{\prime}$ remain equal meaning
$\overline{\mathbb{J}}(p)$ and $\overline{\mathbb{J}}(p^{\prime})$ remain
equal in $\mathcal{D}^{\prime}$.

Next, assume that $\overline{\mathbb{J}}$ is not foldable in $\mathcal{D}$.
Then, there exist $p$ and $p^{\prime}$ in $P_{ZZ}$ with $s(p)=s(p^{\prime})$
so that $\overline{\mathbb{J}}(p)\neq\overline{\mathbb{J}}(p^{\prime})$ in
$\mathcal{D}$. Using the same argument as above, we can see that the spaces
$\overline{\mathbb{J}}(p)$ and $\overline{\mathbb{J}}(p^{\prime})$ remain
unequal in $\mathcal{D}^{\prime}$. ∎

The algorithm GenRank draws upon Theorem 5.1. For simplicity, we assume
$\mathbb{F}=\mathbb{Z}_{2}$ to describe the algorithm. It takes every full
interval module $\mathbb{I}$ that is not foldable and checks if it is
convertible and its complement $\overline{\mathbb{I}}$ is foldable. It
continues converting such modules to foldable modules until it cannot find any
to convert. The current direct decomposition $\mathcal{D}$ of
$\mathbb{M}_{ZZ}$ changes with these conversions. At the end of this process,
all convertible modules in the current decomposition whose complements are
foldable become foldable themselves. Their number then coincides with
${\sf{rk}}(\mathbb{M})$. To determine the existence of the limit modules whose
addition makes $\mathbb{I}$ foldable, we take the help of an annotation matrix
$A_{p}$ [15, Chaper 4] for each complex $K_{p}$, $p\in P_{ZZ}$, computed in
step 2. Without further elaborations, we only mention that annotation for a
$k$-cycle $z\in Z_{k}(K_{p})$ (cycle group in degree $k$) is the coordinate of
its class $[z]$ in a chosen basis of $H_{k}(K_{p})$; see [7]. The
representative cycles maintained for every interval module in the
decomposition of $\mathbb{M}_{ZZ}$ at point $p$ form a cycle basis
$[z_{1}],\ldots,[z_{g}]$ of $H_{k}(K_{p})$. We will see later that testing a
full module for foldability amounts to calculating the annotations of the
representative cycles of limit modules for certain points $p\in P_{ZZ}$ and
performing certain matrix reductions with them; see section 5.1.

Algorithm GenRank ($P$-filtration $F$, $k\geq 0$)

  * •

Step 1. Unfold $P$ and $F$ into a zigzag path $P_{ZZ}$ and a zigzag filtration
$F_{ZZ}$ respectively

  * •

Step 2. Compute an annotation matrix $A_{p}$ for every complex $K_{p}$ in
$F_{ZZ}$, $p\in P_{ZZ}$

  * •

Step 3. Compute a barcode for $F_{ZZ}$ with representative $k$-cycles; Let
$\mathcal{I}$ denote the set of full interval modules corresponding to full
bars in the current decomposition $\mathcal{D}$

  * •

Step 4. For every module $\mathbb{I}\in{\mathcal{I}}$ do

    * –

If $\mathbb{I}$ is convertible and $\overline{\mathbb{I}}$ is foldable in
$\mathcal{D}$, update $\mathcal{D}$ with
$\mathbb{I}\leftarrow\mathrm{Convert}(\mathbb{I})$

    * –

mark $\mathbb{I}$ complete

  * •

Output the number of complete interval modules/*may output converted modules*/

Now we focus on the crucial checks in step 4. Let us fix the degree of all
homology groups to be $k\geq 0$, which form the vector spaces of the modules
in our discussion.

###  5.1 Convertibility of $\mathbb{I}$ and computing
$\mathrm{Convert}(\mathbb{I})$

Assume that $\mathbb{I}$ is a full interval module in the current direct
decomposition $\mathcal{D}$ of
$\mathbb{M}_{ZZ}=\bigoplus_{i}\mathbb{I}_{i}=\bigoplus_{i}\mathbb{I}^{[p_{b_{i}},p_{d_{i}}]}$.
For each interval module $\mathbb{I}_{i}=\mathbb{I}^{[p_{b_{i}},p_{d_{i}}]}$
the algorithm computes a sequence of _representative_ $k$-cycles
$\\{z^{i}_{p_{j}}\in Z^{k}(K_{p_{j}})\mid
p_{j}\in\\{p_{b_{i}},p_{b_{i}+1},\ldots,p_{d_{i}}\\}\subseteq P_{ZZ}\\}$. A
representative for a limit module $\mathbb{I}^{[p_{b_{i}},p_{d_{i}}]}$ is
given by the homology classes
$[z^{i}_{p_{b_{i}}}],\ldots,[z^{i}_{p_{d_{i}}}]$. Initially, the
representatives for each limit module is computed by an adaptation of the
zigzag persistence algorithm in [28] or in [15, Chapter 4]. Then, every
conversion of a convertible module $\mathbb{I}$ updates these representatives
as we update $\mathbb{I}$ to $\mathrm{Convert}(\mathbb{I})$.

For any point $p\in P_{ZZ}$, call the set of all points that fold to $s(p)$
its partners and denote it as $\mathrm{prt}(p)$. We check if there are limit
modules whose representatives when added to the representative of $\mathbb{I}$
makes the vectors at each point in $\mathrm{prt}(p)$ the same for every point
$p\in P_{ZZ}$ because that converts $\mathbb{I}$ to a foldable interval
module. The partner sets partition $P_{ZZ}$. We designate an arbitrary point,
say $p$, in each partner set $\mathrm{prt}(p)$ where $|\mathrm{prt}(p)|>1$ as
the _leader_ of $\mathrm{prt}(p)$. Let $L$ denote the set of these leaders.
For every point $p\in L$, we do the following.

Let $\mathbb{I}_{1},\ldots,\mathbb{I}_{\ell}$ denote the set of limit modules
in the current decomposition $\mathcal{D}$ of $\mathbb{M}_{ZZ}$ and WLOG
assume $\mathbb{I}=\mathbb{I}_{1}$. The module $\mathbb{I}$ is convertible iff
for all $p\in L$, there exist $\alpha_{i}\in\\{0,1\\}$ so that ${\sf
b}^{\mathbb{I}_{1}}_{p}+\sum_{i=2}^{\ell}\alpha_{i}{\sf
b}^{\mathbb{I}_{i}}_{p}=({\sf
b}^{\mathbb{I}_{1}}_{p_{j}}+\sum_{i=2}^{\ell}\alpha_{i}{\sf
b}^{\mathbb{I}_{i}}_{p_{j}})$ for every $p_{j}\in\mathrm{prt}(p)$. Said
differently, for all $p\in L$ and for every $p_{j}\in\mathrm{prt}(p)$,

${\sf b}^{\mathbb{I}_{1}}_{p}+{\sf
b}^{\mathbb{I}_{1}}_{p_{j}}=\sum_{i=2}^{\ell}\alpha_{i}({\sf
b}^{\mathbb{I}_{i}}_{p}+{\sf
b}^{\mathbb{I}_{i}}_{p_{j}})=\sum_{i=2}^{\ell}\alpha_{i}v^{i}_{j}.$ (4)

where $v^{i}_{j}:={\sf b}^{\mathbb{I}_{i}}_{p}+{\sf
b}^{\mathbb{I}_{i}}_{p_{j}}$.

Figure 6: Illustration of matrix reduction with linearization to check Eq.
(4); (top) $p$ is representative of
$\mathrm{prt}(p)=\\{p\\}\cup\\{p_{1},\ldots,p_{t}\\}$, each row
$\mathbb{I}_{i}$ is a limit module with annotations of representatives at
points in $\mathrm{prt}(p)$; (bottom left) row $\sf I_{i}$ consists of
annotations of cycles $\\{\hat{z}^{i}_{p_{j}}\\}_{j}$ where
$\hat{z}^{i}_{p_{j}}=z^{i}_{p}+z^{i}_{p_{j}}$; (bottom middle) annotations of
cycles in row $\sf I_{i}$ form matrix $A_{i}^{p}$ in the stacks of matrices;
(bottom right) each matrix $A_{i}^{p}$, $i=2,\ldots,\ell$, linearized into a
vector and combined into a larger matrix $A^{p}$ and $A_{1}^{p}$ into vector
$\sf v_{p}$.

Our goal is to determine coefficients $\alpha_{i}$s if Eq. (4) holds. To do
this, for every $i=1,\ldots,\ell$ and every $p\in L$, consider the matrices
$A_{i}^{p}$ whose columns are annotations of the representative cycles
$\hat{z}_{p_{j}}^{i}$ of $v^{i}_{j}$ for every $p_{j}\in\mathrm{prt}(p)$; see
Figure 6 for an illustration. We can compute the $\mathbb{Z}_{2}$-sum of two
chains $\hat{z}_{p_{j}}^{i}=z_{p_{j}}^{i}+z_{p}^{i}$ and add their annotation
vectors which is well defined because their annotation vectors have the same
dimension $g_{p}=\dim H_{k}(K_{p})$ since all complexes at $p$ and $p_{j}$s
were made equal during unfolding. Notice that, if $t_{p}=|\mathrm{prt}(p)|$,
the matrix $A_{i}^{p}$ has dimensions $g_{p}\times t_{p}$. Then, checking Eq.
(4) boils down to determining $\alpha_{i}$s so that
$A_{1}^{p}=\sum_{i=2}^{\ell}\alpha_{i}A_{i}^{p}$. This can be done by using
the linearization trick presented in [16]. Each of the $g_{p}\times t_{p}$
matrices $A_{i}^{p}$, $i\in\\{2,\ldots,\ell\\}$, is linearized into a vector
$\sf v_{i}$ of length $t_{p}g_{p}$ and concatenated into a matrix of
dimensions $t_{p}g_{p}\times\ell$. Let $A^{p}$ denote this matrix (Figure
6,bottom-right).

Suppose that there are $t=\sum_{p\in L}t_{p}$ points in
$\cup_{p}\mathrm{prt}(p)$ and $g=\max_{p}\\{g_{p}\\}$. We need to check Eq.
(4) simultaneously for all $p\in L$ to determine the $\alpha_{i}$s. To do
this, we concatenate matrices $A^{p}$ for all $p\in L$ each of dimensions
$t_{p}g_{p}\times\ell$ to create a matrix $A$ of dimensions
$(\sum_{p}g_{p}t_{p})\times\ell$. Then, a vector $\sf v$ of dimension
$\sum_{p}g_{p}t_{p}$ is created by concatenating vectors $\sf v_{p}$ of
dimension $t_{p}g_{p}$ obtained by linearizing the matrices $A_{1}^{p}$ for
all $p\in L$. Checking if Eq. (4) holds simultaneously for all $p\in L$ boils
down to checking if $\sf v$ is in the column space of $A$. This is a matrix
rank computation on a matrix of dimensions $(\sum_{p}g_{p}t_{p})\times\ell$
which can be done in
$O(\ell^{\omega-1}\sum_{p}g_{p}t_{p})=O(\ell^{\omega-1}gt)$ time where
$\omega<2.373$ is the matrix multiplication exponent [20].

If Eq. (4) holds, we need to compute
$\alpha=[\alpha_{2},\ldots,\alpha_{\ell}]^{T}$ which can be done by solving
the linear system $A\alpha={\sf v}$. Then, we update $\mathbb{I}$ to
$\mathrm{Convert}(\mathbb{I})$ with the representative ${\sf
b}^{\mathbb{I}}+\sum_{i=2}^{\ell}\alpha_{i}{\sf b}^{\mathbb{I}_{i}}$ to get
the new decomposition $\mathcal{D}$. This takes $O(\ell^{\omega-1}gt)$ time
again.

Notice that $g=O(n)=O(t)$. There are $O(t)$ interval modules in the computed
decomposition of $\mathbb{M}_{ZZ}$ and there are at most $O(n)$ full interval
modules among them. So, we check at most $O(n)$ full interval modules for
convertibility. If there are $\ell=O(t)$ number of limit modules, each
convertibility check takes $O(\ell^{\omega-1}tg)=O(t^{\omega}n)$ time giving a
total of $O(t^{\omega}n^{2})$ time for converting all convertible interval
modules in step 4.

###  5.2 Foldability of $\overline{\mathbb{I}}$

To check foldability of $\overline{\mathbb{I}}$, we have to check if
$\overline{\mathbb{I}}(p)=\overline{\mathbb{I}}(p^{\prime})$ for every point
$p^{\prime}\in\mathrm{prt}(p)$. The vector space $\overline{\mathbb{I}}(p)$
for any point $p\in P_{ZZ}$ is spanned by the basis
$([z_{p}^{1}],\ldots,[z_{p}^{r}])$ where $z_{p}^{i}$, $i\in[r]$, are the
$k$-cycles computed as representative cycles for the interval modules
$\mathbb{I}_{1},\ldots,\mathbb{I}_{r}$ none of which equals $\mathbb{I}$ and
whose support contains $p$, that is, $\mathbb{I}_{i}(p)\not=0$. Let $L$ be the
set of points defined in section 5.1. For every point $p\in L$, we form an
annotation matrix $A_{p}$ whose columns represent the annotation of the basis
elements $[z_{p}^{1}],\ldots,[z_{p}^{r}]$ for $\overline{\mathbb{I}}(p)$.
Then, for every point $p^{\prime}\in\mathrm{prt}(p)$, we consider the column
vectors similarly formed by the basis elements
$[z_{p^{\prime}}^{1}],\ldots,[z_{p^{\prime}}^{r}]$ for
$\overline{\mathbb{I}}(p^{\prime})$ and check if each of the vectors
$[z_{p^{\prime}}^{i}]$ is in the column span of $A_{p}$. If so, we have
$\overline{\mathbb{I}}(p)=\overline{\mathbb{I}}(p^{\prime})$ for every
$p^{\prime}\in\mathrm{prt}(p)$ and otherwise not. For better time complexity,
we augment $A_{p}$ with the column vectors made for
$[z_{p^{\prime}}^{1}],\ldots,[z_{p^{\prime}}^{r}]$. Then, we reduce this
augmented matrix of dimensions $O(g)\times O(gt)$ which takes at most
$O(tg^{\omega})$ time.

Time complexity. Let the graph $G=(P,E(p))$ of the poset $P$ indexing the
input filtration $F$ in GenRank have a total of $m$ vertices and edges. Recall
that $K_{p}$ denote the complex at point $p\in P$. Let
$e_{p,q}=|K_{p}\setminus K_{q}|$ where $(p,q)$ is a directed edge in $G$, that
is, $e_{p,q}$ is the number of simplices that are added in the filtration
going from $p$ to $q$. Let

$e=\sum_{(p,q)\in E(P)}e_{p,q}\mbox{ and }t=\max\\{m,e\\}.$ (5)

The quantity $t$ is an upper bound on the size of the input $P$-filtration and
the size of the poset $P$. Let every complex $K_{p}$ for every point $p\in P$
has at most $n$ simplices. Then, step 1 of GenRank takes at most $O(t)$ time
to unfold the poset to $P_{ZZ}$ with the procedure described in section 4.2.
Producing the zigzag filtration $F_{ZZ}$ takes at most $O(t)$ time. Step 2
takes at most $O(n^{3})$ time to produce the annotation matrix [15] for every
complex $K_{p}$, $p\in P_{ZZ}$, giving a total of $O(tn^{3})$ time. Step 3
takes $O(t^{2}n^{2})$ time to compute the zigzag barcode with representatives
by adapting the algorithm in [28] or in [15, chapter 4].

Step 4 takes a total of $O(t^{\omega}n^{2})$ time as discussed before. The
entire foldability test takes a total time $O(tg^{\omega})=O(tn^{\omega})$.
Accounting for all terms, we get:

######  Theorem 5.2.

Let $F$ be an input $P$-filtration of a complex with $n$ simplices where $F$
and $P$ have size at most $t$. The algorithm GenRank computes
${\sf{rk}}(\mathbb{M})$ in $O(tn^{3}+t^{\omega}n^{2})$ time where $\mathbb{M}$
is the $P$-module induced by $F$. With $n=O(t)$, the bound becomes
$O(t^{\omega+2})$.

###### Proof.

The correctness of GenRank follows from Theorem 5.1 because step 4 effectively
either increases the count $\kappa(\mathcal{D})$ or determines that
$\kappa(\mathcal{D})$ cannot be increased in which case $\mathcal{D}$ is
$s$-complete. The time complexity claim follows from our analysis. ∎

##  6 Special case of degree-$d$ homology for $d$-complexes

In this section, we show that when a $P$-module $\mathbb{M}$ is induced by
applying the homology functor in degree $d\geq 0$ on a $P$-filtration of a
$d$-dimensional simplicial complex, we have a much more efficient algorithm
for computing ${\sf{rk}}(\mathbb{M})$. The key observation is that, in this
case, the representatives for the interval modules in a direct decomposition
of $\mathbb{M}_{ZZ}$ takes a special form. In particular, the following
Proposition holds leading to Theorem 6.1.

######  Proposition 6.1.

Let $\mathbb{M}$ be a $P$-module where $\mathbb{M}(p)=H_{d}(K_{p})$ with
$K_{p}$ being a simplicial $d$-complex. For an interval module
$\mathbb{I}^{[p_{b},p_{d}]}$ in a direct decomposition of $\mathbb{M}_{ZZ}$
and for any two points $p_{i},p_{j}\in[p_{b},p_{d}]$, the representative
$d$-cycles $z_{p_{i}}$ and $z_{p_{j}}$ are the same.

###### Proof.

First assume that $p_{i}$ and $p_{j}$ are immediate points in $P_{ZZ}$ and
without loss of generality let $p_{i}\rightarrow p_{j}$. According to the
definition of representatives, we must have the homology classes $[z_{p_{i}}]$
and $[z_{p_{j}}]$ homologous in $K_{p_{j}}$. Since $K_{p_{j}}$ is a
$d$-complex, $[z_{p_{i}}]=[z_{p_{j}}]$ only if $z_{p_{i}}=z_{p_{j}}$ as
chains. It follows by transitivity that this is true even if $p_{i}$ and
$p_{j}$ are not immediate. ∎

It follows from the above proposition that a full interval module in a direct
decomposition of $\mathbb{M}_{ZZ}$ is foldable. Next proposition says that
even the complement $\overline{\mathbb{I}}$ is foldable. Then, applying
Theorem 4.1(1), we can claim that ${\sf{rk}}(\mathbb{M})$ is equal to the
number of full interval modules in $\mathbb{M}_{ZZ}$.

######  Proposition 6.2.

Let $\mathbb{I}$ be any full interval module in a direct decomposition of
$\mathbb{M}_{ZZ}$ where $\mathbb{M}_{ZZ}$ is constructed as in Proposition
6.1. Then, both $\mathbb{I}$ and $\overline{\mathbb{I}}$ are foldable.

###### Proof.

$\mathbb{I}$ is foldable due to Proposition 6.1. Let $p,p^{\prime}\in P_{ZZ}$
be any two points with $s(p)=s(p^{\prime})$. We need to show that
$\overline{\mathbb{I}}(p)=\overline{\mathbb{I}}(p^{\prime})$.

For the full module $\mathbb{I}$, there is a single $d$-cycle that forms a
fixed representative at each point in $P_{ZZ}$ (Proposition 6.1). Let $z$ be
such a $d$-cycle and $\sigma$ be any $d$-simplex in $z$. Delete $\sigma$ from
the complex $K_{p}$ for every $p\in P_{ZZ}$. Let $\mathbb{M}_{ZZ}^{-}$ denote
the $P_{ZZ}$-module induced by the homology functor in degree $d$ on the
zigzag filtration $F_{ZZ}^{-}$ obtained from the original filtration $F_{ZZ}$
by deleting the simplex $\sigma$ everywhere. It is easy to verify that
$\mathbb{M}_{ZZ}^{-}$ is $s$-foldable because
$K_{p}\setminus\sigma=K_{p^{\prime}}\setminus\sigma$ for every
$p,p^{\prime}\in P_{ZZ}$ with $s(p)=s(p^{\prime})$. A direct decomposition of
$\mathbb{M}_{ZZ}$ is obtained from a direct decomposition of
$\mathbb{M}_{ZZ}^{-}$ by adding a full bar with the representative $z$.
Therefore, $\overline{\mathbb{I}}$ is equal to $\mathbb{M}_{ZZ}^{-}$ and thus
foldable. ∎

######  Theorem 6.1.

Let $\mathbb{M}$ be a module constructed as in Proposition 6.1 from a
$P$-filtration $F$ of a $d$-complex where $P$ and $F$ have size at most $t$.
Then, ${\sf{rk}}(\mathbb{M})$ is the number of full interval modules in any
direct decomposition of $\mathbb{M}_{ZZ}$ which can be computed in
$O(t^{\omega})$ time.

###### Proof.

By Proposition 6.2, $\kappa(\mathcal{D})=\tau(\mathcal{D})$ for any direct
decomposition $\mathcal{D}$ of $\mathbb{M}_{ZZ}$. Then, it follows from
Proposition 5.2 that ${\sf{rk}}(\mathbb{M})=\kappa(\mathcal{D})$, which is
exactly equal to the number of full interval modules in any direct
decomposition of $\mathbb{M}_{ZZ}$. Therefore, ${\sf{rk}}(\mathbb{M})$ can be
simply obtained by computing the zigzag barcode of $\mathbb{M}_{ZZ}$ (no need
of computing the representatives). This can be done in $O(t^{\omega})$ time
with the fast zigzag algorithm [13]. ∎

If $\mathbb{M}$ is induced by a $P$-filtration of a graph, then
${\sf{rk}}(\mathbb{M})$ can be computed even faster. Observe that every
$1$-cycle that represents a full bar must continue to be present from the
initial graph $G_{p_{0}}$ at $p_{0}\in P$ to the final graph $G_{p_{m}}$ at
$p_{m}\in P$. This suggests the following algorithm. Take $G_{p_{m}}$; delete
all edges and vertices that are deleted as one moves along $P_{ZZ}$ from
$p_{0}$ to $p_{m}$, but do not insert any of the added edges and vertices. In
the final graph $G_{p_{m}}^{\prime}$ thus obtained (which may be different
from $G_{p_{m}}$ because we ignore the inserted edges and vertices along
$P_{ZZ}$), we compute the number of independent $1$-cycles. This number can be
computed by a depth first search in $G_{p_{m}}^{\prime}$ in linear time. Then,
as an immediate corollary we have Theorem 6.2.

######  Theorem 6.2.

If $\mathbb{M}$ is induced by degree-$1$ homology of a $P$-filtration $F$ of a
graph with a total of $n$ vertices and edges, then ${\sf{rk}}(\mathbb{M})$ can
be computed in $O(n+t)$ time where $P$ and $F$ have size at most $t$.

##  7 Conclusions

Analyzing a mutliparameter persistence module with the help of one parameter
persistence modules is not new. It has been introduced in the context of
computing matching distances [2, 10, 21] for $2$-parameter modules. The
unfolding/folding technique proposed here offers a different slicing
technique. By producing one zigzag path instead of multiple slices, the
unfolding preserves the structural maps of the original module $\mathbb{M}$ in
a lossless manner. We showed how to use them for reconstructing full interval
modules and hence for computing the generalized rank. It will be interesting
to see what other invariants one can reconstruct using the folding/unfolding
of persistenec modules. A natural candidate would be to compute the limit and
colimit of the original module from its zigzag straightening. Recent advances
in zigzag persistence computations [13, 28, 30] can then be taken advantage of
for computing limits and colimits.

## References

  * [1] Gorô Azumaya.  Corrections and supplementaries to my paper concerning Krull-Remak-Schmidt’s theorem.  Nagoya Mathematical Journal, 1:117–124, 1950.
  * [2] Håvard Bakke Bjerkevik and Michael Lesnick.  $\ell$${}^{\mbox{p}}$-distances on multiparameter persistence modules.  CoRR, abs/2106.13589, 2021.  URL: https://arxiv.org/abs/2106.13589, arXiv:2106.13589.
  * [3] Magnus Botnan, Steffen Oppermann, and Steve Oudot.  Signed barcodes for multi-parameter persistence via rank decompositions and rank-exact resolutions.  arXiv preprint arXiv:2107.06800, 2021.
  * [4] Magnus Bakke Botnan and William Crawley-Boevey.  Decomposition of persistence modules.  Proc. American Mathematical Society (AMS), 148(5):4581–4596, 2020\.
  * [5] Magnus Bakke Botnan and Michael Lesnick.  An introduction to multiparameter persistence, 2023.  arXiv:2203.14289.
  * [6] Peter Bubenik and Jonathan A. Scott.  Categorification of persistent homology.  Discret. Comput. Geom., 51(3):600–627, 2014.
  * [7] Oleksiy Busaryev, Sergio Cabello, Chao Chen, Tamal K. Dey, and Yusu Wang.  Annotating simplices with a homology basis and its applications.  In Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, volume 7357 of Lecture Notes in Computer Science, pages 189–200. Springer, 2012.
  * [8] Gunnar Carlsson, Vin de Silva, and Dmitriy Morozov.  Zigzag persistent homology and real-valued functions.  In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 247–256, 2009.
  * [9] Gunnar Carlsson and Afra Zomorodian.  The theory of multidimensional persistence.  Discrete & Computational Geometry, 42(1):71–93, 2009.
  * [10] A. Cerri, B. Di Fabio, M. Ferri, P. Frosini, and C. Landi.  Betti numbers in multidimensional persistent homology are stable functions.  Mathematical Methods in the Applied Sciences, 36(12):1543–1557, 2013.
  * [11] Erin Chambers and David Letscher.  Persistent homology over directed acyclic graphs.  In Research in Computational Topology, pages 11–32. Springer, 2018\.
  * [12] William Crawley-Boevey.  Locally finitely presented additive categories.  Communications in Algebra, 22(5):1641–1674, 1994.  arXiv:https://doi.org/10.1080/00927879408824927, doi:10.1080/00927879408824927.
  * [13] Tamal K. Dey and Tao Hou.  Fast computation of zigzag persistence.  In 30th European Symposium on Algorithms (ESA 2022), 2022.
  * [14] Tamal K. Dey, Woojin Kim, and Facundo Mémoli.  Computing generalized rank invariant for 2-parameter persistence modules via zigzag persistence and its applications.  In 38th International Symposium on Computational Geometry, SoCG 2022, volume 224 of LIPIcs, pages 34:1–34:17, 2022.
  * [15] Tamal K. Dey and Yusu Wang.  Computational Topology for Data Analysis.  Cambridge University Press, 2022.
  * [16] Tamal K Dey and Cheng Xin.  Generalized persistence algorithm for decomposing multiparameter persistence modules.  Journal of Applied and Computational Topology, pages 1–52, 2022\.
  * [17] Herbert Edelsbrunner and John Harer.  Computational Topology: An Introduction.  American Mathematical Society, Jan 2010.
  * [18] Emerson G Escolar and Yasuaki Hiraoka.  Persistence modules on commutative ladders of finite type.  Discrete & Computational Geometry, 55(1):100–157, 2016.
  * [19] Peter Gabriel.  Unzerlegbare Darstellungen I.  Manuscripta Mathematica, 6(1):71–103, 1972.  doi:10.1007/BF01298413.
  * [20] Claude-Pierre Jeannerod, Clément Pernet, and Arne Storjohann.  Rank-profile revealing gaussian elimination and the CUP matrix decomposition.  J. Symb. Comput., 56:46–68, 2013.  URL: https://doi.org/10.1016/j.jsc.2013.04.004.
  * [21] Michael Kerber, Michael Lesnick, and Steve Oudot.  Exact computation of the matching distance on 2-parameter persistence modules.  J. Comput. Geom., 11(2):4–25, 2020.
  * [22] Michael Kerber and Alexander Rolle.  Fast minimal presentations of bi-graded persistence modules.  In Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2021, Virtual Conference, January 10-11, 2021, pages 207–220. SIAM, 2021.
  * [23] Woojin Kim and Facundo Mémoli.  Generalized persistence diagrams for persistence modules over posets.  Journal of Applied and Computational Topology, 5(4):533–581, 2021\.
  * [24] Alexander Kirillov Jr.  Quiver representations and quiver varieties, volume 174 of Graduate Studies.  American Mathematical Society, 2016.
  * [25] Michael Lesnick.  The theory of the interleaving distance on multidimensional persistence modules.  Foundations of Computational Mathematics, 15(3):613–650, 2015.
  * [26] Michael Lesnick and Matthew Wright.  Computing minimal presentations and bigraded betti numbers of 2-parameter persistent homology.  SIAM J. Appl. Algebra Geom., 6(2):267–298, 2022.
  * [27] Saunders Mac Lane.  Categories for the working mathematician, volume 5.  Springer Science & Business Media, 2013.
  * [28] Clément Maria and Steve Y Oudot.  Zigzag persistence via reflections and transpositions.  In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 181–199. SIAM, 2014.
  * [29] Ezra Miller.  Modules over posets: commutative and homological algebra.  arXiv preprint arXiv:1908.09750, 2019.
  * [30] Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba.  Zigzag persistent homology in matrix multiplication time.  In Proceedings of the twenty-seventh Annual Symposium on Computational Geometry, pages 216–225, 2011.
  * [31] Steve Oudot.  Persistence Theory: From Quiver Representations to Data Analysis, volume 209.  AMS Mathematical Surveys and Monographs, 2015.
  * [32] Amit Patel.  Generalized persistence diagrams.  Journal of Applied and Computational Topology, 1(3):397–419, 2018\.
  * [33] Anna Seigal, Heather A. Harrington, and Vidit Nanda.  Principal components along quiver representations.  Found. Comput. Math., 23(4):1129–1165, 2023.

##  Appendix A Limits and colimits

We recall the notions of limit and colimit from category theory [27]. Although
it is known that limit and colimit may not exist for all functors, they do
exist for functors defined on finite posets, which is the case we consider.
The following definitions are reproduced from [14]. Let ${\mathcal{C}}$ denote
a category in the following definitions.

######  Definition A.1 (Cone).

Let $F:P\rightarrow{\mathcal{C}}$ be a functor. A _cone_ over $F$ is a pair
$\left(L,(\pi_{p})_{p\in P}\right)$ consisting of an object $L$ in
${\mathcal{C}}$ and a collection $(\pi_{p})_{p\in P}$ of morphisms
$\pi_{p}:L\rightarrow F(p)$ that commute with the arrows in the diagram of
$F$, i.e. if $p\leq q$ in $P$, then $\pi_{q}=F(p\leq q)\circ\pi_{p}$ in
${\mathcal{C}}$, i.e. the diagram below commutes.

${F(p)}$${F(q)}$${L}$$\scriptstyle{F(p\leq
q)}$$\scriptstyle{\pi_{p}}$$\scriptstyle{\pi_{q}}$ (6)

In Definition A.1, the cone $\left(L,(\pi_{p})_{p\in P}\right)$ over $F$ is
sometimes denoted simply by $L$, suppressing the collection $(\pi_{p})_{p\in
P}$ of morphisms if no confusion can arise. A limit of
$F:P\rightarrow{\mathcal{C}}$ is a terminal object in the collection of all
cones over $F$:

######  Definition A.2 (Limit).

Let $F:P\rightarrow{\mathcal{C}}$ be a functor. A _limit_ of $F$ is a cone
over $F$, denoted by $\left(\mathsf{lim}\,F,\ (\pi_{p})_{p\in P}\right)$ or
simply $\mathsf{lim}\,F$, with the following (universal) _terminal_ property:
For any cone $\left(L^{\prime},(\pi^{\prime}_{p})_{p\in P}\right)$ of $F$,
there is a _unique_ morphism $u:L^{\prime}\rightarrow\mathsf{lim}\,F$ such
that $\pi_{p}^{\prime}=\pi_{p}\circ u$ for all $p\in P$.

Cocones and colimits are defined in a dual manner:

######  Definition A.3 (Cocone).

Let $F:P\rightarrow{\mathcal{C}}$ be a functor. A _cocone_ over $F$ is a pair
$\left(C,(i_{p})_{p\in P}\right)$ consisting of an object $C$ in
${\mathcal{C}}$ and a collection $(i_{p})_{p\in P}$ of morphisms
$i_{p}:F(p)\rightarrow C$ that commute with the arrows in the diagram of $F$,
i.e. if $p\leq q$ in $P$, then $i_{p}=i_{q}\circ F(p\leq q)$ in
${\mathcal{C}}$, i.e. the diagram below commutes.

${C}$${F(p)}$${F(q)}$$\scriptstyle{i_{p}}$$\scriptstyle{F(p\leq
q)}$$\scriptstyle{i_{q}}$ (7)

In Definition A.3, a cocone $\left(C,(i_{p})_{p\in P}\right)$ over $F$ is
sometimes denoted simply by $C$, suppressing the collection $(i_{p})_{p\in P}$
of morphisms. A colimit of $F:P\rightarrow{\mathcal{C}}$ is an initial object
in the collection of cocones over $F$:

######  Definition A.4 (Colimit).

Let $F:P\rightarrow{\mathcal{C}}$ be a functor. A _colimit_ of $F$ is a
cocone, denoted by $\left(\mathsf{colim}\,F,\ (i_{p})_{p\in P}\right)$ or
simply $\mathsf{colim}\,F$, with the following _initial_ property: If there is
another cocone $\left(C^{\prime},(i^{\prime}_{p})_{p\in P}\right)$ of $F$,
then there is a _unique_ morphism $u:\mathsf{colim}\,F\rightarrow C^{\prime}$
such that $i^{\prime}_{p}=u\circ i_{p}$ for all $p\in P$.

The following proposition gives a standard way of constructing a limit of a
$P$-module $\mathbb{M}$. See for example [14, 23]).

######  Notation A.1.

Let $p,q\in P$ and let $v_{p}\in\mathbb{M}(p)$ and $v_{q}\in\mathbb{M}(q)$. We
write $v_{p}\sim v_{q}$ if $p$ and $q$ are comparable, and either $v_{p}$ is
mapped to $v_{q}$ via $\mathbb{M}(p\leq_{P}q)$ or $v_{q}$ is mapped to $v_{p}$
via $\mathbb{M}(q\leq_{P}p)$.

######  Proposition A.1.

  1. (i)

The limit of $\mathbb{M}$ is (isomorphic to) the pair $\left(W,(\pi_{p})_{p\in
P}\right)$ described as follows:

$W:=\left\\{(v_{p})_{p\in P}\in\bigoplus_{p\in P}\mathbb{M}(p):\ \forall p\leq
q\mbox{ in }P,\ v_{p}\sim v_{q}\right\\}$ (8)

and for each $p\in P$, the map $\pi_{p}:W\rightarrow\mathbb{M}(p)$ is the
canonical projection. An element of $W$ is called a _global section_ of
$\mathbb{M}$.

  2. (ii)

The colimit of $\mathbb{M}$ is (isomorphic to) the pair $\left(U,(i_{p})_{p\in
P}\right)$ described as follows: For $p\in P$, let the map
$j_{p}:\mathbb{M}(p)\hookrightarrow\bigoplus_{p\in P}\mathbb{M}(p)$ be the
canonical injection. $U$ is the quotient $\left(\bigoplus_{p\in
P}\mathbb{M}(p)\right)/T$, where $T$ is the subspace of $\bigoplus_{p\in
P}\mathbb{M}(p)$ which is generated by the vectors of the form
$j_{p}(v_{p})-j_{q}(v_{q}),\ v_{p}\sim v_{q},$ the map
$i_{p}:\mathbb{M}(p)\rightarrow U$ is the composition $\rho\circ j_{p}$, where
$\rho$ be the quotient map $\bigoplus_{p\in P}\mathbb{M}(p)\rightarrow U$.

##  Appendix B Missing proofs in section 4

######  Proposition B.1.

For a $Q$-module $\mathbb{N}$ and a folding $s:Q\to P$, if
$\mathrm{Fld}_{s}(\mathbb{N})$ exists, then $\mathrm{Fld}_{s}(\mathbb{N})$ is
unique.

###### Proof.

If there were two modules $\mathbb{M}_{1}$ and $\mathbb{M}_{2}$ that are
$s$-foldings of $N$, then both
$\mathbb{M}_{1}(p)=\mathbb{M}_{2}(p)=\mathbb{N}(s^{-1}(p))$ for every $p\in
P$. Furthermore,
$\mathbb{M}_{1}(p\leq_{P}p^{\prime})=\mathbb{M}_{2}(p\leq_{P}p^{\prime})=\mathbb{N}(s^{-1}(p)\leq_{Q}s^{-1}(p^{\prime}))$
$\forall(p\leq_{P}p^{\prime})$ by definition. This immediately shows that
$\mathbb{M}_{1}=\mathbb{M}_{2}$. ∎

Proposition B.2, Proposition B.3, and Proposition B.4 below are used to prove
Theorem 4.1 that characterizes modules which fold into summand modules.

######  Proposition B.2 ([8]).

Let $\mathbb{N}$ be a submodule of a $P$-module $\mathbb{M}$ where there is a
submodule $\overline{\mathbb{N}}$ of $\mathbb{M}$ so that
$\mathbb{M}(p)=\mathbb{N}(p)\oplus\overline{\mathbb{N}}(p)$ for every $p\in
P$. Then, $\mathbb{N}$ is a summand of $\mathbb{M}$, that is,
$\mathbb{M}=\mathbb{N}\oplus\overline{\mathbb{N}}$.

######  Proposition B.3.

Let $\mathbb{N}$ be a $Q$-module where $\mathrm{Fld}_{s}(\mathbb{N})$ exists
for some folding $s:Q\rightarrow P$. Then, for any submodule
$\mathbb{N}^{\prime}\subseteq\mathbb{N}$ that is foldable
$\mathrm{Fld}_{s}(\mathbb{N}^{\prime})$ exists.

###### Proof.

Construct a $P$-module $\mathbb{M}$ as follows: First, put
$\mathbb{M}(p)=\mathbb{N}^{\prime}(q)$ where $p=s(q)$. This is well defined
because $\mathbb{N}^{\prime}$ is foldable. Next, put
$\mathbb{M}(p\leq_{P}p^{\prime})=\mathbb{N}^{\prime}(q\leq_{Q}q^{\prime})$
where $p=s(q)$ and $p^{\prime}=s(q^{\prime})$. This is also well defined
because for every pair $q\leq_{Q}q^{\prime}$ so that $p=s(q)$ and
$p^{\prime}=s(q^{\prime})$, we have $\mathbb{N}^{\prime}(q\leq_{Q}q^{\prime})$
to be a restriction of $\mathbb{N}(q\leq_{Q}q^{\prime})$ where
$\mathrm{Fld}_{s}(\mathbb{N})$ exists. Observe that
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{N}^{\prime})$ by Definition 4.2. ∎

######  Proposition B.4.

Let $\mathbb{M}$ be a $P$-module and $\mathbb{N}$ be a $Q$-module where
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{N})$ for some folding $s:Q\rightarrow P$.
For any submodule $\mathbb{N}^{\prime}\subseteq\mathbb{N}$, if
$\mathrm{Fld}_{s}(\mathbb{N}^{\prime})$ exists, then it is a submodule of
$\mathbb{M}$. Conversely, if $\mathbb{M}^{\prime}$ is a submodule of
$\mathbb{M}$, then $\mathrm{Fld}_{s}^{-1}(\mathbb{M}^{\prime})$ is a submodule
of $\mathbb{N}$.

###### Proof.

We have $\mathbb{N}^{\prime}(q)\subseteq\mathbb{N}(q)$ for $\forall q\in Q$
and $\mathbb{N}^{\prime}(p\leq_{Q}q)$ is a restriction of
$\mathbb{N}(p\leq_{Q}q)$ on $\mathbb{N}^{\prime}(p)$ $\forall p\leq_{Q}q$
because $\mathbb{N}^{\prime}$ is a submodule of $\mathbb{N}$. Then, by
Definition 4.2,

$\displaystyle\mathrm{Fld}_{s}(\mathbb{N}^{\prime})(s(q))$ $\displaystyle=$
$\displaystyle\mathbb{N}^{\prime}(q)\subseteq\mathbb{N}(q)=\mathbb{M}(s(q))~{}~{}\forall
q\in Q\mbox{ and }$
$\displaystyle\mathrm{Fld}_{s}(\mathbb{N}^{\prime})(s(p)\leq_{P}s(q))$
$\displaystyle=$
$\displaystyle\mathbb{N}^{\prime}(p\leq_{Q}q)=\mathbb{N}(p\leq_{Q}q)|_{\mathbb{N}^{\prime}(p)}=\mathbb{M}(s(p)\leq_{P}s(q))|_{\mathrm{Fld}_{s}(\mathbb{N}^{\prime})(s(p))},$

which establishes that $\mathrm{Fld}_{s}(\mathbb{N}^{\prime})$ is a submodule
of $\mathbb{M}$.

For the converse statement, check that
$\mathrm{Fld}_{s}^{-1}(\mathbb{M}^{\prime})$ necessarily exists and it is a
submdoule of $\mathbb{M}$ by definition of unfolding. ∎

###### Proof of Theorem 4.1.

(1) By Proposition B.3, both $\mathrm{Fld}_{s}(\mathbb{N}_{1})$ and
$\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})$ exist and they are submodules of
$\mathbb{M}$ by Proposition B.4. If we show that
$\mathbb{M}(p)=\mathrm{Fld}_{s}(\mathbb{N}_{1})(p)\oplus\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})(p)$
for every $p\in P$, then
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{N}_{1})\oplus\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})$
due to Proposition B.2.

We have
$\mathbb{M}(p)=\mathrm{Fld}_{s}(\mathbb{N})(p)=\mathrm{Fld}_{s}(\mathbb{N}_{1}\oplus\overline{\mathbb{N}_{1}})(p)=\mathrm{Fld}_{s}(\mathbb{N}_{1})(p)\oplus\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})(p)$.

(2) For the converse, observe that $\mathrm{Fld}_{s}^{-1}(\mathbb{M}_{1})$ and
$\mathrm{Fld}_{s}^{-1}(\overline{\mathbb{M}_{1}})$ necessarily exist and they
are submodules of $\mathbb{N}$ by Proposition B.4. Furthermore,
$\mathbb{N}(q)=\mathrm{Fld}_{s}^{-1}(\mathbb{M})(q)=(\mathrm{Fld}_{s}^{-1}(\mathbb{M}_{1}\oplus\overline{\mathbb{M}_{1}}))(q)=\mathrm{Fld}_{s}^{-1}(\mathbb{M}_{1})(q)\oplus\mathrm{Fld}_{s}^{-1}(\overline{\mathbb{M}_{1}})(q)$.
Then, by Proposition B.2, we have
$\mathbb{N}=\mathrm{Fld}_{s}^{-1}(\mathbb{M}_{1})\oplus\mathrm{Fld}_{s}^{-1}(\overline{\mathbb{M}_{1}})$.

(3) By assumption, we have
$\mathbb{M}=\mathrm{Fld}_{s}\mathbb{N}_{1}\oplus\overline{\mathrm{Fld}_{s}\mathbb{N}_{1}}$.
Then, applying (2) above, we have
$\mathbb{N}=\mathrm{Fld}_{s}^{-1}(\mathrm{Fld}_{s}\mathbb{N}_{1})\oplus\mathrm{Fld}_{s}^{-1}(\overline{\mathrm{Fld}_{s}\mathbb{N}_{1}})=\mathbb{N}_{1}\oplus\mathrm{Fld}_{s}^{-1}(\overline{\mathrm{Fld}_{s}\mathbb{N}_{1}})$.
Let
$\mathbb{U}=\mathrm{Fld}_{s}^{-1}(\overline{\mathrm{Fld}_{s}\mathbb{N}_{1}})$
which is foldable. It follows from Azumaya-Krull-Remak-Schmidt theorem [1]
that there is an automorphism of $\mathbb{N}$ that sends $\mathbb{U}$ to
$\overline{\mathbb{N}_{1}}$ where $\mathbb{U}$ is foldable. Either this
automorphism is an identity in which case $\overline{\mathbb{N}_{1}}$ is
flodable. Otherwise, $\overline{\mathbb{N}_{1}}$ is obtained by pointwise
addition of the interval module $\mathbb{N}_{1}$ to one of the indecomposables
of $\mathbb{U}$ in which case $\overline{\mathbb{N}_{1}}$ becomes foldable
because both $\mathbb{N}_{1}$ and $\mathbb{U}$ are foldable. It follows that
$\mathrm{Fld}_{s}(\overline{\mathbb{N}_{1}})$ exists and is a summand of
$\mathbb{M}$ by the conclusion in (1). ∎

##  Appendix C Missing proof in section 5

###### Proof of Proposition 5.1.

First, Proposition 3.1 allows us to write

${\sf b}^{\mathbb{I}}=\sum_{i=1}^{\ell}\alpha_{i}{\sf
b}^{\mathbb{I}_{i}}\mbox{ for some unique
}\alpha_{i}\in\mathbb{F},i\in[\ell].$

Suppose that the claim of the proposition is not true. Fix a point $p\in
P_{ZZ}$. We have ${\sf b}^{\mathbb{I}}_{p}=\sum_{i=1}^{\ell}\alpha_{i}{\sf
b}^{\mathbb{I}_{i}}_{p}$. Recall the quotient map $\rho$ for colimit in
Proposition A.1(ii). For each vector $v_{i}={\sf b}^{\mathbb{I}_{i}}_{p}$, the
quotient vector $\rho(v_{i})$ is a zero element in the colimit
$\mathsf{colim}\,\mathbb{M}_{ZZ}$ because the limit module $\mathbb{I}_{i}$
which is not full either has a sequence of vectors
$v_{i}\leftrightarrow\cdots\rightarrow 0$ or $0\leftarrow\cdots\leftrightarrow
v_{i}$ in its representative and thus $v_{i}\sim 0$ (Notation A.1). It follows
that any representative of $\mathbb{I}$ is sent to a zero element in
$\mathsf{colim}\,\mathbb{M}_{ZZ}$. Since $\mathbb{I}$ is $s$-complete,
$\mathrm{Fld}_{s}(\mathbb{I})$ exists and its representative is an element of
$\mathsf{lim}\,\mathbb{M}$. The definition of the folding implies that the
limit-to-colimit map sends the representative of
$\mathrm{Fld}_{s}(\mathbb{I})$ also to a zero element in
$\mathsf{colim}\,\mathbb{M}$.

Since $\mathbb{I}$ is $s$-complete, it is foldable and its complement is also
foldable. Then, $\mathrm{Fld}_{s}(\mathbb{I})$ is a full interval summand of
$\mathbb{M}$ according to Theorem 4.1(1). Since the full interval summand
$\mathrm{Fld}_{s}(\mathbb{I})$ is sent to zero by the limit-to-colimit map, we
have ${\sf{rk}}(\mathbb{M}^{\prime})={\sf{rk}}(\mathbb{M})$ where
$\mathbb{M}=\mathrm{Fld}_{s}(\mathbb{I})\oplus\mathbb{M}^{\prime}$. However,
${\sf{rk}}(\mathbb{M}^{\prime})\leq{\sf{rk}}(\mathbb{M})-1$ according to
Theorem 2.2 reaching a contradiction. ∎


* [37] F. Renac, A robust high-order Lagrange-projection like scheme with large time steps for the isentropic Euler equations, Numer. Math., 135 (2017), pp. 493–519, https://doi.org/https://doi.org/10.1007/s00211-016-0807-0.
  * [38] F. Renac, Entropy stable DGSEM for nonlinear hyperbolic systems in nonconservative form with application to two-phase flows, J. Comput. Phys., 382 (2019), pp. 1–26, https://doi.org/https://doi.org/10.1016/j.jcp.2018.12.035.
  * [39] F. Renac, Entropy stable, robust and high-order DGSEM for the compressible multicomponent Euler equations, J. Comput. Phys., 445 (2021), p. 110584, https://doi.org/10.1016/j.jcp.2021.110584.
  * [40] A. M. Rueda-Ramírez, E. Ferrer, D. A. Kopriva, G. Rubio, and E. Valero, A statically condensed discontinuous galerkin spectral element method on gauss-lobatto nodes for the compressible navier-stokes equations, J. Comput. Phys., 426 (2021), p. 109953, https://doi.org/https://doi.org/10.1016/j.jcp.2020.109953.
  * [41] Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, second ed., 2003, https://doi.org/https://doi.org/10.1137/1.9780898718003.
  * [42] B. Strand, Summation by parts for finite difference approximations for d/dx, J. Comput. Phys., 110 (1994), pp. 47–67, https://doi.org/https://doi.org/10.1006/jcph.1994.1005.
  * [43] E. Tadmor, The numerical viscosity of entropy stable schemes for systems of conservation laws. i, Math. Comp., 49 (1987), pp. 91–103.
  * [44] J. J. W. van der Vegt, Y. Xia, and Y. Xu, Positivity preserving limiters for time-implicit higher order accurate discontinuous Galerkin discretizations, SIAM J. Sci. Comput., 41 (2019), pp. A2037–A2063, https://doi.org/10.1137/18M1227998.
  * [45] C. F. Van Loan, The ubiquitous Kronecker product, J. Comput. Appl. Math., 123 (2000), pp. 85–100, https://doi.org/https://doi.org/10.1016/S0377-0427(00)00393-9.
  * [46] C. F. Van Loan, Structured Matrix Problems from Tensors, Springer International Publishing, Cham, 2016, pp. 1–63, https://doi.org/10.1007/978-3-319-49887-4_1.
  * [47] M. Waruszewski, J. E. Kozdon, L. C. Wilcox, T. H. Gibson, and F. X. Giraldo, Entropy stable discontinuous Galerkin methods for balance laws in non-conservative form: Applications to the Euler equations with gravity, J. Comput. Phys., 468 (2022), p. 111507, https://doi.org/https://doi.org/10.1016/j.jcp.2022.111507.
  * [48] A. R. Winters, D. Derigs, G. J. Gassner, and S. Walch, A uniquely defined entropy stable matrix dissipation operator for high Mach number ideal MHD and compressible Euler simulations, J. Comput. Phys., 332 (2017), pp. 274–289.
  * [49] A. R. Winters and G. J. Gassner, Affordable, entropy conserving and entropy stable flux functions for the ideal MHD equations, J. Comput. Phys., 304 (2016), pp. 72–108.
  * [50] Z. Xu and C.-W. Shu, High order conservative positivity-preserving discontinuous galerkin method for stationary hyperbolic equations, J. Comput. Phys., 466 (2022), p. 111410, https://doi.org/https://doi.org/10.1016/j.jcp.2022.111410.
  * [51] Z. Xu and C.-W. Shu, On the conservation property of positivity-preserving discontinuous galerkin methods for stationary hyperbolic equations, J. Comput. Phys., 490 (2023), p. 112304, https://doi.org/https://doi.org/10.1016/j.jcp.2023.112304.
  * [52] S. T. Zalesak, Fully multidimensional flux-corrected transport algorithms for fluids, J. Comput. Phys., 31 (1979), pp. 335–362.
  * [53] X. Zhang and C.-W. Shu, On maximum-principle-satisfying high order schemes for scalar conservation laws, J. Comput. Phys., 229 (2010), pp. 3091–3120.
  * [54] X. Zhang and C.-W. Shu, On positivity-preserving high order discontinuous Galerkin schemes for compressible Euler equations on rectangular meshes, J. Comput. Phys., 229 (2010), pp. 8918–8934.
  * [55] X. Zhang, Y. Xia, and C.-W. Shu, Maximum-principle-satisfying and positivity-preserving high order discontinuous Galerkin schemes for conservation laws on triangular meshes, Journal of Scientific Computing, 50 (2012), pp. 29–62.