Distributed computation of persistent homology

1 Introduction

• Available memory remains a practical constraint because persistence computation can take less time than reading the input after algorithmic optimizations.Prior parallelization efforts described here use shared-memory systems.Source: §1 · p. 2
• The proposed parallel distributed-memory algorithm is intended to compute instances too large for state-of-the-art algorithms on a single machine.Its primary purpose is overcoming the memory bottleneck while also aiming for time efficiency.Source: §1 · p. 2
• The implementation scales memory usage across nodes and outperforms similar parallel shared-memory code in running time.The authors note that this is surprising given the global nature of persistent homology and their algorithm's simple communication pattern.Source: §1 · p. 2
• Reduced columns are stored by pivot rather than matrix index, allowing local eliminations; message batching and neighbor-only communication further simplify communication.The method also incorporates the clearing optimization to avoid unnecessary column operations.Source: §1 · p. 2

2 Background

• The exposition limits its description to simplicial homology over Z2 for simplicity, while stating that the methods generalize to chain complexes over arbitrary fields.Homology is defined as cycles modulo boundaries, with Betti numbers giving the dimension of the homology group.Source: §2 · p. 3
• A simplexwise filtration adds one simplex at each step, and persistence tracks homology classes as they are born and die across the sequence.A birth-death index pair has persistence equal to the difference between its indices.Source: §2 · p. 3
• The boundary matrix encodes which simplices are codimension-one faces of each simplex, and a column's pivot is its largest-index nonzero row.The matrix is upper triangular because faces precede their simplices in the filtration.Source: §2 · p. 3
• Reduction uses left-to-right column additions to obtain unique pivots, and the set of persistence pairs is invariant across reductions.The standard procedure processes columns from left to right and has a worst-case running time of at most cubic in the number of simplices.Source: §2 · p. 4
• In a reduction, nonzero columns among the first i columns form a basis of the boundary group, and a nonzero column with pivot i identifies a persistence pair.The passage states that the resulting pairs are the persistence pairs of the filtration.Source: §2 · p. 4
• Clearing reduces the boundary matrix dimension by dimension in decreasing order, setting pivot-index columns to zero before reducing the next dimension.This optimization follows from the fact that a pivot index corresponds to a zero column in any reduction.Source: §2 · p. 5

Reduction in blocks

• Each block reduction eliminates columns in increasing order, adding earlier columns with matching pivots until the current pivot no longer conflicts.A block is reducible when its left and upper neighboring blocks have already been reduced.Source: §3 · p. 5

Parallel reduction

• Diagonal blocks are independent; later blocks can be reduced once their left and upper dependencies are reduced, yielding a reduction of the input matrix.Blocks on the same diagonal sweep phase can also be processed independently.Source: §3 · p. 6

Distributed reduction

• Each node retains reduced columns whose pivots fall in its row range, while unreduced columns move between nodes; each matrix column is stored on exactly one node.The node processes blocks from left to right and sends unreduced columns to its predecessor.Source: §3 · p. 6
• Each node communicates only with its immediate neighbors, and fewer than p messages pass between each consecutive node pair.The authors state that this simple pattern makes communication overhead and network latency negligible.Source: §3 · p. 6

Clearing in parallel

• A single global partition lets a node clear columns whose indices were pivots in the preceding dimension, without communicating with other nodes.Those pivots correspond to simplices that create homology and therefore to zero columns in any reduction.Source: §3 · p. 7

Design rationale

• Blocking package transfers can delay processing, but ensures each node holds at most one package and prevents package accumulation from increasing memory use.The design rationale contrasts this with direct pivot routing, which complicates data management and prevents bounding queued columns; sending reduced columns forward is expected to transfer more data.Source: §3 · p. 7

Experimental evaluation

• The section identifies peak-memory and running-time comparisons for Phat and Dipha, but the supplied table passages provide no measured values.Table 1 covers peak memory; Table 2 covers running times.Source: Table 1 · p. 8, Table 2 · p. 8

Experimental setup

• The comparison used Phat's best tested sequential and parallel shared-memory variants, with only one processor core per node for distributed runs.The experiments were designed to assess scaling and compare against state-of-the-art implementations on instances feasible in the shared-memory setting.Source: §4 · p. 8
• Tests used 256^3 and 512^3 image filtrations from isotropic Gaussian random fields, plus the 512^3 vertebra16 medical image.The cluster had up to 32 nodes connected by a 40Gbit Infiniband interconnect.Source: §4 · pp. 8–9

Scalability

• Memory per node nearly halves as node count doubles, and running time also falls, providing evidence of scaling in both space and time.The tables are incomplete because address-space limitations in the OpenMPI I/O API prevented some cases from being computed.Source: §4 · p. 9

Comparison

• On 16 nodes, the distributed algorithm ran faster than the 16-core shared-memory algorithm, while both Phat variants ran out of memory on larger examples.The authors suggest the distributed system's larger total processor cache may outweigh network communication overhead for memory-intensive matrix reduction.Source: §4 · p. 9

Communication analysis

• For challenging examples, communication reached gigabytes, yet local block reductions dominated communication time.Figure 1 plots block-reduction times by dimension for vertebra16 on 32 nodes.Source: §4 · p. 9, Figure 1 · p. 9

• The distributed approach permits computation of instances infeasible for previous methods and speeds computation for previously feasible instances.Source: §5 · p. 10
• The implementation resembles the spectral sequence algorithm, with lower-level design choices adapted for distributed memory.Source: §5 · p. 10
• Benchmarking is constrained because generating the filtration input can itself require massive computation and become infeasible on a single machine.The authors are developing distributed methods for generating filtrations of large 3D images and Rips filtrations.Source: §5 · p. 10