On Thu, Dec 14, 2023 at 12:52 PM Dima Pasechnik <dimp...@gmail.com> wrote: > > On Thu, Dec 14, 2023 at 5:37 AM Nils Bruin <nbr...@sfu.ca> wrote: > > > > (side note: Q is generally considered a PID, but indeed it makes little > > sense worrying about Smith normal form over it) > > > > Concerning the slow performance: from the documentation, > > R._matrix_smith_form would allow an optimized routine to kick in. That > > doesn't exist, though. > > ZZ doesn't have it either, but there is a whole different class for that in > > sage/matrix/matrix_integer_dense.pyx that provides a specific-for-ZZ smith > > form algorithm. For QQ['t'] you end up with the generic algorithm, which is > > liable to be inefficient and have quirks such having large variations in > > runtime, depending on the specific input. > > > > So: it makes sense it's not very optimal (yet?). It would require work to > > get a better implementation specific for QQ['t']. This could be worthwhile > > to do well. Summer of Code? > > Can't Sage just wrap PARI/gp matsnf (and mathnf) for QQ[t]? They work > for this case too, e.g. > > sage: R.<x> = QQ[] > sage: M=matrix(R, [[1+x^2, 2-x+x^3],[42-x, x^3]]) > sage: M.__pari__().matsnf(0) > [x^5 + x^4 - 41*x^3 - x^2 + 44*x - 84, 1] > sage: M.__pari__().mathnf(0) > [x^5 + x^4 - 41*x^3 - x^2 + 44*x - 84, 1/74088*x^4 + 43/74088*x^3 + > 1765/74088*x^2 + 41/74088*x + 883/37044; 0, 1] >
There are few caveats here. matsnf only takes square matrices in this case (something that can be fixed by padding with zero rows/columns) a bit of testing shows that on square random matrices, of size up to 7x7, testing along the lines of the code posted here shows that, if one doesn't do conversion, then PARI is, on average, twice, or even more as fast as smith_hermite() - but sometimes it's a slower, in between smith_hermite(A) and A.smith_form() Interestingly, Sage's hermite_form(), which seems to be an optimised Cython implementation, using _hermite_form_euclidean in matrix2.pyx, beats PARI's mathnf in terms of speed. (and mathnf is usually slower than matsnf!) Conversion back to Sage matrices doesn't work as there is no conevsion from PARI's polynomials to Sage polynomials implemented for gen_to_sage(), so it's not a bug per se, just a gap in functionality. Dima -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-support/CAAWYfq2ukzRvB6EShrK-nFVMUMCs1P4v1vmjVzNws2QXffQ%2BUQ%40mail.gmail.com.
