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 stack of sophisticated K[x] techniques such as minimal approximant basis and high-order lifting for system solving and some of the algorithms of Neiger and his coauthors: http://dl.acm.org/citation.cfm?id=2930889.2930928 An algorithm for Hermite Normal form which is fast for "random" input matrices is much easier to make. In this case, a lot of the complexity of the above approach trivialises. Vincent Neiger has told me that generally a sensible implementation of his algorithms should have a fair amount of these "if stuff is simple, just do this"-clauses to avoid extra work. Perhaps that's yet another reason it is tricky to get. I know that some work has been initiated in LinBox, notably computing minimal approximant bases (also known as sigma basis or order basis) using the algorithm PMBasis from: Giorgi, P., C.P. Jeannerod, and G. Villard. 2003. βOn the Complexity of Polynomial Matrix Computations.β In International Symposium on Symbolic and Algebraic Computation, 135β142. Just having that algorithm in Sage would be a great addition: it is a powerful hammer that can be applied to many problems, e.g. computing reduced and normal forms as well as determinant etc. etc. My understanding is that these implementations are still experimental and somewhat undocumented in LinBox but Pascal Giorgi in particular is working on it. Once that stabilises, we should get it into Sage asap. 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. Best, Johan 'Bill Hart' via sage-devel writes: > 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 Tuesday, 15 November 2016 10:01:09 UTC+1, Kwankyu Lee wrote: >> >> Hi, >> >> The current Hermite normal form algorithm in Sage for matrices over k[x] >> seems embarrassingly slow. It is a generic algorithm for matrices over >> PIDs. What would be possible ways to improve the situation? Any reference >> to literature or implementations or like would be welcome. Thanks. >> >> -- -- 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.
