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. 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
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
