The actual computation of homology groups ends up being linear algebra with the differentials thought of as matrices. This module contains some utility functions for this purpose.
Preprocess a matrix using the “Elimination algorithm” described by Dumas et al. [DHSW], and then call elementary_divisors on the resulting (smaller) matrix.
‘snf’ stands for ‘Smith Normal Form’.
(They use the transpose of the matrix considered here, so they use rows instead of columns.)
Go through mat one column at a time. For each column, add multiples of previous columns to it until either
Then do a second pass on the deferred columns.
At this point, the columns with 1 or -1 in the first entry contribute to the rank of the matrix, and these can be counted and then deleted (after using the 1 or -1 entry to clear out its row). Suppose that there were \(N\) of these.
The resulting matrix should be much smaller; we then feed it to Sage’s elementary_divisors function, and prepend \(N\) 1’s to account for the rows deleted in the previous step.
sage: from sage.homology.matrix_utils import dhsw_snf sage: mat = matrix(ZZ, 3, 4, range(12)) sage: dhsw_snf(mat) [1, 4, 0] sage: mat = random_matrix(ZZ, 20, 20, x=-1, y=2) sage: mat.elementary_divisors() == dhsw_snf(mat) True
|[DHSW]||Dumas, Heckenbach, Saunders, and Welker. Computing simplicial homology based on efficient Smith normal form algorithms. Algebra, geometry, and software systems. (2003) 177-206.|