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