Utility Functions for Matrices#

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.

sage.homology.matrix_utils.dhsw_snf(mat, verbose=False)[source]#

Preprocess a matrix using the “Elimination algorithm” described by Dumas et al. [DHSW2003], and then call elementary_divisors on the resulting (smaller) matrix.

Note

‘snf’ stands for ‘Smith Normal Form’.

INPUT:

  • mat – an integer matrix, either sparse or dense.

(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

  • it’s zero, in which case it should be deleted.

  • its first nonzero entry is 1 or -1, in which case it should be kept.

  • its first nonzero entry is something else, in which case it is deferred until the second pass.

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

>>> from sage.all import *
>>> from sage.homology.matrix_utils import dhsw_snf
>>> mat = matrix(ZZ, Integer(3), Integer(4), range(Integer(12)))
>>> dhsw_snf(mat)
[1, 4, 0]
>>> mat = random_matrix(ZZ, Integer(20), Integer(20), x=-Integer(1), y=Integer(2))
>>> mat.elementary_divisors() == dhsw_snf(mat)
True