PaperlayerView exact revision on arXiv

Source-linked AI summary

Interactive Visualization of 2-D Persistence Modules

Michael Lesnick, Matthew Wright

arXiv:1512.00180v1math.ATcs.CGmath.AC

TL;DR

Multidimensional persistence lacks practical exploratory-analysis software, while its invariants are substantially more complex than in one dimension. The paper introduces RIVET and an augmented-arrangement framework for interactively visualizing 2-D persistence modules and querying slice barcodes efficiently. Preliminary results indicate that the implementation already scales to bifiltrations with millions of simplices, although the method remains restricted to the 2-D case and uses a line-arrangement algorithm with a removable logarithmic factor.

  • Problem

    Multidimensional persistence provides richer but more complex invariants, and practical software extending the standard exploratory pipeline was lacking.

  • Method

    RIVET combines interactive visualizations of slice barcodes, dimension functions, and bigraded Betti numbers with an augmented arrangement supporting fast barcode queries.

  • Results

    The current implementation already scales well enough to study bifiltrations with millions of simplices in preliminary timing experiments.

  • Takeaways & Limitations

    RIVET provides a practical framework for exploratory visualization of 2-D persistence modules and supports a broader program of computational tools for multidimensional persistence.

  • Takeaways & Limitations

    The paper restricts attention to 2-D persistence, and its line-arrangement construction uses Bentley–Ottmann despite asymptotically faster alternatives that remove the log κ factor.

Abstract

from arXiv · show

The goal of this work is to extend the standard persistent homology pipeline for exploratory data analysis to the 2-D persistence setting, in a practical, computationally efficient way. To this end, we introduce RIVET, a software tool for the visualization of 2-D persistence modules, and present mathematical foundations for this tool. RIVET provides an interactive visualization of the barcodes of 1-D affine slices of a 2-D persistence module $M$. It also computes and visualizes the dimension of each vector space in $M$ and the bigraded Betti numbers of $M$. At the heart of our computational approach is a novel data structure based on planar line arrangements, on which we can perform fast queries to find the barcode of any slice of $M$. We present an efficient algorithm for constructing this data structure and establish bounds on its complexity.

1 Introduction

RIVET addresses the lack of practical multidimensional-persistence software by interactively visualizing complementary invariants of 2-D persistence modules. Its augmented-arrangement framework supports efficient barcode queries, with stated bounds for construction, storage, and querying.

  • Motivation: No publicly available software previously extended the standard exploratory persistent-homology pipeline to multidimensional persistence.
  • Contribution: RIVET addresses this gap with an interactive tool and mathematical and algorithmic foundations for exploratory analysis of 2-D persistence.
  • Visualization paradigm: RIVET visualizes the dimension function, fibered barcodes of 1-D affine slices, and multigraded Betti numbers of a 2-D persistence module.
  • Visualization paradigm: The fibered barcode complements global dimension and Betti-number views with a sharper, more local view of module structure.
  • Computational framework: The augmented arrangement enables fast recovery of B(M_L) for arbitrary affine slices by querying a data structure built from a planar line arrangement.
  • Complexity results: O(log κ + |B(M_L)|) query time is achieved for lines in arrangement 2-cells, with analogous perturbed-line bounds for other lines.

2 Algebra Preliminaries

This section develops the module-theoretic framework for persistence modules, including graded modules, presentations, Betti numbers, and discrete-grid representations. It establishes that finitely presented modules admit minimal presentations and continuous extensions from finitely generated discrete modules.

  • Foundations: Persistence modules are identified with R^n-graded modules over a ring whose monomial exponents range over [0,∞).The grading decomposes the underlying vector space, and multiplication shifts grades by vectors in [0,∞)^n.
  • Presentations: Presentations represent an n-module as a quotient of a free module by a homogeneous generated submodule.Finite sets of generators and relations define finitely presented persistence modules.
  • Invariants: The rank invariant does not completely determine a persistence module’s isomorphism type.Two modules can have equal rank invariants but induced maps with different ranks.
  • Presentations: Minimal presentations characterize minimal generators for both the module and its relation submodule, and every finitely presented module has one.Proposition 2.3 gives the characterization, while Remark 2.4 states existence.
  • Invariants: Betti numbers record graded algebraic information, with ξ0(M) and ξ1(M) sufficient for the augmented-arrangement and fibered-barcode constructions.The dimension function separately records dim(M_a) at each grade.
  • Discrete representations: Any finitely presented n-module is a continuous extension of a finitely generated discrete persistence module along some n-D grid.A grid containing the supports of ξ0(M) and ξ1(M) yields such a representation, preserving presentation size.

3 Augmented Arrangements of 2-D Persistence Modules

This section constructs the augmented arrangement A•(M) for a finitely presented 2-D persistence module. The arrangement partitions line parameters into cells with stable ordered point partitions and barcode templates, enabling fibered-barcode queries.

  • Construction: The augmented arrangement A•(M) consists of the line arrangement A(M) together with a barcode template T_e attached to every 2-cell e.The construction first defines A(M), characterizes its 1-skeleton, and then defines the templates.
  • Point-line duality: Point-line duality identifies nonvertical affine lines with [0,∞)×R via y=ax+b ↦ (a,−b) and (c,d) ↦ y=cx−d.The duality preserves incidence but does not naturally include vertical lines.
  • Arrangement: The arrangement is determined by anchors, which are least upper bounds of weakly incomparable support points, and its 1-skeleton comprises dual lines through anchors plus x=0.Weak incomparability includes incomparability or sharing one coordinate.
  • Complexity: κ lines and at most κ^2 vertices, edges, and faces bound the size of A(M), where κ is the product of the numbers of unique x- and y-coordinates in S.Here S=supp ξ0(M)∪supp ξ1(M).
  • Push maps and critical lines: For a line L, the push map sends each point to the least point of L above or rightward from it, inducing a totally ordered partition S_L of S.For positive finite slope, pushed points lie on a horizontal or vertical alignment with the original point.
  • Push maps and critical lines: Theorem 3.3 identifies the 1-skeleton with critical lines, where the push-order partition changes under arbitrarily small perturbations.Lines through anchors are critical because perturbations reverse the order of pushed weakly incomparable points; partitions are constant within each 2-cell.
  • Barcode templates: The augmented arrangement is completely determined by the fibered barcode B(M) and S, and conversely it determines B(M).The barcode templates stored in cells provide the additional data needed for this correspondence.

4 Querying the Augmented Arrangement

The augmented arrangement encodes the barcode of every affine slice by selecting an appropriate 2-cell and pushing template endpoints onto the slice. This yields a query procedure with logarithmic cell-location overhead and output-sensitive barcode construction.

  • 4.1 Selecting a 2-D Coface e of L: For generic, horizontal, and vertical lines, Section 4.1 specifies a 2-cell coface using arrangement containment or boundary conventions.Generic lines use a cell whose closure contains the dual point; horizontal and vertical lines use designated bottom or above-cell rules.
  • 4.2 The Query Theorem: Theorem 4.1 recovers B(M_L) by pushing each pair in the selected cell’s template T_e onto L and retaining nondegenerate intervals.The selected cell depends on L, and intervals with equal pushed endpoints are omitted.
  • 4.3 Computational Details of Queries: The arrangement is stored as a DCEL containing vertices, edges, and 2-cells, with each 2-cell storing its barcode template as a multiplicity-aware list.A template pair (a,b) can occur multiple times and is stored with multiplicity k.
  • 4.3 Computational Details of Queries: A query first locates the prescribed 2-cell and then applies push_L to every template pair.For nonvertical lines this uses point location for the dual point; vertical lines use a separate slope-sorted search structure.
  • 4.3 Computational Details of Queries: O(|T_e| + log κ) is the total query time after preprocessing, with O(log κ) cell location and constant-time endpoint pushing.When the dual point lies in e, |T_e| equals |B(M_L)|; otherwise it equals the barcode size for an arbitrarily small perturbation L′.

5 Computing the Arrangement A(M)

The arrangement computation accepts free implicit representations of persistence modules, including those arising from finite bifiltrations. It computes Betti-number support data and uses it to construct the line arrangement, with algebraic computation available in O(m^3) time for the discrete case.

  • 5 Computing the Arrangement A(M): An FI-representation Φ=(gr1, gr2, D1, D2) specifies graded sets and matrices whose homology realizes the persistence module M.The matrices represent consecutive maps satisfying ∂1∘∂2=0, with M isomorphic to ker ∂1 / im ∂2.
  • 5 Computing the Arrangement A(M): The algorithm takes an FI-representation of M as input, matching the representation typically available for persistent homology modules of bifiltrations.Direct presentations are generally unavailable initially and can be computationally expensive to obtain.
  • 5 Computing the Arrangement A(M): 1-critical filtrations yield free chain modules, while multi-critical filtrations require a generalized FI-representation construction.Finite bifiltrations can produce these representations in O(l log l) time from a simplicial complex and grades of appearance.
  • 5 Computing the Arrangement A(M): The implementation computes the augmented arrangement for one homology index at a time, while 1-critical bifiltrations can also support all indices in one pass.The single-index approach saves effort when only one module is needed and is suited to multi-critical filtrations.
  • 5 Computing the Arrangement A(M): O(m^3) is the runtime for fully computing ξ0(Q), ξ1(Q), and ξ2(Q) from an FI-representation of a Z^2-indexed module.The algorithm uses scheduled column reductions based on homology of Koszul complexes rather than computing an entire free resolution.
  • 5 Computing the Arrangement A(M): Bentley–Ottmann contributes the κ^2 log κ term to the construction bound, although asymptotically faster arrangement algorithms can remove the logarithmic factor.The paper retains Bentley–Ottmann because it is relatively simple and performs well in practice.

6 Computing the Barcode Templates

Barcode templates are computed from a trimmed FI-representation using standard persistence reductions and incremental updates across adjacent arrangement cells. The algorithm combines RU-decompositions, sorting, and vineyard updates to avoid recomputing every cell independently.

  • 6 Computing the Barcode Templates: The template-computation input comprises an FI-representation, a sparse matrix of template points, and a DCEL for the line arrangement.The FI-representation, template-point matrix, and arrangement are computed or stored before template construction begins.
  • 6.1 Trimming the Free Implicit Representation: Trimming replaces an untrimmed FI-representation with a smaller equivalent one and can be computed in O(m + d) time, where d=O(m^2) nonzero entries are in D2.The trimmed representation preserves the module while simplifying subsequent computation.
  • 6.2 RU-Decompositions and Computation of Persistence Barcodes: The standard persistence algorithm computes D=RU, with R reduced and U upper triangular, in O(rs^2) time for an r×s matrix.Barcode intervals are read from the paired RU-decompositions of D1 and D2.
  • 6.2 RU-Decompositions and Computation of Persistence Barcodes: Pairs(Φ) and Ess(Φ) determine the barcode and are independent of the chosen RU-decomposition, despite the decomposition itself being non-unique.This makes the barcode data well-defined even when multiple valid reductions exist.
  • 6.2 RU-Decompositions and Computation of Persistence Barcodes: Adjacent row or column transpositions update an RU-decomposition in O(d1+d2) time through the vineyard algorithm.These updates are the essential subroutine for transferring barcode computations between neighboring arrangement cells.
  • 6.3 Permutations of Free Implicit Representations: Permutations sort the grade functions into non-decreasing order while applying corresponding row and column permutations to the matrices.Insertion sort supplies a minimum-length sequence of adjacent transpositions for these permutations.

6.4 Induced Free Implicit Representations at Each 2-Cell

Each arrangement cell induces a reordered FI-representation of the corresponding discrete slice module. Templates are computed while traversing the arrangement’s dual graph, updating lift maps, permutations, and RU-decompositions incrementally.

  • 6.4 Induced Free Implicit Representations at Each 2-Cell: For each 2-cell e, the original FI-representation induces a FI-representation Φ_e of the discrete module M_e with non-decreasing graded functions.The induced representation is obtained by lifting grades and applying valid permutations to the matrices.
  • 6.4 Induced Free Implicit Representations at Each 2-Cell: The lift map sends each point to the minimum template point above it, and adjacent cells can have different lift maps on shaded regions.This local change explains why neighboring cells may require updates to their induced representations.
  • 6.4 Induced Free Implicit Representations at Each 2-Cell: A valid cell-specific permutation need not be unique, but the resulting template map is independent of that choice.The algorithm may therefore choose any valid permutation while preserving the template map.
  • 6.4 Induced Free Implicit Representations at Each 2-Cell: The barcode template T_e is obtained from the template map and an RU-decomposition of Φ_e for any valid cell-specific permutation.This relationship is the computational basis for constructing templates at every 2-cell.
  • 6.4 Induced Free Implicit Representations at Each 2-Cell: Neighboring-cell computation updates lift-composed grades, sorting permutations, and RU-decompositions rather than restarting from scratch.Vineyard RU-updates are applied repeatedly along adjacent transpositions generated by insertion sort.
  • 6.4 Induced Free Implicit Representations at Each 2-Cell: The dual graph G has one vertex per 2-cell and one edge per adjacent-cell pair; the algorithm traverses a path Γ visiting every 2-cell at least once.The path provides the order in which cell-specific template maps and decompositions are computed.

6.6 Computing the Path Γ

The algorithm chooses a traversal path through the line arrangement’s cells using estimated update costs, then initializes data structures and decompositions at the starting cell.

  • Choosing Γ: Edge weights estimate the work required to move between adjacent cells, influencing the chosen path but not the asymptotic complexity bounds.The weights are computed from expected insertion-sort transpositions and RU-decomposition updates.
  • Choosing Γ: Because finding a minimum-length valid path is expected to be NP-hard, the algorithm computes an approximately minimum path instead.A valid path starts at e0 and visits every vertex of the dual graph.
  • Choosing Γ: A minimum spanning tree followed by depth-first search yields a valid path of length at most twice the minimum valid-path length.The path traverses each spanning-tree edge at most twice.
  • Initialization at e0: At the initial cell e0, the algorithm initializes levSetj lists, concatenates them by y-coordinate, constructs permutation arrays, and computes the RU-decompositions.The lists support later updates as the algorithm traverses the arrangement.
  • Initialization at e0: The levSetj lists can be initialized by an O(m log m + mκ)-time sweep, after which the resulting arrays support constant-time template-map evaluations.The representation combines liftsj and sigj with the RU-decomposition to read barcode templates.

6.9 Computations at Cell ei, for i ≥1

As the traversal crosses arrangement cells, the algorithm updates lift assignments and permutations locally, using insertion-sort transpositions and corresponding vineyard updates to maintain barcode templates.

  • Cell updates: The update interleaves changes to lift assignments, insertion-sort transpositions, and RU-decomposition updates rather than performing these stages separately.This ordering is slightly more efficient than first updating all lift maps and then sorting.
  • Cell updates: When crossing a boundary with anchor α, elements in levSetj(α) move to levSetj(v) when their grade’s y-coordinate is at most v2.Elements above v2 retain lift α and may trigger a sortOneElement update.
  • Cell updates: sortOneElement restores the ordering of sigj and sigInvj after an adjacent transposition and applies the corresponding RU-decomposition update.Its input assumes the ordering is already valid after position w.
  • Switches and separations: Switching pairs are incomparable, and pairs can switch at the same anchor line independently of which adjacent cells on that line are crossed.Separations likewise depend only on the anchor line.
  • Switches and separations: The edge-weight estimate counts switching pairs and weights separating pairs by roughly one quarter because separations trigger transpositions only in some crossings.The quantities swL and sepL count unordered switching and separating pairs along anchor line L.
  • Weight computation: All edge weights are computed by traversing a path that crosses each anchor line once and running a simplified barcode-template algorithm.Only elements in the relevant levSet lists need to be considered for each anchor line.

7 Cost of Computing and Storing the Augmented Arrangement

The paper bounds the size, storage, and computational cost of the augmented arrangement in terms of representation size m and module coarseness κ, with vineyard updates dominating the runtime.

  • Complexity bounds: O(m^3κ + mκ^2 log κ) elementary operations and O(m^2 + mκ^2) storage suffice to compute the augmented arrangement.These are the algebraic-input bounds stated in Proposition 7.1.
  • Size and storage: The arrangement has O(κ^2) cells, while storing all barcode templates contributes O(mκ^2) total size.Each one-dimensional barcode has at most m1 intervals, so each cell’s template has size at most m1.
  • Runtime analysis: The algorithm performs O(m^2κ) insertion-sort transpositions across all barcode-template computations.This bound controls the costs of updating the permutation arrays.
  • Runtime analysis: O(m^3κ) time is required for vineyard updates because each transposition invokes the vineyard algorithm at most twice at O(m) cost.The analysis also accounts for O(κ^2) cells.
  • Runtime analysis: Computing all edge weights takes O(m^2 + mκ) time using a stripped-down version of the barcode-template algorithm.The weight computation relies on the bound in Lemma 7.5.
  • Transposition analysis: For each pair of points, there is at most one switching anchor line and at most two separating anchor lines, yielding the transposition bound.If a pair switches, it does not separate at any anchor line.

8 Speeding up the Computation of the Augmented Arrangement

The paper accelerates augmented-arrangement computation through adaptive choices among recomputation and vineyard updates, combinatorial optimization, and module coarsening.

  • Practical accelerations: Practical strategies allow augmented arrangements for substantially larger datasets than would otherwise be possible.The strategies target runtime bottlenecks in barcode-template computation.
  • Adaptive template computation: At each cell, the algorithm chooses among a fast update, full recomputation, and vineyard updates, balancing speed against future update options.Choosing the fastest local option can prevent vineyard updates at the next cell.
  • Avoiding unnecessary computation: Avoiding full RU-decompositions can provide additional speedups because only persistent pairs and essential entries are needed for the next template.This permits use of faster persistence algorithms that compute PE(Φ) without the full RU-decomposition.
  • Adaptive template computation: The resulting discrete optimization problem can be solved efficiently by reducing it to a minimum-cut problem in a flow network.The reduction proceeds through a bipartite maximum-weight independent-set and minimum-cost vertex-cover formulation.
  • Adaptive template computation: Runtime estimates are updated in stages using measured costs from earlier cells before optimizing the remaining path.The path is processed in successive blocks until the estimates stabilize.
  • Coarsening: Coarsening the module reduces computational size, and coordinate changes bounded by δ guarantee interleaving distance at most δ.The grid controls module coarseness while preserving this explicit approximation bound.

9 Preliminary Runtime Results

Preliminary experiments measure runtimes for graded Betti numbers and augmented arrangements on noisy-circle bifiltrations. The implementation is preliminary, but the reported results scale to data with millions of simplices.

  • Implementation caveats: The implementation omits several optimizations, including an efficient barcode-template scheme, better sparse-matrix column storage, and parallel processing.The reported code uses a simplified edge-crossing scheme, linked-list columns, and a single processing core.
  • Observed scalability: Despite these limitations, the current implementation scales sufficiently to study bifiltrations with millions of simplices.The authors expect further speedups from the proposed implementation improvements.
  • Computational setting: The computations ran on a single 800 MHz core, with approximately 9.3 GB of RAM required for the largest computation.The experiments used a 32-core server with 96 GB of RAM, although only one slow core was used.
  • Data construction: The noisy-circle data consist of point clouds with 90% of points sampled from a thick annulus and 10% from a containing square.A codensity function is used to construct the Vietoris–Rips bifiltration.
  • Runtime measurements: The experiments report average runtimes for computing bigraded Betti numbers and building augmented arrangements from noisy-circle data.Tables 3–5 cover Betti-number computations and arrangements for 0th- and 1st-homology modules.

10 Conclusion

The paper concludes by introducing RIVET as a practical framework for visualizing 2-D persistence and by presenting its augmented-arrangement foundations. Preliminary experiments indicate scalability to bifiltrations with millions of simplices, while several implementation improvements remain.

  • 10 Conclusion: RIVET visualizes affine-slice barcodes, the dimension function, and bigraded Betti numbers of 2-D persistence modules.Its mathematical theory centers on the augmented arrangement data structure.
  • 10 Conclusion: The paper introduces an augmented arrangement, analyzes an algorithm for computing it, and describes strategies for improving its practical runtime.These contributions provide the computational framework underlying the visualization paradigm.
  • 10 Conclusion: The current implementation scales sufficiently to study bifiltrations with millions of simplices, despite not yet incorporating several key optimizations.The authors expect further implementation work to broaden its usable settings.
  • 10 Conclusion: Future work includes applying RIVET to scientific data, developing statistical foundations, and extending the paradigm to clustering and generalized persistence settings.The listed directions include bidendrogram visualization and cosheaves over R2 or R.
  • 10 Conclusion: The authors frame practical computational tools for multidimensional persistence as a promising direction with room for diverse approaches.This broader program is presented independently of RIVET’s eventual usefulness.

A.1 Details of the RIVET Interface

The RIVET interface defines how persistence slices are selected, parameterized, and displayed. It also handles normalization and intervals extending beyond the main persistence-diagram viewing region.

  • Interface bounds: RIVET receives the module as a free implicit representation and uses grading maps to determine interface bounds.The bounds derive from the greatest lower and least upper bounds of the grading-map images.
  • Interface bounds: The Line Selection Window spans the selected lower-left and upper-right bounds and can be toggled between scale-preserving and square-normalized views.The default display is drawn to scale.
  • Barcode display: For each selected line, RIVET uses a unique order-preserving isometry to parameterize the line before plotting its barcode as a persistence diagram.The parameterization anchors finite-positive-slope lines at the nonnegative coordinate axes and fixes coordinate lines at specified intercepts.
  • Barcode display: The persistence-diagram window is statically set to [0, |B|] × [0, |B|], independently of the selected line.Normalization correspondingly maps the chosen bounds to (0, 0) and (1, 1).
  • Overflow representation: Intervals extending beyond the main diagram region are represented in “inf” and “< inf” strips, with additional counts for points beyond the horizontal range.This preserves information when persistence coordinates become very large as line slopes approach 0 or infinity.

A.2 Computing the Lists levSetj(u) at Cell e0

A frontier-sweep algorithm constructs the lists levSetj(u) by scanning grid rows, maintaining a monotone frontier, and assigning grades to appropriate frontier entries. Its runtime is governed by grid height and frontier length.

  • A.2 Computing the Lists levSetj(u) at Cell e0: The sweep assumes grading maps are increasing in colexicographical order, applying sorting first when necessary.This assumption provides immediate access to entries with a given grade.
  • A.2 Computing the Lists levSetj(u) at Cell e0: The algorithm scans grid rows from top to bottom while maintaining a linked-list frontier whose x- and y-coordinates strictly decrease.The frontier stores pointers to entries in the point matrix.
  • A.2 Computing the Lists levSetj(u) at Cell e0: At each nonempty row, the sweep replaces the frontier’s last entry when columns coincide; otherwise, it appends the row’s rightmost point.It then traverses the frontier to locate insertion lists.
  • A.2 Computing the Lists levSetj(u) at Cell e0: Each grade k is inserted into levSetj(u) for the leftmost frontier element satisfying r ≤ u1, and each list remains lexicographically sorted.The selected frontier element equals lift0 ◦ grj(k), as required.
  • A.2 Computing the Lists levSetj(u) at Cell e0: The frontier-update cost is O(ny), while scanning frontier entries costs O(nyκx).The total runtime also includes constant-time insertion for each k ∈ [mj].

Notation Index

The notation index defines the paper’s core objects for multidimensional persistence, affine-line slices, barcodes, and the line-arrangement data structure. It also records auxiliary maps, functions, categories, and representation conventions used throughout the paper.

  • Line-arrangement structure: A(M) is the line arrangement, with e denoting a cell and A•(M) its augmented arrangement.
  • Auxiliary notation: Auxiliary notation includes G for an n-D grid function, G for the dual graph of A(M), grW for a grade function, and flG for a floor function.
  • Auxiliary notation: The index also specifies persistence-related functions, categories, sets, and conventions, including Hi, rank(M), κ, p.f.d., FI-rep, Zn, Rn, and [k].
  • Affine-line spaces: L and ¯L describe affine lines in R2 with non-negative slope, while L◦ restricts to finite, positive slope.
  • Core persistence objects: M denotes a multidimensional persistence module, while B(M) denotes a 1-D barcode or the fibered barcode of a 2-D module.
  • Templates and maps: The index defines T e as a barcode template at cell e and f e as the template map, alongside template-point sets P and Pe.
Loading 1512.00180v1…