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. Of course, if someone has a better idea about how this should be done, I'm all ears for that too. 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 --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
