Computing Persistent Homology

Preliminaries

The following module computes a Vietoris-Rips filtration from a point cloud. The filtration is returned as a list of simplices, each associated with the distance value at which it appears in the filtration.

computeVRfiltration[points_,maxDist_:∞]:=Module[
{n=Length[points],
dists,
filtration,
dist,triangles
},

(* compute all edge lengths *) 
dists=Table[0,n,n];
Do[
dists[[i,j]]=EuclideanDistance[points[[i]],points[[j]]]
,{i,1,n},{j,i+1,n}];

(* build the simplicial complex *)
filtration=Table[{i}->0,{i,1,n}];
Do[
If[dists[[i,j]]<=maxDist,
AppendTo[filtration,{i,j}->dists[[i,j]]];
Do[
If[dists[[i,k]]<=maxDist&&dists[[j,k]]<=maxDist,
AppendTo[filtration,{i,j,k}->Max[dists[[i,j]],dists[[i,k]],dists[[j,k]]]]
]
,{k,j+1,n}]
]
,{i,1,n},{j,i+1,n}];

(* return the simplicial complex *) 
SortBy[filtration,Last]
]

The following module computes the boundary matrix (∂_j) of a Vietoris-Rips filtration. Row and column simplices are ordered according to their order of appearance in the filtration.

computeBoundaryMx[filtration_,dim_]:=Module[
{rowSimplices,colSimplices,matrix,faces,r},

(* get the lists of simplices in adjacent dimensions *) 
rowSimplices=Keys[Select[filtration,Length[First[#]]==dim&]];
(*Print[rowSimplices];*)
colSimplices=Keys[Select[filtration,Length[First[#]]==dim+1&]];
(*Print[colSimplices];*)
(* handle empty matrix *)
If[Length[rowSimplices]==0||Length[colSimplices]==0,Return[{{}}]];

(* initialize a matrix *) 
matrix=Table[0,Length[rowSimplices],Length[colSimplices]];

(* loop over all columns *)
Do[
(* loop over all codim 1 faces of this simplex *)
faces=Subsets[colSimplices[[c]],{dim}];
Do[
(* set the correct entry to 1 *) 
r=Position[rowSimplices,f,1][[1,1]];
matrix[[r,c]]=1;
,{f,faces}];
,{c,1,Length[colSimplices]}];

(* return the matrix*) 
matrix
]

Matrix Reduction

Here is a point cloud:

points={{0.7689,0.083849},{0.023843,0.321199},{0.68597,0.970322},{0.479365,0.254942},{0.411302,0.130928},{0.628332,0.298282},{0.596307,0.311435}};
pointPlot=ListPlot[points->Range[Length[points]],PlotRange->{{0,1},{0,1}},AspectRatio->1]

Here is the Vietoris-Rips filtration on this point cloud:

filtration=computeVRfiltration[points]

Here are the boundary matrices (∂_0), (∂_1), and (∂_2) for this filtration:

d0=computeBoundaryMx[filtration,0]

d1=computeBoundaryMx[filtration,1];
MatrixForm[d1]

d2=computeBoundaryMx[filtration,2];
MatrixForm[d2]

Your tasks:

Write a module to reduce a boundary matrix using left-to-right column additions, with mod 2 arithmetic. Use your code to reduce the matrices above.

Identify the pairings of simplices given by the “low” entries of the reduced matrices.

Write down the persistent homology barcode given by the pairings of simplices that you identified.