Finite filtered complexes#

AUTHORS:

  • Guillaume Rousseau (2021-05)

This module implements the basic structures of finite filtered complexes. A filtered complex is a simplicial complex, where each simplex is given a weight, or “filtration value”, such that the weight of a simplex is greater than the weight of each of its faces.

The algorithm used in this module comes from [ZC2005].

EXAMPLES:

sage: FilteredSimplicialComplex([([0], 0), ([1], 0), ([0, 1], 1)])
Filtered complex on vertex set (0, 1) and
 with simplices ((0,) : 0), ((1,) : 0), ((0, 1) : 1)

>>> from sage.all import *
>>> FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(0)), ([Integer(0), Integer(1)], Integer(1))])
Filtered complex on vertex set (0, 1) and
 with simplices ((0,) : 0), ((1,) : 0), ((0, 1) : 1)

Sage can compute persistent homology of simplicial complexes:

sage: X = FilteredSimplicialComplex([([0], 0), ([1], 0), ([0, 1], 1)])
sage: X.persistence_intervals(0)                                                    # needs sage.modules
[(0, 1), (0, +Infinity)]

>>> from sage.all import *
>>> X = FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(0)), ([Integer(0), Integer(1)], Integer(1))])
>>> X.persistence_intervals(Integer(0))                                                    # needs sage.modules
[(0, 1), (0, +Infinity)]

FilteredSimplicialComplex objects are mutable. Filtration values can be set with the filtration method as follows:

sage: X = FilteredSimplicialComplex() # returns an empty complex
sage: X.persistence_intervals(1)                                                    # needs sage.modules
[]
sage: X.filtration(Simplex([0, 2]), 0) # recursively adds faces
sage: X.filtration(Simplex([0, 1]), 0)
sage: X.filtration(Simplex([1, 2]), 0)
sage: X.filtration(Simplex([0, 1, 2]), 1) # closes the circle
sage: X.persistence_intervals(1)                                                    # needs sage.modules
[(0, 1)]

>>> from sage.all import *
>>> X = FilteredSimplicialComplex() # returns an empty complex
>>> X.persistence_intervals(Integer(1))                                                    # needs sage.modules
[]
>>> X.filtration(Simplex([Integer(0), Integer(2)]), Integer(0)) # recursively adds faces
>>> X.filtration(Simplex([Integer(0), Integer(1)]), Integer(0))
>>> X.filtration(Simplex([Integer(1), Integer(2)]), Integer(0))
>>> X.filtration(Simplex([Integer(0), Integer(1), Integer(2)]), Integer(1)) # closes the circle
>>> X.persistence_intervals(Integer(1))                                                    # needs sage.modules
[(0, 1)]

The filtration value of a simplex can be accessed as well with the filtration method, by not specifying a filtration value in the arguments. If the simplex is not in the complex, this returns None:

sage: X = FilteredSimplicialComplex([([0], 0), ([1], 0), ([0,1], 1)])
sage: X.filtration(Simplex([0]))
0
sage: X.filtration(Simplex([1,2])) is None
True

>>> from sage.all import *
>>> X = FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(0)), ([Integer(0),Integer(1)], Integer(1))])
>>> X.filtration(Simplex([Integer(0)]))
0
>>> X.filtration(Simplex([Integer(1),Integer(2)])) is None
True

Filtration values can be accessed with function call and list syntax as follows:

sage: X = FilteredSimplicialComplex([([0], 0), ([1], 0), ([0,1], 1)])
sage: s_1 = Simplex([0])
sage: X[s_1]
0
sage: X(Simplex([0,1]))
1
sage: X(Simplex(['baba']))

>>> from sage.all import *
>>> X = FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(0)), ([Integer(0),Integer(1)], Integer(1))])
>>> s_1 = Simplex([Integer(0)])
>>> X[s_1]
0
>>> X(Simplex([Integer(0),Integer(1)]))
1
>>> X(Simplex(['baba']))
<BLANKLINE>

It is also possible to set the filtration value of a simplex with the insert method, which takes as argument a list of vertices rather than a Simplex. This can make code more readable / clear:

sage: X = FilteredSimplicialComplex()
sage: X.insert(['a'], 0)
sage: X.insert(['b', 'c'], 1)
sage: X
Filtered complex on vertex set ('a', 'b', 'c') and with simplices
 (('a',) : 0), (('c',) : 1), (('b',) : 1), (('b', 'c') : 1)

>>> from sage.all import *
>>> X = FilteredSimplicialComplex()
>>> X.insert(['a'], Integer(0))
>>> X.insert(['b', 'c'], Integer(1))
>>> X
Filtered complex on vertex set ('a', 'b', 'c') and with simplices
 (('a',) : 0), (('c',) : 1), (('b',) : 1), (('b', 'c') : 1)
class sage.topology.filtered_simplicial_complex.FilteredSimplicialComplex(simplices=[], verbose=False)[source]#

Bases: SageObject

Define a filtered complex.

INPUT:

  • simplices – list of simplices and filtration values

  • verbose – (default: False) if True, any change to the filtration value of a simplex will be printed

simplices should be a list of tuples (l, v), where l is a list of vertices and v is the corresponding filtration value.

EXAMPLES:

sage: FilteredSimplicialComplex([([0], 0), ([1], 0), ([2], 1), ([0,1], 2.27)])
Filtered complex on vertex set (0, 1, 2) and with simplices
 ((0,) : 0), ((1,) : 0), ((2,) : 1), ((0, 1) : 2.27000000000000)

>>> from sage.all import *
>>> FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(0)), ([Integer(2)], Integer(1)), ([Integer(0),Integer(1)], RealNumber('2.27'))])
Filtered complex on vertex set (0, 1, 2) and with simplices
 ((0,) : 0), ((1,) : 0), ((2,) : 1), ((0, 1) : 2.27000000000000)
betti_number(k, a, b, field=2, strict=True, verbose=None)[source]#

Return the k-dimensional Betti number from a to a + b.

INPUT:

  • k – the dimension for the Betti number

  • a – the lower filtration value

  • b – the size of the interval

  • field – prime number (default: 2); modulo which persistent homology is computed

  • strict – (default: True) if False, takes into account intervals of persistence 0

  • verbose – (optional) if True, print the steps of the persistent homology computation; the default is the verbosity of self

The Betti number \(\beta_k^{a,a+b}\) counts the number of homology elements which are alive throughout the whole duration [a, a+b].

EXAMPLES:

sage: X = FilteredSimplicialComplex([([0], 0), ([1], 0), ([0,1], 2)])
sage: X.betti_number(0, 0.5, 1)                                             # needs sage.modules
2
sage: X.betti_number(0, 1.5, 1)                                             # needs sage.modules
1

>>> from sage.all import *
>>> X = FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(0)), ([Integer(0),Integer(1)], Integer(2))])
>>> X.betti_number(Integer(0), RealNumber('0.5'), Integer(1))                                             # needs sage.modules
2
>>> X.betti_number(Integer(0), RealNumber('1.5'), Integer(1))                                             # needs sage.modules
1

If an element vanishes at time a + b exactly, it does not count towards the Betti number:

sage: X = FilteredSimplicialComplex([([0], 0), ([1], 0), ([0,1], 2)])
sage: X.betti_number(0, 1.5, 0.5)                                           # needs sage.modules
1

>>> from sage.all import *
>>> X = FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(0)), ([Integer(0),Integer(1)], Integer(2))])
>>> X.betti_number(Integer(0), RealNumber('1.5'), RealNumber('0.5'))                                           # needs sage.modules
1
filtration(s, filtration_value=None)[source]#

Set filtration value of a simplex, or return value of existing simplex.

INPUT:

  • s – Simplex for which to set or obtain the value of

  • filtration_value – (optional) filtration value for the simplex

If no filtration value is specified, this returns the value of the simplex in the complex. If the simplex is not in the complex, this returns None.

If filtration_value is set, this function inserts the simplex into the complex with the specified value. See documentation of insert() for more details.

EXAMPLES:

sage: X = FilteredSimplicialComplex([([0], 0), ([1], 1)])
sage: X.filtration(Simplex([0, 1])) is None
True
sage: X.filtration(Simplex([0, 1]), 2)
sage: X.filtration([0, 1])
2

>>> from sage.all import *
>>> X = FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(1))])
>>> X.filtration(Simplex([Integer(0), Integer(1)])) is None
True
>>> X.filtration(Simplex([Integer(0), Integer(1)]), Integer(2))
>>> X.filtration([Integer(0), Integer(1)])
2
insert(vertex_list, filtration_value)[source]#

Add a simplex to the complex.

All faces of the simplex are added recursively if they are not already present, with the same value. If the simplex is already present, and the new value is lower than its current value in the complex, the value gets updated, otherwise it does not change. This propagates recursively to faces.

If verbose has been enabled, this method will describe what it is doing during an insertion.

INPUT:

  • vertex_list – list of vertices

  • filtration_value – desired value of the simplex to be added

EXAMPLES:

sage: X = FilteredSimplicialComplex()
sage: X.insert(Simplex([0]),3)
sage: X
Filtered complex on vertex set (0,) and with simplices ((0,) : 3)

>>> from sage.all import *
>>> X = FilteredSimplicialComplex()
>>> X.insert(Simplex([Integer(0)]),Integer(3))
>>> X
Filtered complex on vertex set (0,) and with simplices ((0,) : 3)

If the verbose parameter was set to true, this method will print some info:

sage: X = FilteredSimplicialComplex(verbose=True)
sage: X.insert(Simplex([0, 1]), 2)
Also inserting face (1,) with value 2
Also inserting face (0,) with value 2
sage: X.insert(Simplex([0]),1)
Face (0,) is already in the complex.
However its value is 2: updating it to 1
sage: X.insert(Simplex([0]), 77)
Face (0,) is already in the complex.
Its value is 1: keeping it that way

>>> from sage.all import *
>>> X = FilteredSimplicialComplex(verbose=True)
>>> X.insert(Simplex([Integer(0), Integer(1)]), Integer(2))
Also inserting face (1,) with value 2
Also inserting face (0,) with value 2
>>> X.insert(Simplex([Integer(0)]),Integer(1))
Face (0,) is already in the complex.
However its value is 2: updating it to 1
>>> X.insert(Simplex([Integer(0)]), Integer(77))
Face (0,) is already in the complex.
Its value is 1: keeping it that way
persistence_intervals(dimension, field=2, strict=True, verbose=None)[source]#

Return the list of \(d\)-dimensional homology elements.

INPUT:

  • dimension – integer; dimension \(d\) for which to return intervals

  • field – prime number (default: 2); modulo which persistent homology is computed

  • strict – (default: True) if False, takes into account intervals of persistence 0

  • verbose – (optional) if True, print the steps of the persistent homology computation; the default is the verbosity of self

EXAMPLES:

sage: X = FilteredSimplicialComplex([([0], 0), ([1], 1), ([0,1], 2)])
sage: X.persistence_intervals(0)                                            # needs sage.modules
[(1, 2), (0, +Infinity)]

>>> from sage.all import *
>>> X = FilteredSimplicialComplex([([Integer(0)], Integer(0)), ([Integer(1)], Integer(1)), ([Integer(0),Integer(1)], Integer(2))])
>>> X.persistence_intervals(Integer(0))                                            # needs sage.modules
[(1, 2), (0, +Infinity)]
prune(threshold)[source]#

Return a copy of the filtered complex, where simplices above the threshold value have been removed.

INPUT:

  • threshold – a real value, above which simplices are discarded

Simplices with filtration value exactly equal to threshold are kept in the result.

EXAMPLES:

sage: a = FilteredSimplicialComplex()
sage: a.insert([0], 0)
sage: a.insert([0, 1], 1)
sage: a.insert([0, 2], 2)
sage: b = a.prune(1)
sage: b
Filtered complex on vertex set (0, 1) and
 with simplices ((0,) : 0), ((1,) : 1), ((0, 1) : 1)

>>> from sage.all import *
>>> a = FilteredSimplicialComplex()
>>> a.insert([Integer(0)], Integer(0))
>>> a.insert([Integer(0), Integer(1)], Integer(1))
>>> a.insert([Integer(0), Integer(2)], Integer(2))
>>> b = a.prune(Integer(1))
>>> b
Filtered complex on vertex set (0, 1) and
 with simplices ((0,) : 0), ((1,) : 1), ((0, 1) : 1)