Regarding the original question: is the question specifically about computing the HNF? Or, is any other canonical form acceptable? (with known algorithms, it seems that the Popov form would be easier to implement efficiently than the HNF)
Also, would you have examples of typical dimensions and degrees of the considered matrices? do you have any additional information (determinant, "genericity", ..)? Now, some comments specifically about the HNF. I assume the question is about square, nonsingular matrices; otherwise it seems that the situation is not completely clarified in the literature. The fastest known algorithms for the HNF are in [1,2,3]. The algorithm of [1,2] is Las Vegas randomized while [3] is deterministic. There does not seem to be huge constant hidden in the big-Oh, but as Johan wrote above, these algorithms use a combination of technical tools, implying that writing a nice, fast implementation is not a straightforward task. In the paper of Mulders and Storjohann mentioned in the above answers, there is not only a weak Popov form algorithm, but many algorithms for a lot of things. They are not the asymptotically fastest known ones since they do not rely on fast polynomial arithmetic (nor fast matrix multiplication); yet usually they provide a good first implementation. In particular, there is an algorithm dedicated to the HNF in Section 5 of this paper, and I would be very much surprised if this turned out to be slower than the general algorithm implemented in Sage. [1] S. Gupta and A. Storjohann, Computing Hermite forms of polynomial matrices. ISSAC'11. https://cs.uwaterloo.ca/~astorjoh/issac11hermite.pdf [2] S. Gupta. Hermite Forms of Polynomial Matrices. Master's thesis, 2011. https://uwspace.uwaterloo.ca/handle/10012/6108 [3] G. Labahn, V. Neiger, W Zhou. Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix. https://arxiv.org/abs/1607.04176 -- 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 https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
