Pruning vineyards: Updating barcodes and representative cycles by removing simplices

Barbara Giunti; Jānis Lazovskis

doi:10.3934/fods.2026007

Article Contents

2026. Doi: 10.3934/fods.2026007

Previous Article Next Article

Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

Pruning vineyards: Updating barcodes and representative cycles by removing simplices

Barbara Giunti^{1, 2, ,} and
Jānis Lazovskis^{3, 4,}

1.
Graz University of Technology, Austria
2.
SUNY - University at Albany, NY, USA
3.
University of Latvia, Riga, Latvia
4.
University of Aberdeen, Scotland, United Kingdom

^*Corresponding author: Barbara Giunti
^*Corresponding author: Barbara Giunti

Received: May 29, 2025

Revised: January 26, 2026

Early access: March 23, 2026

Published online: March 23, 2026

The first author was partially supported by Austrian Science Fund (FWF) P 33765-N. The second author was supported by the EPSRC grant EP/P025072/1, and the Latvian Council of Science No 1.1.1.9/LZP/1/24/125.

Abstract / Introduction Full Text(HTML) Figure(8) / Table(3) Related Papers Cited by

Abstract

The barcode of a filtration and its representative cycles encode rich information often useful in data analysis. However, obtaining them can be computationally expensive. Therefore, it is useful to have methods that update them if the associated filtration undergoes small changes. There are already efficient algorithms updating a barcode if simplices exchange entrance order or are added, but not if simplices are removed. We provide an implementation to update a reduced boundary matrix when simplices in the filtration are removed. Our algorithm, the Simplicial Removal Update Procedure (SiRUP), intrinsically updates also the representative cycles, and is compatible with the clearing optimizations. We show that the complexity of our algorithm is lower than recomputing the barcode from scratch and that the number of executed matrix column additions is minimal, with both theoretical and experimental methods.

Keywords:

Mathematics Subject Classification: Primary: 55N31, 68T09, 68Q25, 15-04.

Citation:

FullText(HTML)

Figure 1. A filtered simplicial complex $ K $ (left) with its simplices indexed by entrance time, its unreduced, total boundary matrix (middle), and its barcode (right), constructed from the pivot indices of the reduced boundary matrix. In the barcode, dimension 0 bars are below the dashed line, and dimension 1 bars are above it

Download: Full-size image PowerPoint slide

Figure 2. A simplicial complex (left), the sub-matrix of its boundary matrix given by the edges and their boundaries (a), the formal sums $ e_2+e_3 $ (dashed) and $ e_1+e_2+e_3 $ (dashed and solid), (b) and (c) respectively

Download: Full-size image PowerPoint slide

Figure 3. Comparison from Example 3.1 of the matrices $ R $ (left side) and $ V $ (right side) in Naive removal (left column) and in SiRUP (right column). The label Column x means that the algorithm is processing the $ x $th column, and the arrows show column addition. Pivots in $ B $ for SiRUP are emphasized

Download: Full-size image PowerPoint slide

Figure 4. A filtered simplicial complex $ K $ and its unreduced boundary matrix $ D $ (left), factored as $ R = DV $ by SBA (right, top), and the outputs $ R_c,V_c $ with clearing (right, bottom). Clearing puts column $ i = 5 $ of the boundary matrix $ R_c $ to zero if and only if there is a pivot pairing $ (i,j) = (5,6) $. That is, if the formal sum corresponding to column $ j = 6 $ kills the homological class generated by simplex corresponding to row $ i = 5 $

Download: Full-size image PowerPoint slide

Figure 5. Examples of how the barcode may change when the star of a simplex (highlighted in red) is removed from different 2-dimensional simplicial complexes. Finite bars (one in dimension $ 0 $ and several in dimension $ 1 $) disappear and an infinite bar in dimension $ 1 $ appears in (a), a finite bar becomes shorter and another finite bar disappears in (b), $ 4 $ infinite bars in dimension $ 1 $ appear in (c), and an infinite bar disappears in (d). Filtrations respect dimension, with all 0-simplices appearing before any 1-simplex, and all 1-simplices appearing before any 2-simplex

Download: Full-size image PowerPoint slide

Figure 6. A filtered simplicial complex (left), drawn without its 1-simplex $ e_4 $. Three possible matrices $ V_i $ (right) for three different choices of $ e_4 $, with $ \left[\begin{array}{ll}0 & R \\ 0 & 0 \end{array}\right]=D_i\left[\begin{array}{ll} I & 0 \\ 0 & V_i \end{array}\right] $ always being satisfied, for $ D_i $ the appropriate boundary matrix in each case. The removal of either $ e_1 $ or $ e_3 $ will not produce the same updated barcode for all three choices of $ e_4 $

Download: Full-size image PowerPoint slide

Figure 7. A visual overview of our main testing results. The plots are colored semi-transparently to distinguish the cases when there is little difference between the $ \texttt{--standard}$ and $\texttt{--twist} $ methods. File sizes of boundary and operations matrices are also compared (right), highlighting the tradeoff in time for space for SiRUP. The full details of the left and center plots are given in Table 3. Raw data for all three plots is given in the related dataset [22]

Download: Full-size image PowerPoint slide

Figure 8. Steps and outputs of full testing environment. The values reported in Table 3 are from execution of SiRUP and PHAT-op in the "Testing" stage (right)

Download: Full-size image PowerPoint slide

Table 1. Descriptive overview of input datasets, with the number of simplices by dimension, and sources for sampling and construction indicated. The filtrations on each dataset that result in the complexes with the given numbers of simplices are described in Table 2

Dataset	0-$ \dim $	1-$ \dim $	2-$ \dim $	3-$ \dim $	4-$ \dim $	Source
$\texttt{vr_dsphere}$	3 000	65 052	400 187	1 224 795	2 353 767	[45,32]
$\texttt{vr_torus}$	1 000	21 988	214 105	1 415 261	7 288 105	[45,32]
$\texttt{vr_senate}$	103	5 253	176 851	4 421 275	0	[39,32]
$\texttt{er_clique}$	100	4 463	118 583	2 111 092	0	[25,32]
$\texttt{er_shuffled}$	100	3 005	36 126	194 908	0	[25,32]
$\texttt{alpha_cube}$	10 000	76 644	133 170	66 525	0	[45,5]
$\texttt{alpha_swissroll}$	100 000	1 043 027	1 829 784	886 756	0	[45,5]
$\texttt{cc_tooth}$	1 558 802	4 635 007	4 593 966	1 517 760	0	[29,5]
$\texttt{bio_bbmcl6}$	3 174	180 032	529 470	157 900	0	[44,32]

| Show Table

DownLoad: CSV

Table 2. Details of filtrations on input datasets

Dataset	Filtration	Description
$\texttt{vr_dsphere}$ $\texttt{vr_torus}$ $\texttt{vr_senate}$	Vietoris–Rips	Random samples over a unit 4-sphere in $ \mathbb{R}^6 $, random samples over a 2-torus with major radius 2 and minor radius 1 in $ \mathbb{R}^4 $, and a legislator voting dataset (distances among 103 points) from [39]. Both random samples have normally distributed noise at standard deviation $ 0.2 $. Only edges less than 0.6 are considered for $ \texttt{vr_dsphere}$, and less than 1 for $ \texttt{vr_torus}$. All edges are considered for $ \texttt{vr_senate}$.
$\texttt{er_clique}$ $\texttt{er_shuffled}$	random, clique	Random values in $ [0,1] $ assigned to $ \binom{100}{2} $ edges, included from highest to lowest "probability, " with higher dimensional simplices defined by the clique complex. For $\texttt{er_clique} $, a $ (d>1) $-simplex is ordered immediately after all its faces. For $ \texttt{er_shuffled}$, the order of every $ (d>1) $-simplex is included in a random order after all its faces have been included. Probability at least $ 0.1 $ considered for $ \texttt{er_clique}$ and at least $ 0.5 $ for $\texttt{er_shuffled} $.
$\texttt{alpha_cube}$ $\texttt{alpha_swissroll}$	alpha	Random samples of 10 000 and 100 000 points over a cube and swiss, respectively, generated with [45].
$\texttt{cc_tooth}$	lowerstar, clique	A 3D image of a tooth from [29], represented as a $ 104\times 91 \times 161 $ array of values in $ [0,255] $. This defines a filtration of a cubical complex in 3 dimensions.
$\texttt{bio_bbmcl6}$	biological, clique	Biologically motivated reconstruction of a rat's neocortex [34], with neurons as vertices, synapses as edges, and their clique complex defining higher dimensional simplices. Restricted to the undirected excitatory subcircuit of bipolar pyramidal cells in Layer 6 (≈ 10% of all the neurons).

| Show Table

DownLoad: CSV

Table 3. Experiments comparison between SiRUP, PHAT-op, and PHAT, indicating the number of simplices removed (in parentheses in increasing dimension) from each filtration. Number of column additions (in millions "M" for PHAT-op and PHAT) and computations time (in seconds, excluding file reading and writing) are given for the standard reduction method and with the twist optimization [9], abbreviated $ \texttt{std}$ and $ \texttt{twi}$, respectively. The best results are indicated in bold. A visual representation of the testing process and results is given in Figure 8

		Number of column additions
Dataset	Simplices removed	SiRUP		PHAT-op (M)		PHAT (M)
		$\texttt{std}$	$\texttt{twi}$	$\texttt{std}$	$\texttt{twi}$	$\texttt{std}$	$\texttt{twi}$
$\texttt{vr_dsphere}$	183 (0, 1, 15, 59,108)	$\textbf{2640}$	$\textbf{2508}$	89.8	42.3	44.9	20.5
$\texttt{vr_torus}$	5 (0, 0, 0, 0, 5)	$\textbf{28}$	$\textbf{28}$	195.8	158.9	97.9	78.7
$\texttt{vr_senate}$	20 (0, 0, 0, 20)	$\textbf{990}$	$\textbf{990}$	63.6	60.4	31.8	30.1
$\texttt{er_clique}$	3 (0, 0, 0, 3)	$\textbf{0}$	$\textbf{0}$	1150.0	1141.6	576.8	570.8
$\texttt{er_shuffled}$	25 (0, 0, 1, 24)	$\textbf{7268}$	$\textbf{7278}$	225.1	222.7	112.6	111.3
$\texttt{alpha_cube}$	5 (0, 0, 0, 5)	$\textbf{4}$	$\textbf{4}$	3.3	0.3	1.7	0.1
$\texttt{alpha_swissroll}$	9 (0, 1, 4, 4)	$\textbf{14}$	$\textbf{18}$	195.3	2.7	97.6	0.4
$\texttt{cc_tooth}$	27 (1, 6, 12, 8)	$\textbf{1228}$	$\textbf{138}$	344.9	15.9	172.4	4.9
$\texttt{bio_bbmcl6}$	8 (0, 1, 6, 1)	$\textbf{30}$	$\textbf{30}$	320.9	207.9	160.5	103.8

Dataset	Simplices removed	Number of column additions
		SiRUP		PHAT-op		PHAT
		$\texttt{std}$	$\texttt{twi}$	$\texttt{std}$	$\texttt{twi}$	$\texttt{std}$	$\texttt{twi}$
$\texttt{vr_dsphere}$	183 (0, 1, 15, 59,108)	$\textbf{13.7}$	11.9	37.5	21.8	17.6	$\textbf{10.2}$
$\texttt{vr_torus}$	5 (0, 0, 0, 0, 5)	$\textbf{6.0}$	$\textbf{6.6}$	70.4	66.7	36.3	33.2
$\texttt{vr_senate}$	20 (0, 0, 0, 20)	15.3	15.4	26.9	26.0	$\textbf{12.5}$	$\textbf{12.4}$
$\texttt{er_clique}$	3 (0, 0, 0, 3)	$\textbf{4.7}$	$\textbf{5.1}$	1196.3	1132.2	429.9	394.8
$\texttt{er_shuffled}$	25 (0, 0, 1, 24)	$\textbf{21.1}$	$\textbf{23.6}$	128.4	136.7	55.5	61.2
$\texttt{alpha_cube}$	5 (0, 0, 0, 5)	$\textbf{0.2}$	$\textbf{0.1}$	3.8	0.6	1.3	0.2
$\texttt{alpha_swissroll}$	9 (0, 1, 4, 4)	$\textbf{10.3}$	3.0	241.3	7.1	68.2	$\textbf{2.2}$
$\texttt{cc_tooth}$	27 (1, 6, 12, 8)	$\textbf{70.5}$	25.5	246.7	32.9	93.5	$\textbf{12.3}$
$\texttt{bio_bbmcl6}$	8 (0, 1, 6, 1)	$\textbf{11.0}$	$\textbf{6.3}$	303.7	155.7	77.9	42.7

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. Adams, A. Tausz and M. Vejdemo-Johansson, Javaplex: A research software package for persistent (co)homology, Mathematical Software–ICMS 2014, $\texttt8592$ (2014), 129-136. doi: 10.1007/978-3-662-44199-2_23.
[2]	M. Aggarwal and V. Periwal, Tight basis cycle representatives for persistent homology of large biological data sets, PLoS Comput Biol 19, (2023). doi: 10.1371/journal.pcbi.1010341.
[3]	U. Bauer, Ripser, https://github.com/Ripser/ripser.
[4]	U. Bauer, Ripser: Efficient computation of Vietoris–Rips persistence barcodes, Journal of Applied and Computational Topology, 5 (2021), 391-423. doi: 10.1007/s41468-021-00071-5.
[5]	U. Bauer, T. Bin Masood, B. Giunti, G. Houry, M. Kerber and A. Rathod, Keeping it sparse: Computing persistent homology revisited, Computing in Geometry and Topology, 3 (2024), 26.
[6]	U. Bauer, M. Kerber and J. Reininghaus, Clear and compress: Computing persistent homology in chunks, Topological Methods in Data Analysis and Visualization III, Theory, Algorithms, and Applications, Springer, (2014), 103-117.
[7]	U. Bauer, M. Kerber, J. Reininghaus and H. Wagner, Phat–persistent homology algorithms toolbox, Journal of Symbolic Computation, 78 (2017), 76-90. doi: 10.1016/j.jsc.2016.03.008.
[8]	A. Cerri, M. Ethier and P. Frosini, A study of monodromy in the computation of multidimensional persistence, Discrete Geometry for Computer Imagery, (2013), 192-202. doi: 10.1007/978-3-642-37067-0_17.
[9]	C. Chen and M. Kerber, Persistent homology computation with a twist, Proceedings 27th European Workshop on Computational Geometry, (2011).
[10]	D. Cohen-Steiner, H. Edelsbrunner and D. Morozov, Vines and vineyards by updating persistence in linear time, Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, Association for Computing Machinery, (2006), 119–126. doi: 10.1145/1137856.1137877.
[11]	G. Colombo, et al., A tool for mapping microglial morphology, morphomics, reveals brain-region and sex-dependent phenotypes, Nature Neuroscience, 25 (2022), 1379-1393. doi: 10.1038/s41593-022-01167-6.
[12]	P. Conceição, D. Govc, J. Lazovskis, R. Levi, H. Riihimäki and J. P. Smith, An application of neighbourhoods in digraphs to the classification of binary dynamics, Network Neuroscience, 6 (2022), 528-551. doi: 10.1162/netn_a_00228.
[13]	V. De Silva, D. Morozov and M. Vejdemo-Johansson, Dualities in persistent (co)homology, Inverse Problems, 27 (2011). doi: 10.1088/0266-5611/27/12/124003.
[14]	T. K. Dey and T. Hou, Computing zigzag vineyard efficiently including expansions and contractions, 40th International Symposium on Computational Geometry (SoCG 2024), 15 (2024). doi: 10.4230/LIPIcs.SoCG.2024.49.
[15]	T. K. Dey and T. Hou, Fast computation of zigzag persistence, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2024), 15. doi: 10.4230/LIPIcs.ESA.2022.43.
[16]	T. K. Dey and T. Hou, Updating barcodes and representatives for zigzag persistence, arXiv, 2022, arXiv:2112.02352.
[17]	T. K. Dey and Y. Wang, Computational Topology for Data Analysis, Cambridge University Press, 2022. doi: 10.1017/9781009099950.
[18]	H. Edelsbrunner, J. Harer, A. Mascarenhas and V. Pascucci, Time-varying reeb graphs for continuous space-time data, Proceedings of the Twentieth Annual Symposium on Computational Geometry, (2004), 366-372.
[19]	H. Edelsbrunner and J. L. Harer, Computational Topology: An Introduction, American Mathematical Society, Providence, RI, 2010. doi: 10.1090/mbk/069.
[20]	H. Edelsbrunner, D. Letscher and A. Zomorodian, Topological persistence and simplification, Proceedings 41st Annual Symposium on Foundations of Computer Science, (2000), 454-463. doi: 10.1109/SFCS.2000.892133.
[21]	B. Giunti, Notes on pivot pairings, Proceedings of the 37th European Workshop on Computational Geometry, (2021), 11.
[22]	B. Giunti and J. Lazovskis, Dataset for "Pruning Vineyards: Updating Barcodes and Representative Cycles by Removing Simplices", https://zenodo.org/records/15481043.
[23]	B. Giunti and J. Lazovskis, PHAT-vineyards, https://bitbucket.org/jlazovskis/phat-sirup, 2024.
[24]	B. Giunti, J. Lazovskis and B. Rieck, DONUT: Database of Original & Non-Theoretical Uses of Topology, https://donut.topology.rocks.
[25]	C. R. Harris, et al., Array programming with NumPy, Nature, 585 (2020), 357-362. doi: 10.1038/s41586-020-2649-2.
[26]	G. Henselman and R. Ghrist, Matroid filtrations and computational persistent homology, arXiv, arXiv:1606.00199.
[27]	A. Hickok, Persistence diagram bundles: A multidimensional generalization of vineyards, arXiv, arXiv:2210.05124.
[28]	W. Kim, F. Mémoli and Z. Smith, Analysis of dynamic graphs and dynamic metric spaces via zigzag persistence, Topological Data Analysis, Springer International Publishing, (2020), 371-389.
[29]	P. Klacansky, Open Scientific Visualization Datasets, https://klacansky.com/open-scivis-datasets/.
[30]	L. Li, C. Thompson, G. Henselman-Petrusek, C. Giusti and L. Ziegelmeier, Minimal cycle representatives in persistent homology using linear programming: An empirical study with user's guide, Front Artif Intell, 4 (2021), 681117. doi: 10.3389/frai.2021.681117.
[31]	Y. Luo and B. J. Nelson, Accelerating iterated persistent homology computations with warm starts, Computational Geometry, 120 (2024), 102089. doi: 10.1016/j.comgeo.2024.102089.
[32]	D. Lütgehetmann, D. Govc, J. P. Smith and R. Levi, Computing persistent homology of directed flag complexes, Algorithms, 13 (2020). doi: 10.3390/a13010019.
[33]	C. Maria, Filtered complexes, GUDHI User and Reference Manual, (2025).
[34]	H. Markram, et al., Reconstruction and simulation of neocortical microcircuitry, Cell 163, 2 (2015), 456-492.
[35]	M. Moor, M. Horn, B. Rieck and K. Borgwardt, Topological autoencoders, Proceedings of Machine Learning Research, PMLR, 119 (2020), 7045-7054.
[36]	D. Morozov, Dionysus, A C++ Library for Computing Persistent Homology, 2007.
[37]	D. Morozov and P. Skraba, Persistent cohomology in matrix multiplication time, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 332 (2025). doi: 10.4230/LIPIcs.SoCG.2025.68.
[38]	P. Oesterling, C. Heine, G. H. Weber, D. Morozov and G. Scheuermann, Computing and visualizing time-varying merge trees for high-dimensional data, Topological Methods in Data Analysis and Visualization IV, Springer International Publishing, (2017), 87–101. doi: 10.1007/978-3-319-44684-4_5.
[39]	N. Otter, M. A. Porter, U. Tillmann, P. Grindrod and H. A. Harrington, A roadmap for the computation of persistent homology, EPJ Data Science, 6 (2017). doi: 10.1140/epjds/s13688-017-0109-5.
[40]	S. Y. Oudot, Persistence theory: From quiver representations to data analysis, American Mathematical Society, Providence, RI, 209 (2015). doi: 10.1090/surv/209.
[41]	J. A. Perea and J. Harer, Sliding windows and persistence: An application of topological methods to signal analysis, Foundations of Computational Mathematics, 15 (2015), 799-838. doi: 10.1007/s10208-014-9206-z.
[42]	J. B. Pérez, S. Hauke, U. Lupo, M. Caorsi and A. Dassatti, Giotto-ph: A python library for high-performance computation of persistent homology of Vietoris–Rips filtrations, arXiv, arXiv:2107.05412.
[43]	M. W. Reimann, et al., Cliques of neurons bound into cavities provide a missing link between structure and function, Frontiers in Computational Neuroscience, 11 (2017). doi: 10.3389/fncom.2017.00048.
[44]	E. Santander, D. Pokorny, C. Ecker, A. Lazovskis, J. Santoro, M. Smith, J. P. Hess, K. R. Levi and M. W. Reimann, Heterogeneous and higher-order cortical connectivity undergirds efficient, robust, and reliable neural codes, Iscience, 28 (2025), 111585. doi: 10.1016/j.isci.2024.111585.
[45]	N. Saul and C. Tralie, TaDAset-a Scikit-TDA project, https://github.com/scikit-tda/tadasets, 2018.
[46]	J. P. Smith, Flagser-Count, https://github.com/JasonPSmith/flagser-count, 2024.