Persistent Homology Algorithm

Algorithm for Fields
In this section we describe an algorithm for computing persistent homology over a field.

We use the small filtration as an example and compute over $\mathbb{Z}_2$ , although the algorithm works for any field.
A filtered simplicial complex with new simplices added at each stage. The integers on the bottom row corresponds to the degrees of the simplices of the filtration as homogenous elements of the persistence module.

The persistence module corresponds to a $\mathbb{Z}_2[t]$ -module by the correspondence in previous Theorem. In this section we use $\{e_j\}$ and $\{\hat{e}_i\}$ to denote homogeneous bases for $C_k$ and $C_{k-1}$ respectively.

We have $\partial_1(ab)=-t\cdot a+t\cdot b=t\cdot a+t\cdot b$ since we are computing over $\mathbb{Z}_2$ . Then the representation matrix for $\partial_1$ is
$\displaystyle M_1=\begin{bmatrix}[c|ccccc] &ab &bc &cd &ad &ac\\ \hline d & 0 & 0 & t & t & 0\\ c & 0 & 1 & t & 0 & t^2\\ b & t & t & 0 & 0 & 0\\ a &t &0 &0 &t^2 &t^3 \end{bmatrix}.$

In general, any representation $M_k$ of $\partial_k$ has the following basic property: $\displaystyle \deg\hat{e}_i+\deg M_k(i,j)=\deg e_j$ provided $M_k(i,j)\neq 0$ .

We need to represent $\partial_k: C_k\to C_{k-1}$ relative to the standard basis for $C_k$ and a homogenous basis for $Z_{k-1}=\ker\partial_{k-1}$ . We then reduce the matrix according to the reduction algorithm described previously.

We compute the representations inductively in dimension. Since $\partial_0\equiv 0$ , $Z_0=C_0$ hence the standard basis may be used to represent $\partial_1$ . Now, suppose we have a matrix representation $M_k$ of $\partial_k$ relative to the standard basis $\{e_j\}$ for $C_k$ and a homogeneous basis $\{\hat{e}_i\}$ for $Z_{k-1}$ .

For the inductive step, we need to compute a homogeneous basis for $Z_k$ and represent $\partial_{k+1}$ relative to $C_{k+1}$ and the homogeneous basis for $Z_k$ . We first sort the basis $\hat{e}_i$ in reverse degree order. Next, we make $M_k$ into the column-echelon form $\tilde{M}_k$ by Gaussian elimination on the columns, using elementary column operations. From linear algebra, we know that $rank M_k=rank B_{k-1}$ is the number of pivots in the echelon form. The basis elements corresponding to non-pivot columns form the desired basis for $Z_k$ .