Our Problem : Homology matrices Algebraic topology of simple graphs
Are boundary maps of simplicial complexes [Welker et al.]
Integer Smith form gives the homology groups [Munkres]
- Large dimension : 500000 ? 500000 is common
- Entries are -1, 0, 1
- Sparse with fixed small number of non-zero elements per row (up to 15)
- Very small Smith invariants : no more than a few words
- Laplacians ATA and AAT
- More than twice as many non-zeroes as A
- Also -1, 0, 1 entries except on diagonal
- very low degree minimal polynomial : even for the largest matrices, degree can be close to 25, sometimes up to 200