On Jul 30, 8:35 am, Niles <nil...@gmail.com> wrote: > Hi, I think both the links are pointing to the same patch, which I've > been working on recently--thanks for taking a look! To get the patch > from trac to work, I think you need to use mercurial; there are some > instructions in the sage developer guide, but in case you don't feel > like going through all that I've put the two files online at > > http://www.math.uga.edu/~njohnson/sage-code/multi_power_series_ring.py > > and > > http://www.math.uga.edu/~njohnson/sage-code/multi_power_series_ring_e... > > It should work to just read them into a sage session, but let me know > if you have trouble. The times for your code look great! If I > understand correctly, the left column is from the trac patch, the > middle is your code in python, and the right is your code modified to > run in sage. I suspect that if you run all the tests on the same > machine, the timings for your code will look even better, but maybe > you could let us know if that's not the case. Could your code extend > to work over other base rings? > > For those interested, the email link from Mario's first post contains > timing comparisons between the trac patch and magma, with the general > conclusion that the trac patch performs better than Magma in several > cases, especially when the total degree is larger than a few hundred. >
Thank you for putting the files online! I have updated the benchmark table using the trac patch code (time in seconds) trac rmpoly.py rmpoly.sage expression 3.72 0.58 1.24 (1 + 2*a + 3*b + 4*d + L(0).O(16))^-5 0.03 0.01 0.01 (1 + a^3 + b^3 + c^4 + d^4 + L(0).O(15))^-20 0.33 0.07 0.12 (-1/6*b^6*d^14 - 1/9*a^4*b^10*c^4*d^12 +...+L(0).O(50))^20 14.3 0.52 1.21 (1 + 1/2*a + 3*b + 4*a*b + ... + Z(0).O(30))^-20 0.10 0.001 0.002 (1+a^14*b^9+8/3*a^22*b^11-...+Z(0).O(51))^-20 2.28 0.39 1.03 (1 + a + b + a*b + a^2 + b^2 + Z(0).O(30))^-20 3.38 0.40 1.09 (1 + a + 2*b - a*b + 3*a^2 - b^2 + Z(0).O(30))^-20 3.77 0.41 1.10 (1+a+12*b-10*a*b +13*a^2-7*b^2+Z(0).O(30))^-20 I have not tried using other rings; can you give me an example to try? > On 30 Jul., 01:03, Bill Hart <goodwillh...@googlemail.com> wrote: > I'm curious how you are getting good timings in Pure python? Is it a > new/clever algorithm? How does it fare for longer power series? Are > there even good algorithms that are asymptotically fast for these > sorts of problems? And can some of these be reduced to ordinary > multivariate polynomial computations? In rmpoly Poly inherits from dict, in which the key is an integer packed exponent; a polynomial p has a precision p.rp.bits_exp; each variable has bits_exp bits, so the maximum power of a variable is 2^(bits_exp) - 1 . There is an extra bit for each variable, used to detect overflow. The values of the dict are the coefficients. Packed exponents save memory, which helps with big polynomials. The product of two monomials is given by the sum of the packed exponents. The division is given by the difference of the packed exponents and a mask operation (see http://code.google.com/p/rmpoly/wiki/Internals). With 'grlex' ordering there is an extra variable carrying the total degree, used in truncations based on the total degree. No clever algorithm is used; packed exponents have been used before, see e.g. the article by M. Monagan, R. Pearce 'Polynomial multiplication and division using heap' available online. Since Python has fast dicts and integers with arbitrary size, it performs well with the product of polynomials and series. I suppose that the Sage version of rmpoly is slower because the Sage Integer is slower than Python integer for sums, and that a cython version of rmpoly would be as fast as the Python version. Mario -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
