Recently some bugs were reported in the implementation of the Pernet-Stein algorithm implemented in Flint (not a released version, so not in Sage).
I've been trying to fix these bugs, but don't seem to be able to. I wonder if someone familiar with the Sage implementation can help me understand this algorithm better. * In the paper [1] it states that "In the rest of this paper, we mainly address computation of the HNF of a square nonsingular matrix A". So I assume that this algorithm requires a non-singular matrix as input. Does Sage deal with this, and if so, how? * In section 7 of the paper they suggest dealing with the non-square case by picking a random prime and computing the rank profile modulo that prime. So this algorithm may return the wrong answer then? If so, how does Sage deal with this? * What are the precise conditions (see the first point above) for the input matrix if it is non-square? * In the Sage implementation, which is in sage/src/sage/matrix/matrix_integer_dense_hnf.py, the algorithm seems to be run until the result is in HNF (note the zero matrix is in HNF), but without passing the original matrix to the is_in_hnf_form function. How can you check the result was correct, if you don't refer to the original matrix? The output could be the HNF of another matrix, which just happens to have the same pivot behaviour. Where can I find a proof that this is sufficient to check the output of the algorithm in the proof=true case? I wasn't able to find a reference for it. Bill. [1] http://www.wstein.org/papers/hnf/pernet-stein-fast_computation_of_hnf_of_random_integer_matrices.pdf -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
