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.<x> = 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.
