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.

Source: “Computing Persistent Homology” by Zomorodian & Carlsson

Advertisements

About mathtuition88

http://mathtuition88.com
This entry was posted in math and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s