On Sunday, July 20, 2014 3:10:33 AM UTC+9, Jonas Jermann wrote: > > Hi all > > Could someone familiar with flint/sage enable flint's > revert_series (for rational/integer polynomials)? > > (Sorry if it was already implemented somewhere and I missed it). > > Attached is a small, non-intrusive patch (done with help from IRC) > in that direction which simply adds series reversion for > integer and rational flint polynomials. > > For those polynomials (resp. power series) flint is _much_ > faster than the current implementation of power series reversion > (which is a big bottleneck for the modular forms code I currently > work on -> "u/jj/hecke_mf"). > > In my opinion this offers an acceptable and small compromise which > in particular doesn't (yet) require to implement power series using > flint. For someone interested in using it for power series, simply > convert the series to a (flint) polynomial, apply flint's revert_series > and convert the result back to a power series. > > It could of course also be used to replace the current power series > reversion over integers/rationals. > > > Best > Jonas > Hi Jonas,
There is also an nmod_poly_revert_series in flint for polynomials over Z/nZ for word-size n. It would not hurt to wrap that function in the same patch. 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. Fredrik -- 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.