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 , 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 -module by the correspondence in previous Theorem. In this section we use and to denote homogeneous bases for and respectively.
We have since we are computing over . Then the representation matrix for is
In general, any representation of has the following basic property: provided .
We need to represent relative to the standard basis for and a homogenous basis for . We then reduce the matrix according to the reduction algorithm described previously.
We compute the representations inductively in dimension. Since , hence the standard basis may be used to represent . Now, suppose we have a matrix representation of relative to the standard basis for and a homogeneous basis for .
For the inductive step, we need to compute a homogeneous basis for and represent relative to and the homogeneous basis for . We first sort the basis in reverse degree order. Next, we make into the column-echelon form by Gaussian elimination on the columns, using elementary column operations. From linear algebra, we know that is the number of pivots in the echelon form. The basis elements corresponding to non-pivot columns form the desired basis for .
Source: “Computing Persistent Homology” by Zomorodian & Carlsson