On Wednesday, March 26, 2014 1:32:13 PM UTC+1, John Cremona wrote: > > You should definitely open a trac ticket.
I just opened #16014 for this. And would make this a link to http://trac.sagemath.org/ticket/16014 if the Google Groups editor weren't too broken to let me do so… Don't expect that if you > post some code as text on a ticket that someone else will magically do > the right thing though! If you have not before contributed to Sage > you can make this your chance to learn how that works, and people will > help. > I've submitted a couple of patches, e.g. for #13608<http://trac.sagemath.org/ticket/13608>and#14239<http://trac.sagemath.org/ticket/14239>, and the one for #14403 <http://trac.sagemath.org/ticket/14403> which even got committed<http://git.sagemath.org/sage.git/log/?h=0434e05e991250f7eb0a19326be1a128a0baccce&qt=range&q=a4b97566e0e90be364d851ac0199bcdb7022ce03..0434e05e991250f7eb0a19326be1a128a0baccce> . But I'll take that opportunity to come to grips with the new git-based workflow. After pulling recent changes into my existing git checkout, I'm currently running “./sage --upgrade”, and hope that after that and a “./sage -b” I have an up-to-date snapshot of the current sage master which I can then use as the basis for this contribution. If I should rather start from a released version, and avoid updating prior to contribution, please tell me so and also let me know why that's preferred. > I would separate out two things here: one is a generic computation of > discriminants of univariate polynomials of degree d, the result being > a polynomial in d+1 variables (the generic coefficients) over ZZ (that > is correct -- there's a unique map from ZZ to any other ring). This > should be part of the current invariant_theory module, though when I > just looked at that it only appeared to implement invariants for > binary forms of degrees 2 and 4 (not 3) as well as some ternary stuff. > Uh… I had never seen that module<http://sagemath.org/doc/reference/rings/sage/rings/invariant_theory.html>before. But the way I see it, one would have to encode the degree of the polynomial into the name of some identifier, which would be possible if I did some case distinction as you indicated, but which feels weird nevertheless. > As a stop-gap, a global function generic_univariate_discriminant(deg) > whose output is a polynomial in ZZ[a0,a1,...,ad] and which caches its > results would do. Sounds more reasonable to me. Would you suggest that global to be in invariant_theory<http://git.sagemath.org/sage.git/tree/src/sage/rings/invariant_theory.py?id=6.1.1>nevertheless, or rather in polynomial_element.pyx<http://git.sagemath.org/sage.git/tree/src/sage/rings/polynomial/polynomial_element.pyx?id=6.1.1>where it is used? > Then your function should be a method for the class which is already > computing your discriminants, namely > sage.rings.polynomial.polynomial_element.Polynomial_generic_dense > but as there is already a discriminant function there you don't need a > new function, just special case code to catch small degrees (up to 3 > or 4 at least) which gets the generic expression and substitutes > coefficients. I wonder whether doing the case distinction on degree is really the right thing to do. On the one hand, if the computation already takes ages for degree 3, it will be even worse for higher degrees. On the other hand, this computation is only bad due to the fact that the determinant computation on big polynomials is so expensive. If the base ring were just some finite field or some such, then I doubt we'd have to worry. So I wonder whether it might make more sense to do the case distinction based on the underlying ring. And in that case, I'm far from sure which cases should be handled which way. I guess I'd start by only detecting polynomial rings, and wait for other use cases to report problems. I don't know the most appropriate way to check whether a ring is a polynomial ring. Is some form of isinstancecheck the right way to do this, or should I combine checks is_PolynomialRing and is_MPolynomialRing? Perhaps I could also add an argument “algorithm” to the discriminant method. It would default to None (meaning auto-selection) but could be used to force either direct computation or substitution. So possible values might be “direct” and “substitution”, perhaps others later on as well. That way, users could try alternatives to work out when a given method is faster than a different one, and could file bug reports requesting a change of default for certain cases. This would be as simple as > > if f.degree()<5: > return generic_univariate_discriminant(f.list()) > > As for the generic function, something like > > def generic_univariate_discriminant(d): > R = PolynomialRing(ZZ,d,names='a') > a = R.gens() > if d==1: return 1 > if d==2: return a[1]^2 - 4*a[0]*a[2] > > if d==3: return a[1]**2*a[2]**2 - 4*a[0]*a[2]**3 - 4*a[1]**3*a[3] + > 18*a[0]*a[1]*a[2]*a[3] - 27*a[0]**2*a[3]**2 > > (and so on) would do. Hmmm… If we do the case distinction not on degree but on base ring, this doesn't look as attractive. Plus my own code would have been particularly efficient for sparse polynomials of high degree, since it would only do the generic computation for the non-zero terms. Hard-coding a few simple cases might still be faster than doing the code I posted for every case, but it also might be slower than using cached values. So perhaps we want a case distinction on degree to choose between cached polynomials for dense low degree cases and on-the fly computation for possibly sparse computation of high degree. The former using code like you posted, the latter code like I did, and both used for subsequent substitution. Of course, all of this could as well be discussed on the trac ticket. -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
