On 17 November 2016 at 16:07, Johan S. H. Rosenkilde <maill...@atuin.dk> 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.
