Hi Jonas, >> Another idea (perhaps for a separate update) would be to add a sage >> implementation of flint's algorithm for reversion over generic base >> ring. This is Algorithm 1: "Fast Lagrange inversion" in >> http://www.ams.org/journals/mcom/0000-000-00/S0025-5718-2014-02857-3/ >> (if you can't access it, http://arxiv.org/abs/1108.4772). The generic >> code would be a little slower than flint's implementations over Z, Q >> and Z/nZ, so you definitely want to special-case those. But in >> general, this should be much faster than sage's current >> implementation for polynomials of high degree. > > I am not familiar with the details but I assume that the algorithm > heavily depends on the performance of power series operations like > multiplication or inversion. See e.g. fredrikj.net/math/rev.pdf > > Flint is quite fast for all of those and I think sage's power series > implementation is not optimized at all (does it even support fast > multiplication?). > > The ideal solution would be to directly improve sage's power series > implementation (e.g. using flint's code, which probably requires quite > a lot of work). In any case if you can implement the mentioned > improvement above that would be great of course. :-)
A while ago I wrote a Sage interface to PARI power series; see http://trac.sagemath.org/ticket/15601. It gives a nice speedup over finite fields, but currently doesn't seem to be much faster than Sage's own implementation over Q or Z. Maybe the upgrade to PARI 2.7.1 will improve this (see http://trac.sagemath.org/ticket/15767), but the two tickets don't work together out of the box. I think the ideal solution would be to implement power series using FLINT; whoever wants to do this should feel free to use #15601 as a template. Peter -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
