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.
