On Thu, Apr 2, 2009 at 10:54 AM, Robert Bradshaw <[email protected]> wrote: > > On Apr 2, 2009, at 8:59 AM, William Stein wrote: > >> >> On Thu, Apr 2, 2009 at 4:42 AM, Jason Grout <jason- >> [email protected]> wrote: >>> >>> Martin Albrecht wrote: >>>> On Thursday 02 April 2009, Christophe Oosterlynck wrote: >>>>> Hi, >>>>> >>>>> is it possible to calculate the echelon form of matrices containing >>>>> polynomials over GF(2)? I'm getting the following error: >>>>> >>>>> NotImplementedError: echelon form over Univariate Polynomial >>>>> Ring in x >>>>> over Finite Field of size 2 (using NTL) not yet implemented >>>>> >>>>> M._maxima_().echelon() does calculate an echelon form but it >>>>> takes a >>>>> while and it's not taking into account the finite field GF(2)... >>>> >>>> Hi, >>>> >>>> one question of course is how you define the echelon form over a >>>> ring. If you >>>> construct a *multi*variate polynomial ring over GF(2) in *one* >>>> variable, then >>>> you have three options: >>>> >>>> sage: P = PolynomialRing(GF(2),1,'x') >>>> sage: type(P) >>>> <type >>>> 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_ >>>> libsingular'> >>>> sage: M = random_matrix(P,5,5) >>>> sage: M >>>> >>>> [ x^2 + 1 x^2 x^2 + x x^2 + x + 1 x + 1] >>>> [ 0 x^2 + x x 0 x^2] >>>> [ x + 1 x^2 + x + 1 1 0 x + 1] >>>> [ x^2 x^2 + x + 1 x^2 + x + 1 0 x + 1] >>>> [ x^2 + x 1 x^2 + 1 x^2 + x x^2 + 1] >>>> sage: type(M) >>>> <type >>>> 'sage.matrix.matrix_mpolynomial_dense.Matrix_mpolynomial_dense'> >>>> >>>> sage: M.echelon_form('row_reduction') >>>> sage: M.echelon_form('frac') >>>> sage: M.echelon_form('bareiss') >>>> >>>> Check >>>> >>>> sage: M.echelon_form? >>>> >>>> to see what each does in detail, basically: >>>> >>>> * row_reduction: only reduce by base field elements >>>> * frac: compute in the fraction field >>>> * bareiss: fraction free Gauss elimination (the name is rather bad) >>> >>> This might also help resolve the back-burner project of mine to make >>> echelon_form for integer matrices return the typical linear algebra >>> definition of rref, i.e., the 'frac' method above. Currently, the >>> decision is to make echelon_form behave like 'frac' above, and make >>> hermite_form behave like 'row_reduction' above. Making echelon_form >>> support the arguments above seems like it would be a better >>> resolution >>> and provide a clear deprecation path. However, the decision would >>> imply >>> that the default be 'frac' instead of 'row_reduction'. On the other >>> hand, it'd be great if things were consistent across base rings. >>> What >>> is the possibility of making the default to be 'frac' over polynomial >>> rings? (Sorry if this question is laughable or repulsive...) >> >> +1 to making the default be over the fraction field in all cases, and >> having a different >> command or non-default option for the non-fraction field version. >> Having just taught >> echelon forms to undergrads I now very much see Jason's point. > > +1 from me too. However, IIRC it used to be this way and then got > changed. Does anyone remember the rational for why?
Because in Magma EchelonForm over ZZ is HermiteForm, and David Kohel convinced me that this was a good design choice. William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
