On Nov 14, 2009, at 5:59 PM, Sebastian Pancratz 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. > > 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.
Frac(R) is written in completely generic Python, and looks like it has lots of room for improvement (I glanced at it recently when looking at doing computations in in F_p(t). It's long overdue for being optimized... and I'm thinking there should probably be a special case for Frac(R[x]). That wouldn't be as fast as coding directly against FLINT, but I bet it could be within a factor of 2 (once trac #4000 goes in). > 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. If you're using MPolynomial_polydicts, that means you're working with the completely generic code, which has a lot of room for optimization (not to mention it sounds like there's a better specialized representation you could have used.) - Robert --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
