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 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.
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 thresholds are like, but for matrices of both small dimension and small degree (I see 10 x 10 matrices of degree 10 in your examples), these algorithms are probably not much faster (or maybe even slower) than simpler algorithms like Mulders-Storjohann's one. Having reasonably efficient implementations of such basic algorithms for K[X]-matrices would be a nice addition to Sage (even the product of K[X]-matrices is quite slow); let's hope we will get the situation improved during my Post-doc with Johan. Best, Vincent -- 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.
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 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.
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 very slow, even
if several aggravating "sanity-checks" in the code are stripped off.
Meanwhile, I coded a simple-minded hnf implementation for arbitrary
matrices over euclidean domains with extended gcd. This already excels the
current implementation:
sage: P. = PolynomialRing(GF(4))
sage: m=5;A=matrix(m,[P.random_element(m) for i in range(m) for j in
range(m)])
sage: timeit('A._hermite_form_PID()')
5 loops, best of 3: 81 ms per loop
sage: timeit('A._hermite_form_euclidean(transformation=True)')
25 loops, best of 3: 23.9 ms per loop
sage: m=10;A=matrix(m,[P.random_element(m) for i in range(m) for j in
range(m)])
sage: timeit('A._hermite_form_PID()')
5 loops, best of 3: 3.8 s per loop
sage: timeit('A._hermite_form_euclidean(transformation=True)')
5 loops, best of 3: 1.69 s per loop
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. The paper by Mulders and Storjohann, as you
said, would be practically useful to implement an hnf algorithm over
polynomial rings in Sage, in future. I will look into it. Thanks a lot to
you and others in this thread!
Kwankyu
--
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.
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 Arjen had written about in > > his (earlier!) thesis. > > The algorithm in [1] by Arjen Lenstra is somewhat similar to what > Mulders and Storjohann's algorithm, but it is asymptotically slower. > The one you implemented in Sage is closer to Lenstra's algorithm (and > has its complexity) than it is to the one of M-S. > > Mulders and Storjohann's algorith even predates the Lenstras: it was > (very loosely) outlined in 1980 in Kailath's legendary book. Arne > Storjohann himself seems slightly embarrassed that it now carries his > name; his article was just the first to really write it properly and > analyse it, and the article's intended contents were lots of stuff it > was used for. > > Best, > Johan > > [1] Lenstra, A.K. 1985. “Factoring Multivariate Polynomials over Finite > Fields.” Journal of Computer and System Sciences 30 (2): 235–248. > Another description of such iterative algorithms for finding a reduced basis can be found in the section 2.5 of the book [Wolovich, Linear Multivariable Systems, 1974]. One might even argue that, the (weak) Popov form being a (non-reduced) Gröbner basis of the row space of the matrix (K[X]-module) for the TOP order, these iterative algorithms are simplified versions of Buchberger's algorithm (~1965) in this univariate context. Yet indeed Mulders and Storjohann were the first to give a detailed algorithm with a clear cost analysis, and with a good cost bound. If one attempts at a first implementation (without following Mulders-Storjohann's presentation) it is quite easy to lose at least a factor in the dimension or degree of the matrix. -- 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.
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 Arjen had written about in > > his (earlier!) thesis. > > The algorithm in [1] by Arjen Lenstra is somewhat similar to what > Mulders and Storjohann's algorithm, but it is asymptotically slower. > The one you implemented in Sage is closer to Lenstra's algorithm (and > has its complexity) than it is to the one of M-S. > > Mulders and Storjohann's algorith even predates the Lenstras: it was > (very loosely) outlined in 1980 in Kailath's legendary book. Arne > Storjohann himself seems slightly embarrassed that it now carries his > name; his article was just the first to really write it properly and > analyse it, and the article's intended contents were lots of stuff it > was used for. > > Best, > Johan > > [1] Lenstra, A.K. 1985. “Factoring Multivariate Polynomials over Finite > Fields.” Journal of Computer and System Sciences 30 (2): 235–248. > Another description of such iterative algorithms for finding a reduced basis can be found in the section 2.5 of the book [Wolovich, Linear Multivariable Systems, 1974]. One might also argue that, the (weak) Popov form being a (non-reduced) Gröbner basis of the row space of the matrix (K[X]-module) for the TOP order, these iterative algorithms are simplified versions of Buchberger's algorithm (~1975) in this univariate context. Yet indeed Mulders and Storjohann were the first to give a detailed algorithm with a clear cost analysis, and with a good cost bound. -- 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.
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 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.
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 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.
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 various tweaks to the algorithm. > In the end the Cython version was at best 2x faster than my pure Sage > implementation. Which is probably not surprising to Cython veterans, but > it was to me :-) > >> > I have semi-unpolished code in my public repo [2] which uses that >> > implementation for shifted Popov form, order basis, etc., allowing the >> > whole host of normal forms and K[x] equation solvers. They work and are >> > tremendously useful, and they are reasonably fast for small-medium >> > matrices. If there is interest and I can get reviewers, I can become >> > motivated to polishing them off for Sage proper. >> >> I think there is interest. > > Good to hear. > >> 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 Arjen had written about in >> his (earlier!) thesis. > > The algorithm in [1] by Arjen Lenstra is somewhat similar to what > Mulders and Storjohann's algorithm, but it is asymptotically slower. > The one you implemented in Sage Not me -- but I did review it in 2010! -- see https://trac.sagemath.org/ticket/9069 > is closer to Lenstra's algorithm (and > has its complexity) than it is to the one of M-S. > > Mulders and Storjohann's algorith even predates the Lenstras: it was > (very loosely) outlined in 1980 in Kailath's legendary book. Arne > Storjohann himself seems slightly embarrassed that it now carries his > name; his article was just the first to really write it properly and > analyse it, and the article's intended contents were lots of stuff it > was used for. > > Best, > Johan > > > > [1] Lenstra, A.K. 1985. “Factoring Multivariate Polynomials over Finite > Fields.” Journal of Computer and System Sciences 30 (2): 235–248. > > -- > 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. -- 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.
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 pure Sage implementation. Which is probably not surprising to Cython veterans, but it was to me :-) > > I have semi-unpolished code in my public repo [2] which uses that > > implementation for shifted Popov form, order basis, etc., allowing the > > whole host of normal forms and K[x] equation solvers. They work and are > > tremendously useful, and they are reasonably fast for small-medium > > matrices. If there is interest and I can get reviewers, I can become > > motivated to polishing them off for Sage proper. > > I think there is interest. Good to hear. > 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 Arjen had written about in > his (earlier!) thesis. The algorithm in [1] by Arjen Lenstra is somewhat similar to what Mulders and Storjohann's algorithm, but it is asymptotically slower. The one you implemented in Sage is closer to Lenstra's algorithm (and has its complexity) than it is to the one of M-S. Mulders and Storjohann's algorith even predates the Lenstras: it was (very loosely) outlined in 1980 in Kailath's legendary book. Arne Storjohann himself seems slightly embarrassed that it now carries his name; his article was just the first to really write it properly and analyse it, and the article's intended contents were lots of stuff it was used for. Best, Johan [1] Lenstra, A.K. 1985. “Factoring Multivariate Polynomials over Finite Fields.” Journal of Computer and System Sciences 30 (2): 235–248. -- 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.
[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 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.
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
>>
>> matrix/matrix_misc.py:32:def weak_popov_form(M,ascend=True):
>
> That function doesn't compute the weak Popov form, but rather a row
> reduced form (they are closely related though), see
> https://trac.sagemath.org/ticket/16888.
>
> The algorithm is also quite slow. Together with a student we implemented
> Mulders and Storjohann's straightforward algorithm [1], see
That was the algorithm I implemented in Magma. It was not very hard.
>
> https://trac.sagemath.org/ticket/16742
>
> This implementation is much faster than what is currently in Sage.
> Unfortunately, the code never got polished and the student moved on to
> other things, so the code is rotting now.
>
> I have semi-unpolished code in my public repo [2] which uses that
> implementation for shifted Popov form, order basis, etc., allowing the
> whole host of normal forms and K[x] equation solvers. They work and are
> tremendously useful, and they are reasonably fast for small-medium
> matrices. If there is interest and I can get reviewers, I can become
> motivated to polishing them off for Sage proper.
I think there is interest.
>
> Unfortunately, I tried the implementation on Hermite Normal Form, and it
> seems worse than the current hermite_normal_form algorithm.
>
> In my previous mail I mention the minimal approximant basis algorithm by
> Giorgi, Jeannerod and Villard. This can be used for asymptotically much
> faster row reduction computation for large matrices.
>
> [1] Mulders, T., and A. Storjohann. 2003. “On Lattice Reduction for
> Polynomial Matrices.” Journal of Symbolic Computation 35 (4): 377–401.
>
> [2] https://bitbucket.org/jsrn/codinglib
>
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 Arjen had written about in
his (earlier!) thesis.
> --
> 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.
--
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.
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 compute the weak Popov form, but rather a row
reduced form (they are closely related though), see
https://trac.sagemath.org/ticket/16888.
The algorithm is also quite slow. Together with a student we implemented
Mulders and Storjohann's straightforward algorithm [1], see
https://trac.sagemath.org/ticket/16742
This implementation is much faster than what is currently in Sage.
Unfortunately, the code never got polished and the student moved on to
other things, so the code is rotting now.
I have semi-unpolished code in my public repo [2] which uses that
implementation for shifted Popov form, order basis, etc., allowing the
whole host of normal forms and K[x] equation solvers. They work and are
tremendously useful, and they are reasonably fast for small-medium
matrices. If there is interest and I can get reviewers, I can become
motivated to polishing them off for Sage proper.
Unfortunately, I tried the implementation on Hermite Normal Form, and it
seems worse than the current hermite_normal_form algorithm.
In my previous mail I mention the minimal approximant basis algorithm by
Giorgi, Jeannerod and Villard. This can be used for asymptotically much
faster row reduction computation for large matrices.
[1] Mulders, T., and A. Storjohann. 2003. “On Lattice Reduction for
Polynomial Matrices.” Journal of Symbolic Computation 35 (4): 377–401.
[2] https://bitbucket.org/jsrn/codinglib
--
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.
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 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.
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, 'Bill Hart' via sage-devel
wrote:
> 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.
--
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.
[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 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.
