6
$\begingroup$

I can use software to calculate the Betti numbers $\beta_0,\beta_1,\beta_2,\dots$ of a finite simplicial complex.

This is prohibitive for large complexes, built on say > 100,000 nodes.

Is there some way to computationally approximate the ranks of the first $n$ homology groups? Results e.g. Carlson here seem to work only for data points in Euclidean space, where the relations on which the complex is built are interpretations of the data (i.e. persistent homology). I have a set of fixed, deterministic relations on a set of vertices i.e. a graph, and the corresponding clique complex.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Could you clarify what you mean by 'approximate' here? $\endgroup$
    – Neil Hoffman
    Commented Nov 27, 2018 at 17:20
  • 1
    $\begingroup$ I mean to get the Betti numbers, but only “nearly”. Some error is allowed. $\endgroup$
    – apg
    Commented Nov 27, 2018 at 17:22
  • 1
    $\begingroup$ Surely some numerical approximation is available which is inaccurate but quick, converging in some limit to the actual situation? $\endgroup$
    – apg
    Commented Nov 27, 2018 at 19:13
  • 2
    $\begingroup$ You can do mod p homology computations on data of large size. It is a kind of approximation. $\endgroup$
    – Dima Pasechnik
    Commented Nov 27, 2018 at 20:23
  • $\begingroup$ Ok I will look at mod p homology. I'm thinking of getting the Euler characteristic of the clique complex of a sparse complex network. $\endgroup$
    – apg
    Commented Nov 28, 2018 at 17:38

1 Answer 1

Reset to default
3
$\begingroup$

You have to find a way to reduce the size of your simplicial complex. Some algorithms based e.g. on discrete Morse theory can do that fairly rapidly, but they don't have guarantees on the amount of size reduction. I don't think there exists faster algorithms for approximate Betti numbers in general, but I believe it can be done if your simplicial complex is "low-dimensional", meaning that for any point, the size of the sub complex formed by vertices at distance less than $r$ from that point grows slowly with $r$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ OK I will look at this "lossy compression" idea. $\endgroup$
    – apg
    Commented Nov 28, 2018 at 17:41
  • 1
    $\begingroup$ Those reduction methods typically won't change the homotopy type, so they'll give you exact Betti numbers in fact $\endgroup$
    – alesia
    Commented Nov 28, 2018 at 18:55
  • $\begingroup$ So you can reduce the computation time, without losing information? Like lossless compression? $\endgroup$
    – apg
    Commented Dec 1, 2018 at 13:25
  • 1
    $\begingroup$ Actually the volume condition I was mentioning was for a different algorithm that approximates Betti numbers. It shouldn't affect the complex reduction algorithms $\endgroup$
    – alesia
    Commented Dec 1, 2018 at 18:00
  • 1
    $\begingroup$ web.math.ku.dk/~moller/students/brian_brost.pdf seems to have a good state of the art (section 7) $\endgroup$
    – alesia
    Commented Dec 1, 2018 at 21:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .