On Nov 30, 2007 8:13 AM, Joel B. Mohler <[EMAIL PROTECTED]> wrote: > > I've observed that variable substitutions in fraction fields of mpolynomial > rings can be very slow. I believe this is because of the many gcd > computations > which occur in intermediate steps of the substitution. In my special case I'm > doing substitutions of monomials and fractions of monomials. This led me to > consider a much more efficient algorithm to do these substitions. Basically, > the idea is that I can keep all of my intermediate work in the mpolynomial > ring > and avoid computing a gcd until the very end when I compute one single gcd. > The > tradeoff is a bit more work up front to set up my book keeping and some > integer > arithmetic with the exponents. I think another way to think about this is > that > you can view a substition with monomials as a matrix multiplication with the > exponents being the entries (although that view point requires some massaging > to > involve the coefficients correctly). > > This improvement is only possible because I'm substituting monomials and so my > algorithm has a limited scope. I'd imagine that this is a fairly common case > though and merits special treatment. My question is whether it's worth > cluttering the substition code with it and where it should be placed.
Yes. You should open a trac ticket for this and post a patch or at least your code there. We don't want this to get lost. > Of > course, if someone has a better idea about how this should be done, I'm all > ears > for that too. I don't have a better idea. > > The code is here: > http://kiwistrawberry.us/research/fast_subst.py > > Here's some benchmarks (cython should help a lot too): > sage: R.<x,y,z>=QQ[] > sage: f1=(x+y)/(x^2-z^2) # small fraction > sage: f2=(x+y+z+x^2+y^2+z^2)/(x^2-z^2) # bigger fraction > sage: d1={x:z^2,y:x} # substitution of simple monomials > sage: d2={x:z^-2,y:z/x} # substitution of things in the fraction field > ************** > sage: timeit f1.subs(d1) > 1000 loops, best of 3: 1.63 ms per loop > sage: timeit fast_subst(f1,d1) > 1000 loops, best of 3: 528 µs per loop > ************** > sage: timeit f2.subs(d1) > 100 loops, best of 3: 2.4 ms per loop > sage: timeit fast_subst(f2,d1) > 1000 loops, best of 3: 681 µs per loop > ************** > sage: timeit f1.subs(d2) > 100 loops, best of 3: 2.04 ms per loop > sage: timeit fast_subst(f1,d2) > 1000 loops, best of 3: 635 µs per loop > ************** > sage: timeit f2.subs(d2) > 100 loops, best of 3: 2.85 ms per loop > sage: timeit fast_subst(f2,d2) > 1000 loops, best of 3: 834 µs per loop > > -- > Joel > > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ 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-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
