Interactive Visualization of 2-D Persistence Modules

1.1 Overview

• RIVET provides interactive exploratory analysis for 2-D persistence, dynamically browsing persistence barcodes while offering more information and flexibility than standard 1-D persistence.The paper restricts attention to 2-D because extending the approach to 3-D presents substantial computational and interface challenges.Source: §1.1 · pp. 2–3

1.2 Multidimensional Filtrations and Persistence Modules

• An n-D filtration is a functor from the coordinatewise-ordered R^n to simplicial complexes, while an n-D persistence module is a functor to vector spaces.Finite filtrations yield pointwise finite-dimensional homology persistence modules with finite presentations.Source: §1.2 · pp. 3–4

1.3 Persistence Barcodes of Data

• The standard 1-D pipeline constructs a filtration, applies homology, and records interval barcodes whose lengths measure feature robustness.The filtration can be chosen flexibly; the Vietoris–Rips construction is a standard choice for finite metric spaces.Source: §1.3 · p. 5

1.4 Multidimensional Persistent Homology

• Multidimensional persistence addresses 1-D barcodes’ sensitivity to outliers and insensitivity to dense-region structure, but its indecomposable modules are too complicated for useful visualization.A parameter-free bifiltration, B-Rips(P), yields a richer invariant that is sensitive to structure in high-density regions.Source: §1.4 · pp. 6–8

1.5 The Rank Invariant and Fibered Barcodes

• The fibered barcode assigns each affine line in a 2-D persistence module the barcode of its 1-D restriction, and it determines the rank invariant together with it.RIVET computes this invariant alongside the dimension function and multigraded Betti numbers.Source: §1.4 · p. 8, §1.5 · pp. 9–10
• Fibered barcodes are robust to perturbations of both the module and slicing line, with greater robustness for lines whose slope is closer to 1.External stability has a slope-dependent Lipschitz constant, equal to 1 for slope 1 and diverging near horizontal or vertical lines; internal stability likewise improves near slope 1.Source: §1.5 · p. 10

1.6 Multigraded Betti Numbers

• The project contributes a fast algorithm for computing multigraded Betti numbers, which are central both to RIVET’s visualization and to constructing its augmented arrangement.The paper emphasizes ξ0 and ξ1 as generators and relations in minimal presentations, while the companion algorithm computes the Betti numbers efficiently.Source: §1.6 · pp. 10–11, §1.10 · p. 16

1.7 The RIVET Visualization Paradigm

• RIVET interactively visualizes fibered barcodes alongside the dimension function and bigraded Betti numbers, combining global coarse views with sharper local barcode views.Users select and move a line through a graphical interface, while the associated barcode and persistence diagram update in real time.Source: §1.7 · pp. 11, 13

1.8 Querying the Fibered Barcode

• The augmented arrangement A•(M) enables correct fast queries for B(M_L) by storing barcode templates on cells of a planar line arrangement and pushing template endpoints onto the selected line.A query identifies the cell containing L and transforms each stored pair in its template to recover the slice barcode.Source: §1.8 · pp. 13–14

1.9 Complexity Results for Computing, Storing, and Querying The Augmented Arrangement

• For a 2-D module, querying generic lines in 2-cells takes O(log κ + |B(M_L)|), other lines use a perturbation L′ with O(log κ + |B(M_L′)|), and construction from F takes O(m^3κ + (m + log κ)κ^2) operations and O(m^2 + mκ^2) storage.Source: §1.9 · p. 15

1.10 Computation of the Augmented Arrangement

• The augmented-arrangement computation combines Betti-number computation, line-arrangement construction, and barcode-template computation, with the template phase most expensive and accelerated in practice using a vineyard-based modification.Template computation is embarrassingly parallelizable, and preliminary results indicate that even the current unoptimized implementation can process millions of simplices with modest coarsening on a standard computer.Source: §1.10 · pp. 16–17

1.11 Outline

• The paper proceeds from persistence-module and Betti-number foundations, through augmented-arrangement definition, querying, construction, complexity analysis, practical speedups, and preliminary timing results.The outline also identifies Appendix A.1 as providing additional RIVET interface details.Source: §1.11 · p. 17

2.1 A Module-Theoretic Description of Multi-D Persistence Modules

• Multi-dimensional persistence modules are identified with R^n-graded P_n-modules, where P_n allows nonnegative real exponents and module actions shift grades by vectors in [0,∞)^n.Morphisms preserve grading, yielding an equivalent module-theoretic description of Vect_R^n.Source: §2.1 · p. 18

2.2 Free n-Modules and Presentations

• Free n-modules are constructed from graded generators, and presentations express M as Free[W]/⟨Y⟩ with homogeneous relations; the rank invariant alone does not determine isomorphism type.Modules M and N can have equal rank but unequal induced-map ranks, proving they are not isomorphic.Source: §2.2 · p. 19

2.3 Minimal Presentations of n-Modules

• A finite presentation is minimal exactly when its generators and relations are minimal, and every finitely presented persistence module therefore has a minimal presentation.This characterization supplies the minimal presentations used in subsequent Betti-number definitions.Source: §2.3 · p. 20

2.4 Graded Betti Numbers of Persistence Modules

• Graded Betti numbers record presentation data, while for finitely presented modules equal grades of influence imply that the corresponding structure map is an isomorphism.The section focuses on ξ_0(M) and ξ_1(M), and uses the resulting local constancy in later constructions.Source: §2.4 · pp. 20–21

2.5 Continuous Extensions of Discrete Persistence Modules

• Every finitely presented n-module is a continuous extension of a finitely generated discrete module along a suitable n-dimensional grid.For injective grids, Betti numbers transfer from the discrete module at grid points and vanish elsewhere, enabling RIVET’s computations for R^2-indexed modules.Source: §2.5 · p. 22
• Continuous extension also transfers discrete barcodes to the continuous setting, including persistence modules indexed by lines, which later supports augmented-arrangement barcode queries.For a line L, the same grid and extension framework applies after identifying its poset category with R.Source: §2.5 · p. 24

3 Augmented Arrangements of 2-D Persistence Modules

• A•(M) consists of the line arrangement A(M) together with a barcode template T_e stored at every 2-cell e.The construction proceeds by defining A(M), characterizing its 1-skeleton, and then defining the templates.Source: §3 · p. 24

3.1 Definition of A(M)

• A(M) is determined by S through lines dual to lines containing anchors, with at most κ lines and at most κ^2 vertices, edges, and faces.Anchors are least upper bounds of weakly incomparable pairs in S, and the 1-skeleton also includes the boundary line x = 0.Source: §3.1 · p. 26

3.2 Characterization of the 1-Skeleton of A(M)

• The 1-skeleton of A(M) is exactly the set of critical lines, and lines through anchors are critical because small perturbations reverse the push-order of the corresponding points.Within each 2-cell, the totally ordered partition S_L is constant; equivalently, lines whose duals lie in the same 2-cell induce the same partition.Source: §3.2 · pp. 27–29

3.3 The Barcode Templates T_e

• Each 2-cell e yields a totally ordered partition S_e, which defines a discrete persistence module M_e and its barcode template T_e.The completed augmented arrangement is determined by the fibered barcode B(M) and S, while the next section shows that it conversely determines B(M).Source: §3.3 · pp. 29–30

4.1 Selecting a 2-D Coface e of L

• The selected 2-cell is any coface for generic lines, the bottom coface for horizontal lines, and a slope- and intercept-determined coface or bottom unbounded cell for vertical lines.Vertical selection uses the arrangement line of greatest slope not exceeding x = a, breaking ties by largest y-intercept.Source: §4.1 · p. 30

4.2 The Query Theorem

• Theorem 4.1 recovers B(M_L) by pushing each template pair (a, b) onto L and retaining exactly those with push_L(a) < push_L(b).If Dℓ(L) lies in a 2-cell, all pushed endpoints are strictly ordered; otherwise equality can occur.Source: §4.2 · p. 31

4.3 Computational Details of Queries

• Queries first locate the appropriate 2-cell and then push its stored barcode-template endpoints, with DCEL storage preserving template multiplicities.Nonvertical point-location preprocessing has O(κ^2) size and O(log κ) query time, while vertical queries use a sorted array and binary search in log n_l time.Source: §4.3 · p. 33
• O(|T_e| + log κ) time answers a barcode query after preprocessing, with O(|B(M_L)| + log κ) when Dℓ(L) lies in the selected cell.For other lines, |T_e| equals the barcode size of an arbitrarily small perturbation L′ whose dual point lies in the selected cell.Source: §4.3 · p. 34

5.1 Free Implicit Representations of Persistence Modules: The Input to our Algorithm

• An FI-representation Φ = (gr1, gr2, D1, D2) encodes M as ker ∂1 / im ∂2 with D1 and D2 representing composable boundary maps satisfying ∂1 ◦ ∂2 = 0.The algorithm accepts such an FI-representation, including the degenerate presentation case m0 = 0.Source: §5.1 · p. 34

5.2 Motivation: Free Implicit Representations From Finite Filtrations

• FI-representations arise naturally from finite bifiltrations: they can be computed for any homology index in O(l log l) time, while single-index arrangement computation avoids unnecessary work.The construction generalizes from 1-critical filtrations, whose chain modules are free, to multi-critical filtrations through an FI-representation construction.Source: §5.2 · pp. 35–37

5.3 Computation of Betti Numbers

• The Betti-number algorithm computes ξ0, ξ1, and ξ2 in O(m^3) time for an FI-representation of dimensions (m0, m1, m2), where m = m0 + m1 + m2.The arrangement computation uses ξ0 and ξ1 to obtain S = supp ξ0(M) ∪ supp ξ1(M).Source: §5.3 · p. 37

5.4 Computation and Storage of Anchors and Template Points

• After Betti numbers are computed in lexicographic order, anchors and the sparse template-point structure tPtsMat are built simultaneously in O(nx × ny) = O(m^2) time beyond the O(m^3) Betti computation.Constant-time anchor tests use row and column pointers, while tPtsMat stores each template point with links to neighboring entries.Source: §5.4 · pp. 39–40

5.5 Building the Line Arrangement

• Bentley–Ottmann constructs the DCEL arrangement in O(κ^2 log κ) operations, whose representation has size O(κ^2); the implementation uses hybrid arithmetic to limit numerical errors [29].Asymptotically faster arrangement algorithms can remove the log κ factor, but Bentley–Ottmann is retained for simplicity and practical performance.Source: §5.5 · pp. 40–41

6 Computing the Barcode Templates

• Barcode templates are computed for every 2-cell after constructing the anchors and line arrangement, using an algorithm later refined for faster practical performance.The computation targets each template T_e without needing to explicitly store B(M_e) or ζ_e.Source: §6 · p. 41
• The algorithm takes a free implicit representation, a sparse matrix of template points, and a DCEL representation of the line arrangement as input.The free implicit representation is supplied, while the other representations are computed from it earlier.Source: §6 · p. 41

6.1 Trimming the Free Implicit Representation

• Trimming replaces an untrimmed free implicit representation with a smaller equivalent one, enabling simpler and more efficient barcode-template computation.Given the template-point matrix and column-sparse representation, trimming takes O(m + d) time, where d = O(m^2) is the number of non-zero entries of D2.Source: §6.1 · pp. 42–43

6.2 RU-Decompositions and Computation of Persistence Barcodes

• RU-decompositions factor boundary matrices as D = RU, with R reduced and U upper-triangular, allowing persistence barcodes to be read from the factors.For an r × s matrix, the standard algorithm runs in O(rs^2) time.Source: §6.2 · p. 43
• The vineyard algorithm updates an RU-decomposition after swapping adjacent rows or columns in O(d1 + d2) time, making it essential for barcode-template computation.It applies when D′ is obtained from D by transposing two adjacent rows or columns.Source: §6.2 · p. 44

6.3 Permutations of Free Implicit Representations

• Permuting the generators and corresponding matrix rows or columns preserves the represented module, so grade functions can be reordered without changing the FI-representation’s homology.For one-dimensional modules, suitable permutations make both grade functions non-decreasing, enabling barcode recovery from RU-decompositions.Source: §6.3 · p. 44
• Insertion sort orders each grade list into non-decreasing order while expressing the required permutation as a minimum-length product of adjacent transpositions.This adjacent-transposition structure is chosen to exploit vineyard updates in the main algorithm.Source: §6.3 · p. 44

6.4 Induced Free Implicit Representations at Each 2-Cell

• For every 2-cell e, Φ induces a free implicit representation Φ_e of the discrete persistence module M_e, enabling B(M_e) to be computed from an RU-decomposition of Φ_e.Source: §6.4 · p. 45
• The induced representation uses lift maps that send points to minimal template points above them, with adjacent cells differing where these maps disagree.Source: §6.4 · p. 45
• A valid pair of permutations reorders the generators and matrices to form Φ_e, while different valid choices can produce different representations.Source: §6.4 · pp. 45–46
• The template map f_e is independent of the valid permutation choice, and together with the RU-decomposition of Φ_e determines the barcode template T_e.Source: §6.4 · p. 46, §6.5 · p. 46

6.5 Our Algorithm

• Rather than recomputing each T_e from scratch, the algorithm traverses a path Γ in the dual graph of the line arrangement that visits every 2-cell.Source: §6.5 · p. 46
• The initial cell is processed using combinatorial computations, row and column permutations, and the standard persistence algorithm to obtain f_0 and an RU-decomposition of Φ_0.Source: §6.5 · p. 47
• For each neighboring cell, the algorithm updates the template map and lift maps, derives valid permutations via insertion-sort transpositions, and applies RU updates for those transpositions.Source: §6.5 · pp. 47–48
• Transpositions are processed immediately during RU updates rather than stored explicitly, reducing the algorithm’s intermediate memory requirements.Source: §6.5 · p. 48

6.6 Computing the Path Γ

• Edge weights estimate transition work between arrangement cells, influencing Γ and barcode-template speed but not asymptotic complexity bounds.The exact weight definitions are deferred to Section 6.10.Source: §6.6 · p. 48
• A minimum-spanning-tree traversal computes a valid path Γ with length at most twice the optimal valid path length.The path starts at e0, visits every dual-graph vertex, and uses each spanning-tree edge at most twice.Source: §6.6 · p. 48

6.7 Data Structures

• The implementation combines RU-decomposition matrices with grades, lifts, signatures, and levSet arrays to support template evaluation and efficient updates between cells.The levSetj(u) lists encode cell-dependent information and are used when passing from cell ei−1 to cell ei; liftsj and sigj enable constant-time template-map evaluations.Source: §6.7 · p. 49

6.8 Computations at the Initial Cell e0

• At e0, levSetj(u) is nonempty only for rightmost points on horizontal lines, so its nonempty entries have unique y-coordinates.This structural property supports the initialization ordering used by the algorithm.Source: §6.8 · p. 50
• An O(m log m + mκ)-time sweep initializes levSetj(u) and liftsj, after which concatenation by increasing y-coordinate constructs sigInvj and sigj in O(mj) time.The resulting sigj arrays define the permutations σ0j.Source: §6.8 · p. 50
• Using column-sparse boundary representations and implicit row permutations, the initial matrix computation takes O(m) time.The algorithm then applies the standard persistence algorithm to obtain the RU-decompositions at e0.Source: §6.8 · p. 50

6.9 Computations at Cell ei, for i ≥1

• The cell-update algorithm interleaves lift updates with insertion-sort transpositions and corresponding RU-decomposition updates for greater efficiency.This avoids first completing the lift update and then sorting separately.Source: §6.9 · p. 50
• At each shared anchor boundary, elements are moved between levSetj(α), levSetj(u), and levSetj(v) according to their coordinates, updating liftsj accordingly.The procedure processes levSetj(α) and then levSetj(u) in decreasing order, with the latter requiring additional moves to levSetj(α).Source: §6.9 · p. 51
• When an update violates lift ordering, sortOneElement swaps adjacent entries in sigj and sigInvj while applying the corresponding RU-decomposition updates.The routine continues while adjacent lift values are out of order.Source: §6.9 · p. 51

6.10 Choosing Edge Weights for G

• Because RU-decomposition updates dominate barcode-template computation, edge weights approximate the expected insertion-sort cost while remaining independent of the chosen path Γ.The estimate depends only on the anchor line L containing an edge’s shared cell boundary, so w(E) = w(L).Source: §6.10 · p. 52
• Switching and separation behavior is invariant across adjacent-cell pairs sharing an anchor line, and every switching pair is incomparable.These facts allow switching and separation to be defined directly at an anchor line.Source: §6.10 · pp. 52–53
• The weight estimate counts switching pairs fully and separation pairs with an estimated 1/4 contribution, using the corresponding pair counts for gr1 and gr2.The estimate reflects that switching always causes a transposition, whereas separation may cause one only in a particular crossing direction.Source: §6.10 · p. 53
• The weights w(L) are computed by traversing a path that crosses each anchor line once, omitting matrix and RU-decomposition updates and classifying relevant pairs by four quadrants.Only elements in levSetj(u) and levSetj(α) need to be considered when crossing L.Source: §6.10 · p. 53

7 Cost of Computing and Storing the Augmented Arrangement

• The algorithm computes A•(M) in O(m^3κ + mκ^2 log κ) elementary operations and stores it using O(m^2 + mκ^2) space.These bounds are stated for a 2-D persistence module of coarseness κ with FI-representation dimensions (m0, m1, m2), where m = m0 + m1 + m2.Source: §7 · p. 54, §7.2 · p. 56

7.1 Size of the Augmented Arrangement

• The augmented arrangement has O(mκ^2) total representation size because its O(κ^2) cells store barcode templates of size at most m1.The DCEL arrangement itself has size O(κ^2), and the template storage is O(m1κ^2) = O(mκ^2).Source: §7.1 · p. 54

7.2 Cost of Computing the Augmented Arrangement

• The algorithm performs O(m^2κ) insertion-sort transpositions and signature-array updates, while all vineyard updates take O(m^3κ) time, with each transposition triggering at most two calls.Each vineyard call takes O(m) time, and computing all edge weights takes O(m^2 + mκ) time.Source: §7.2 · pp. 55–56

7.3 Bounding Total Number of Transpositions Required to Compute all Barcode Templates

• At most two anchor lines can cause any pair of points to switch or separate, yielding O(m^2κ) total insertion-sort transpositions.The bound follows because the path crosses each anchor line at most 2κ times, while each relevant pair can switch or separate only a bounded number of times.Source: §7.2 · p. 55, §7.3 · pp. 57, 58, 60

8 Speeding up the Computation of the Augmented Arrangement

• Combined runtime strategies make augmented arrangements feasible for persistent homology modules from much larger datasets.The strategies target the computation of A•(M) and improve practical runtime when used together.Source: §8 · p. 60

8.1 Persistence Computation from Scratch When RU-Updates are too Slow

• At each cell, the algorithm chooses among a fast clear-and-compress computation, full RU-recomputation, and vineyard updates by solving a minimum-cut optimization problem.The tradeoff is that the fastest option can preclude vineyard updates at the next cell; runtime estimates can be updated dynamically from measured costs over successive path segments.Source: §8.1 · pp. 61, 63

8.2 Coarsening of Persistence Modules

• O(m^3κ+(m+log κ)κ^2) elementary operations are required, while the arrangement size grows quadratically with module coarseness κ.Coarsening limits κ; if grid steps are at most δ, then the interleaving distance satisfies dI(M, MG) ≤ δ, and coarsening only the FI-representation’s grade functions constructs the coarsened input.Source: §8.2 · pp. 63–64

8.3 Parallelization

• With l^2 processors, selecting the l highest-weight anchor lines partitions the arrangement into at most l^2 polygonal cells processed independently.Each processor runs the serial algorithm on its cell’s induced arrangement; initialization is modified because the standard initial cell may not lie in that subarrangement.Source: §8.3 · p. 64

Limitations

• The results are preliminary because the implementation uses a simplified barcode-template scheme, linked-list sparse-matrix columns, and a single processing core.The authors expect substantial speedups from the Section 8.1 scheme, smarter column storage, and parallel barcode-template computation.Source: §9 · p. 65

Experimental Setup

• Computations ran on one slow 800 MHz core with 96 GB available RAM, while the largest computation used approximately 9.3 GB.Only a fraction of the server’s memory was required for the reported computations.Source: §9 · p. 65

Noisy Circle Data

• The synthetic datasets contain 90% noisy annulus samples and 10% samples from a containing square, analyzed with a codensity-based Vietoris–Rips bifiltration.The Euclidean scale parameter is capped slightly above the annulus’s inner diameter.Source: §9 · p. 65

Computing the Graded Betti Numbers

• Runtimes are reported for computing ξ0, ξ1, and ξ2 of H_i(F), with averages over three point clouds for each dataset size.For 100-point clouds, the resulting bifiltrations averaged 3,920 simplices for H0 computations.Source: §9 · p. 65, Table 3 · p. 66

Building the Augmented Arrangement

• Tables report average runtimes for building augmented arrangements of H0(F) and H1(F) across four coarsenings, averaged over three point clouds per size.The H0 and H1 results are presented separately in Tables 4 and 5.Source: §9 · p. 65, Table 4 · p. 66, Table 5 · p. 66

Contributions

• RIVET interactively visualizes affine-slice barcodes, dimension functions, and bigraded Betti numbers for 2-D persistence modules.The visualization paradigm is supported by a mathematical theory centered on augmented arrangements.Source: §10 · p. 66

Computational foundation

• The paper introduces and analyzes an algorithm for computing augmented arrangements, with practical strategies for improving its runtime.These arrangements form the computational foundation of RIVET’s visualization capabilities.Source: §10 · pp. 66–67

Empirical scaling

• Preliminary timing experiments show that the current implementation scales well enough to study bifitrations with millions of simplices, despite several unimplemented optimizations.The authors expect further implementation work to support settings where 1-D persistence is used for exploratory data analysis.Source: §10 · p. 67

Future directions

• Future directions include scientific-data applications, statistical foundations, 0-D homology for hierarchical clustering, and extensions to other generalized persistence settings [28].The authors frame practical computational tools for multidimensional persistence as a promising direction for TDA with room for diverse approaches.Source: §10 · p. 67

A.1 Details of the RIVET Interface

• RIVET accepts M as a free implicit representation and uses gr1 and gr2 to determine interface bounds from their combined image.Source: §A.1 · p. 68
• The Line Selection Window spans the greatest lower bound A to the least upper bound B, with optional normalization that displays it as a square.Source: §A.1 · p. 68
• For each slice line L, RIVET plots B(M_L) using a unique order-preserving isometry, with origins fixed according to positive slope, vertical, or horizontal line cases.Source: §A.1 · p. 68
• The appendix notes that extrinsic image-based bounds are chosen for intuitive scale, although intrinsic bounds based on nonzero graded components are also possible.Source: §A.1 · p. 68
• The Persistence Diagram Window is statically set to [0, |B|] × [0, |B|], independently of the selected line L.Source: §A.1 · p. 69
• RIVET records persistence intervals outside the main diagram region using “inf” and “< inf” strips plus counts for points beyond the visible bounds.This handles intervals whose coordinates can become huge but finite as the slice slope approaches 0 or ∞.Source: §A.1 · p. 69
• When the Line Selection Window is normalized, RIVET applies corresponding affine normalizations so that A = (0, 0) and B = (1, 1), then recomputes lines and diagram bounds accordingly.Source: §A.1 · p. 69

Algorithm

• After sorting gr_1 and gr_2 into increasing colexicographical order when necessary, the algorithm scans grid rows from top to bottom and maintains Frontier with strictly decreasing x- and y-coordinates.The required sorting costs O(m log m).Source: §A.2 · pp. 69–70
• For each grade in a scanned row, the algorithm assigns its index to levSet_j(u) using the leftmost frontier element whose column bounds contain the grade, preserving lexicographical list order.This assignment yields u = lift_0 ◦ gr_j(k), so levSet_j(u) = (lift_0 ◦ gr_j)^−1(u).Source: §A.2 · p. 70

Complexity

• The frontier-sweep algorithm runs in O(m log m + n_yκ_x) = O(m log m + mκ) time, including sorting and list insertions.Frontier updates cost O(n_y), frontier scans cost O(n_yκ_x), and inserting all elements costs O(m).Source: §A.2 · p. 70

• A(M) is the line arrangement of M, A•(M) its augmented arrangement, and e denotes a cell in A(M).Source: Notation Index · p. 74
• M denotes a multidimensional persistence module, while B(M) denotes either a 1-D barcode or the fibered barcode of a 2-D persistence module.Source: Notation Index · p. 74
• The index also defines computational and structural notation, including κ for module coarseness, G for the dual graph or n-D grid function, and S for the union of supports of M’s 0th and 1st bigraded Betti numbers.Source: Notation Index · pp. 74–75
• L, L̄, and L° denote affine-line spaces in R2 with respectively non-negative finite, non-negative, and finite positive slopes.Source: Notation Index · p. 74
• T_e is the barcode template at cell e, while P and P_e are the sets of all template points and those at cell e.Source: Notation Index · pp. 74–75