On Sat, Nov 14, 2009 at 5:59 PM, Sebastian Pancratz <s...@pancratz.org> wrote: > > Dear all, > > Some might remember that in September I put a lot of effort into > rewriting Q[t] to use FLINT. While the patch (see trac #4000) was > very usable in practice already, despite the help of many people there > remained a few doctest failures throughout SAGE.
Could you add something to this email about performance comparisons with Magma? It's one thing to say "Sage is slow compared to my custom optimized C code" (no surprise), and another to say "Sage is 1000 times slower than some easy-to-write interpreter code in Magma" (ouch, and is the case here, right?). William > > In short, while using SAGE with my own PhD work (on computing > connection matrices) I came across a couple other issues with a high > overhead involved in using SAGE and so I decided to write plain C. > Currently, I am occupied with preparing my first year transfer thesis, > which I think serves the same purpose as the qualifying exams in the > US, but I am hoping that afterwards I can find the time to finish the > above ticket, if no-one else closes it before that. In the meantime, > I wanted to briefly describe the problems I ran into using SAGE and > let people know about some of the C code I have written to overcome > these problems (at least with regards to my own work), in case someone > else is interested. > > The first problem concerns the rational function field over Q. Using > this via > > F.<t> = Frac(PolynomialRing(QQ, 't')) > > was slow without applying the patch at trac #4000, but even with that > applied there seemed to still be a very noticeable overhead due to > some category related code. In fairness, I have to admit that I did > not go through too much trouble to chase down the exact problem. But > in any case I have written *much* faster C code based on FLINT --- I > include a link to this at the very end of this post. I should also > point to my post on flint-devel > > > http://groups.google.com/group/flint-devel/browse_thread/thread/43a57724b8b949fd > > I think that this code is set up quite well and that other people > might be interested in this. > > The second problem had to do with monomials in multivariate polynomial > rings. Here perhaps I should first say that I have only been working > with three to five variables, that is to say, there is no notion of > asymptotic performance as the number of variables increases. My main > motivation to look at this was that, on some examples, my code for > computing connection matrices made 5--100 million calls to monomial > comparisons alone. In SAGE, there was a very noticeable improvement > in performance at each step when moving from using > MPolynomial_polydict objects in a multivariate polynomial ring to > working directly with ETuple objects to finally working with a Cython > wrapper of a C array of ints. In my C code, I have now taken this a > step further, representing an entire monomial as a primitive type in a > 64-bit word. Benefits are the greatly simplified data structure and > that a couple of operations (multiplication, division, inverse > lexicographical comparison, to name the most prominent ones) reduce to > a simple operation on single words ("+", "-" and "<", respectively). > There are a few downsides, in particular with regards to generality. > For example, if one wants to use up to eight variables and have a > fixed number of bits per exponents regardless of the number of > variables (so that one can have implicit coercion between $R[X_0, X_1] > \subset \dotsb \subset R[X_0, \dotsc, X_7]$), then one needs to > guarantee that no computation involves individual exponents greater > than 255. On the other hand, if one is working with curves in three > homogeneous variables, then this approach allows exponents up to > 65535, which will probably suffice for most practical purposes. > > Of course, this implementation is much faster than my previous SAGE > code. But it is much more limited and I don't quite see it being of > much use in a general framework. Nonetheless, in case someone is > interested in taking a look at this, I have uploaded it to my domain, > too. > > I've uploaded these two implementations, together with full online > code documentations generated by doxygen, to my domain at > > http://www.pancratz.org/code/ > > Please don't be surprised by the simplistic design of the website, so > far I am mostly using it for private purposes. > > Kind regards, > > Sebastian > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
