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.
