Timeline for Checking a generating set of $\mathbb{Z}^k$
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2017 at 11:32 | comment | added | Emil Jeřábek | The original reference for polynomial-time algorithm for SNF (and HNF) is doi.org/10.1137/0208040 . | |
| Oct 9, 2017 at 9:22 | comment | added | Derek Holt | To get a polynomial time algorithm, you can calculate the Hadamard bound $d$ on the determinants of square submatrices of $B$, and then do your computations modulo $d$. For your application, you do not need the associated basis change matrices, but the Kannan-Bachem algorithm is a polynomial tiem method for doing this. | |
| Oct 9, 2017 at 8:21 | comment | added | Derek Holt | There is a lot of literature on this problem. There are certainly polynomial time versions of SNF but I believe that the LLL based methods are the fastest in practice. | |
| Oct 9, 2017 at 1:25 | comment | added | Noam D. Elkies | Curiously LLL (or some other algorithm for lattice basis reduction) is often the most efficient way to deal with this issue. Also, SNF is implemented in several computer-algebra systems; e.g. in gp it's matsnf. | |
| Oct 9, 2017 at 0:51 | comment | added | Mikhail Tikhomirov | Thanks Richard! At a glance it seems that the intermediate coefficients can be exponentially long, which makes it hard to use this method for large matrices. Can we "cheat" computing $B$ explicitly if we only want to check that diagonal elements of $B$ are $\pm 1$? | |
| Oct 9, 2017 at 0:49 | history | edited | Richard Stanley | CC BY-SA 3.0 |
slight inaccuracy corrected
|
| Oct 9, 2017 at 0:20 | history | answered | Richard Stanley | CC BY-SA 3.0 |