Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

People in this thread might want to note the ticket https://trac.sagemath.org/ticket/21024 -- 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

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

Le vendredi 18 novembre 2016 04:44:49 UTC+1, Kwankyu Lee a écrit : > I am not a big fan of the suggested asymptotically best algorithms relying > on auxiliary tools, which would be hard to implement and gain for small > matrices might be not much. > For sure; I do not know precisely what the

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

> > Vincent Neiger will soon join my group for two years as a postdoc, and I > know he is interested in implementing some of these things. I hope we > can do some things here and improve Sage's capabilities in this respect. > This would be great! -- You received this message because you are

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

Hi Vincent, Thank you for your expert comments and cutting-edge references. My target is to get hermite normal forms for square matrices over polynomial rings over finite fields, underlying function field arithmetic. What is available in Sage for this is only "A._hermite_form_PID()", which is

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

Le jeudi 17 novembre 2016 21:15:11 UTC+1, Johan S. H. Rosenkilde a écrit : > > John Cremona writes: > > I once used the weak Popov form in a talk with Hendrik Lenstra in the > > audience and he was quite amused since it appeared to be (and I think > > he is right) much the same as his brother

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

Le jeudi 17 novembre 2016 21:15:11 UTC+1, Johan S. H. Rosenkilde a écrit : > > John Cremona writes: > > I once used the weak Popov form in a talk with Hendrik Lenstra in the > > audience and he was quite amused since it appeared to be (and I think > > he is right) much the same as his brother

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

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

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

> Not me -- but I did review it in 2010! -- see > https://trac.sagemath.org/ticket/9069 Ah, I misunderstood what you had written previously :-) -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

On 17 November 2016 at 20:15, Johan S. H. Rosenkilde wrote: > John Cremona writes: >> That was the algorithm I implemented in Magma. It was not very hard. > > Indeed. My student made an effort of comparing C++, Cython and pure Sage > implementations, in combination with

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

John Cremona writes: > That was the algorithm I implemented in Magma. It was not very hard. Indeed. My student made an effort of comparing C++, Cython and pure Sage implementations, in combination with various tweaks to the algorithm. In the end the Cython version was at best 2x faster than my

[sage-devel] Re: Hermite normal form of matrix over polynomial ring

An optimised version is implemented in fricas, available as fricas. HP_solve It might provide a good benchmark. Martin -- 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

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

On 17 November 2016 at 16:07, Johan S. H. Rosenkilde wrote: >> I'm sure that Sage already has code for Weak Popov Form. I >> implemented it myself in about 2004 but from the date you can tell >> that it was not in Sage (but Magma). >> >> Indeed, search_src("popov") finds >> >>

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

> I'm sure that Sage already has code for Weak Popov Form. I > implemented it myself in about 2004 but from the date you can tell > that it was not in Sage (but Magma). > > Indeed, search_src("popov") finds > > matrix/matrix_misc.py:32:def weak_popov_form(M,ascend=True): That function doesn't

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

There's been quite a bit of work on Hermite normal form of K[x]-matrices recently, most notably by Vincent Neiger: http://dl.acm.org/citation.cfm?id=2930889.2930936 This algorithm gives a much faster way of computing the Hermite Normal form of K[x] matrices. Unfortunately it relies on quite

Re: [sage-devel] Re: Hermite normal form of matrix over polynomial ring

I'm sure that Sage already has code for Weak Popov Form. I implemented it myself in about 2004 but from the date you can tell that it was not in Sage (but Magma). Indeed, search_src("popov") finds matrix/matrix_misc.py:32:def weak_popov_form(M,ascend=True): John On 17 November 2016 at 15:27,

[sage-devel] Re: Hermite normal form of matrix over polynomial ring

A colleague suggested to look at the Popov form. I didn't look at what Sage is currently doing, so my apologies if this turns out to not be a useful comment. Here is a random paper on this that I found [1]. Bill. [1] http://perso.ens-lyon.fr/gilles.villard/BIBLIOGRAPHIE/PDF/issac96.pdf On