The notion of generalized rank in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. However, its efficient computation has not yet been studied in the literature. We show that the generalized rank over a finite interval
This content will become publicly available on January 20, 2025
Matrix reduction is the standard procedure for computing the persistent homology of a filtered simplicial complex with
 NSFPAR ID:
 10486734
 Publisher / Repository:
 Springer Nature
 Date Published:
 Journal Name:
 Journal of Applied and Computational Topology
 ISSN:
 23671726
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract I of a indexed persistence module$$\textbf{Z}^2$$ ${Z}^{2}$M is equal to the generalized rank of the zigzag module that is induced on a certain path inI tracing mostly its boundary. Hence, we can compute the generalized rank ofM overI by computing the barcode of the zigzag module obtained by restricting to that path. IfM is the homology of a bifiltrationF of simplices (while accounting for multicriticality) and$$t$$ $t$I consists of points, this computation takes$$t$$ $t$ time where$$O(t^\omega )$$ $O\left({t}^{\omega}\right)$ is the exponent of matrix multiplication. We apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module$$\omega \in [2,2.373)$$ $\omega \in [2,2.373)$M , determine whetherM is interval decomposable and, if so, compute all intervals supporting its indecomposable summands. 
Abstract We study a family of invariants of compact metric spaces that combines the Curvature Sets defined by Gromov in the 1980 s with Vietoris–Rips Persistent Homology. For given integers
and$$k\ge 0$$ $k\ge 0$ we consider the dimension$$n\ge 1$$ $n\ge 1$k Vietoris–Rips persistence diagrams ofall subsets of a given metric space with cardinality at mostn . We call these invariantspersistence sets and denote them as . We first point out that this family encompasses the usual Vietoris–Rips diagrams. We then establish that (1) for certain range of values of the parameters$${\textbf{D}}_{n,k}^{\textrm{VR}}$$ ${D}_{n,k}^{\text{VR}}$n andk , computing these invariants is significantly more efficient than computing the usual Vietoris–Rips persistence diagrams, (2) these invariants have very good discriminating power and, in many cases, capture information that is imperceptible through standard Vietoris–Rips persistence diagrams, and (3) they enjoy stability properties analogous to those of the usual Vietoris–Rips persistence diagrams. We precisely characterize some of them in the case of spheres and surfaces with constant curvature using a generalization of Ptolemy’s inequality. We also identify a rich family of metric graphs for which fully recovers their homotopy type by studying splitmetric decompositions. Along the way we prove some useful properties of Vietoris–Rips persistence diagrams using Mayer–Vietoris sequences. These yield a geometric algorithm for computing the Vietoris–Rips persistence diagram of a space$${\textbf{D}}_{4,1}^{\textrm{VR}}$$ ${D}_{4,1}^{\text{VR}}$X with cardinality with quadratic time complexity as opposed to the much higher cost incurred by the usual algebraic algorithms relying on matrix reduction.$$2k+2$$ $2k+2$ 
Abstract Sequence mappability is an important task in genome resequencing. In the (
k ,m )mappability problem, for a given sequenceT of lengthn , the goal is to compute a table whosei th entry is the number of indices such that the length$$j \ne i$$ $j\ne i$m substrings ofT starting at positionsi andj have at mostk mismatches. Previous works on this problem focused on heuristics computing a rough approximation of the result or on the case of . We present several efficient algorithms for the general case of the problem. Our main result is an algorithm that, for$$k=1$$ $k=1$ , works in$$k=O(1)$$ $k=O\left(1\right)$ space and, with high probability, in$$O(n)$$ $O\left(n\right)$ time. Our algorithm requires a careful adaptation of the$$O(n \cdot \min \{m^k,\log ^k n\})$$ $O(n\xb7min\{{m}^{k},{log}^{k}n\})$k errata trees of Cole et al. [STOC 2004] to avoid multiple counting of pairs of substrings. Our technique can also be applied to solve the allpairs Hamming distance problem introduced by Crochemore et al. [WABI 2017]. We further develop time algorithms to compute$$O(n^2)$$ $O\left({n}^{2}\right)$all (k ,m )mappability tables for a fixedm and all or a fixed$$k\in \{0,\ldots ,m\}$$ $k\in \{0,\dots ,m\}$k and all . Finally, we show that, for$$m\in \{k,\ldots ,n\}$$ $m\in \{k,\dots ,n\}$ , the ($$k,m = \Theta (\log n)$$ $k,m=\Theta (logn)$k ,m )mappability problem cannot be solved in strongly subquadratic time unless the Strong Exponential Time Hypothesis fails. This is an improved and extended version of a paper presented at SPIRE 2018. 
Abstract The Dushnik–Miller dimension of a poset
P is the leastd for whichP can be embedded into a product ofd chains. Lewis and Souza isibility order on the interval of integers is bounded above by$$[N/\kappa , N]$$ $[N/\kappa ,N]$ and below by$$\kappa (\log \kappa )^{1+o(1)}$$ $\kappa {(log\kappa )}^{1+o\left(1\right)}$ . We improve the upper bound to$$\Omega ((\log \kappa /\log \log \kappa )^2)$$ $\Omega \left({(log\kappa /loglog\kappa )}^{2}\right)$ We deduce this bound from a more general result on posets of multisets ordered by inclusion. We also consider other divisibility orders and give a bound for polynomials ordered by divisibility.$$O((\log \kappa )^3/(\log \log \kappa )^2).$$ $O({(log\kappa )}^{3}/{(loglog\kappa )}^{2}).$ 
Abstract In this paper, we study multistage stochastic mixedinteger nonlinear programs (MSMINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with
nonLipschitzian value functions and multistage stochastic mixedinteger linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MSMINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a stage stochastic MINLP satisfying$$(T+1)$$ $(T+1)$L exact Lipschitz regularization withd dimensional state spaces, to obtain an optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$$\varepsilon $$ $\epsilon $ , and is lower bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ $O\left({\left(\frac{2LT}{\epsilon}\right)}^{d}\right)$ for the general case or by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ $O\left({\left(\frac{\mathrm{LT}}{4\epsilon}\right)}^{d}\right)$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/21})$$ $O\left({\left(\frac{\mathrm{LT}}{8\epsilon}\right)}^{d/21}\right)$polynomially on the number of stages. We further show that the iteration complexity dependslinearly onT , if all the state spaces are finite sets, or if we seek a optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with$$(T\varepsilon )$$ $\left(T\epsilon \right)$T . To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixedinteger optimization.