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.
Note
‘snf’ stands for ‘Smith Normal Form’.
INPUT:
(They use the transpose of the matrix considered here, so they use rows instead of columns.)
ALGORITHM:
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.
EXAMPLES:
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
REFERENCES:
[DHSW] | Dumas, Heckenbach, Saunders, and Welker. Computing simplicial homology based on efficient Smith normal form algorithms. Algebra, geometry, and software systems. (2003) 177-206. |