Re: [sage-devel] Re: flint revert_series
Hi On 22.07.2014 14:47, Jean-Pierre Flori wrote: My point of view is let's make one step at a time or we'll just never include anything in Sage. So I think the little wrapper you submitted is a good inclusion. For sure we should also implement all that Fredrik and you suggested, but let's already include what you already did. I added revert_series for flint over finite fields and I applied the suggested corrections. So the ticket is ready for review again. Best Jonas -- 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.
Re: [sage-devel] Re: flint revert_series
Hi On 21.07.2014 13:10, Fredrik Johansson wrote: On Mon, Jul 21, 2014 at 7:37 AM, Jonas Jermann jjerma...@gmail.com wrote: I agree, but somehow the flint import details are slightly different. I also saw a different name somewhere, reverse_series. So I was not sure how to exactly import it for nmod. I would appreciate if someone familiar with flint could do that (or leave it out for now). You could use some other method in polynomial_zmod_flint.pyx as a template; reverse() for example. I guess you saw reverse_series in nmod_poly.pxd. This file is just out of date and should be updated to match the nmod_poly.h in the latest flint. I added the zmod revert_series but somehow the result is wrong(?), even if I increase the precision. Attached is a patch against the current ticket with the failing doctest. Maybe revert_series does not exactly do what we/I expect for finite fields, it seems to drop the t^5 term over GF(5)? 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/-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 The fast reversion algorithm basically does fewer polynomial multiplications than the naive algorithm (O(n^0.5) instead of O(n)), so it's an improvement regardless of whether polynomial multiplication is slow or fast. That's very nice and only positive change. :) It's an independent modification of the current ticket though, right? I still feel the best long-term solution would be to use flint for power series. That would give a huge performance boost. But again, that's an independent question: The ticket could be applied even if flint was already used for power series. Best Jonas -- 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. diff --git a/src/sage/libs/flint/nmod_poly.pxd b/src/sage/libs/flint/nmod_poly.pxd index e99a228..3926a6c 100644 --- a/src/sage/libs/flint/nmod_poly.pxd +++ b/src/sage/libs/flint/nmod_poly.pxd @@ -68,6 +68,8 @@ cdef extern from flint/nmod_poly.h: cdef void nmod_poly_one(nmod_poly_t res) cdef void nmod_poly_truncate(nmod_poly_t poly, long len) cdef void nmod_poly_reverse(nmod_poly_t output, nmod_poly_t input, long m) +cdef void nmod_poly_revert_series(nmod_poly_t output, nmod_poly_t intput, long m) + cdef int nmod_poly_equal(nmod_poly_t a, nmod_poly_t b) # Powering diff --git a/src/sage/rings/polynomial/polynomial_zmod_flint.pyx b/src/sage/rings/polynomial/polynomial_zmod_flint.pyx index 1856be1..254501c 100644 --- a/src/sage/rings/polynomial/polynomial_zmod_flint.pyx +++ b/src/sage/rings/polynomial/polynomial_zmod_flint.pyx @@ -767,3 +767,39 @@ cdef class Polynomial_zmod_flint(Polynomial_template): else: nmod_poly_reverse(res.x, self.x, nmod_poly_length(self.x)) return res + +def revert_series(self, n): +r +Return a polynomial `f` such that `f(self(x)) = self(f(x)) = x mod x^n`. + +EXAMPLES:: + +sage: R.t = GF(5)[] +sage: f = t - t^3 + t^5 +sage: f.revert_series(5) # todo: this fails (needs to be fixed)! +t + t^3 + 2*t^5 + +sage: f.revert_series(-1) +Traceback (most recent call last): +... +ValueError: argument n must be a non-negative integer, got -1 + +sage: g = - t^3 + t^5 +sage: g.revert_series(6) +Traceback (most recent call last): +... +ValueError: self must have constant coefficient 0 and a unit for coefficient 1 + +cdef Polynomial_zmod_flint res = self._new() +cdef unsigned long m +if n 0: +raise ValueError(argument n must be a non-negative integer, got %s % n) +m = n +if not self[0].is_zero() or not self[1].is_unit(): +raise ValueError(self must have constant coefficient 0 and a unit for coefficient 1) + +sig_on() +nmod_poly_revert_series(res.x, self.x, m) +sig_off() + +return
Re: [sage-devel] Re: flint revert_series
On Tue, Jul 22, 2014 at 9:05 PM, Jonas Jermann jjerma...@gmail.com wrote: Hi On 21.07.2014 13:10, Fredrik Johansson wrote: On Mon, Jul 21, 2014 at 7:37 AM, Jonas Jermann jjerma...@gmail.com wrote: I agree, but somehow the flint import details are slightly different. I also saw a different name somewhere, reverse_series. So I was not sure how to exactly import it for nmod. I would appreciate if someone familiar with flint could do that (or leave it out for now). You could use some other method in polynomial_zmod_flint.pyx as a template; reverse() for example. I guess you saw reverse_series in nmod_poly.pxd. This file is just out of date and should be updated to match the nmod_poly.h in the latest flint. I added the zmod revert_series but somehow the result is wrong(?), even if I increase the precision. Attached is a patch against the current ticket with the failing doctest. Maybe revert_series does not exactly do what we/I expect for finite fields, it seems to drop the t^5 term over GF(5)? The reversion of t - t^3 + O(t^5) to length n = 5 should be t + t^3 + O(t^5). This is what I get when I call flint directly from a C program. Are you getting something different? Note that the current implementation requires that 1, 2, ..., n-1 are invertible (this restriction is documented in the flint manual). So for polynomials over GF(5), n = 6 would be invalid input. You could insert some code that checks this and either raises an exception or computes over Z or Q and converts back. 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/-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 The fast reversion algorithm basically does fewer polynomial multiplications than the naive algorithm (O(n^0.5) instead of O(n)), so it's an improvement regardless of whether polynomial multiplication is slow or fast. That's very nice and only positive change. :) It's an independent modification of the current ticket though, right? Sure. I still feel the best long-term solution would be to use flint for power series. That would give a huge performance boost. But again, that's an independent question: The ticket could be applied even if flint was already used for power series. True. 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.
Re: [sage-devel] Re: flint revert_series
On Tuesday, July 22, 2014 2:05:30 PM UTC+2, Jonas Jermann wrote: Hi On 21.07.2014 13:10, Fredrik Johansson wrote: On Mon, Jul 21, 2014 at 7:37 AM, Jonas Jermann jjer...@gmail.com javascript: wrote: I agree, but somehow the flint import details are slightly different. I also saw a different name somewhere, reverse_series. So I was not sure how to exactly import it for nmod. I would appreciate if someone familiar with flint could do that (or leave it out for now). You could use some other method in polynomial_zmod_flint.pyx as a template; reverse() for example. I guess you saw reverse_series in nmod_poly.pxd. This file is just out of date and should be updated to match the nmod_poly.h in the latest flint. I added the zmod revert_series but somehow the result is wrong(?), even if I increase the precision. Attached is a patch against the current ticket with the failing doctest. Maybe revert_series does not exactly do what we/I expect for finite fields, it seems to drop the t^5 term over GF(5)? 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/-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 The fast reversion algorithm basically does fewer polynomial multiplications than the naive algorithm (O(n^0.5) instead of O(n)), so it's an improvement regardless of whether polynomial multiplication is slow or fast. That's very nice and only positive change. :) It's an independent modification of the current ticket though, right? My point of view is let's make one step at a time or we'll just never include anything in Sage. So I think the little wrapper you submitted is a good inclusion. For sure we should also implement all that Fredrik and you suggested, but let's already include what you already did. -- 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.
Re: [sage-devel] Re: flint revert_series
On 22.07.2014 14:42, Fredrik Johansson wrote: On Tue, Jul 22, 2014 at The reversion of t - t^3 + O(t^5) to length n = 5 should be t + t^3 + O(t^5). This is what I get when I call flint directly from a C program. Are you getting something different? I meant to write revert_series(6) which didn't produce the t^5 term with flint but did with sage's reversion. Note that the current implementation requires that 1, 2, ..., n-1 are invertible (this restriction is documented in the flint manual). So for polynomials over GF(5), n = 6 would be invalid input. You could insert some code that checks this and either raises an exception or computes over Z or Q and converts back. Oh right. Thanks, I didn't realize that. That seems like a pretty serious restriction. :( I added support for flint's revert_series with that restriction. Best Jonas -- 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.
Re: [sage-devel] Re: flint revert_series
On Mon, Jul 21, 2014 at 7:37 AM, Jonas Jermann jjerma...@gmail.com wrote: I agree, but somehow the flint import details are slightly different. I also saw a different name somewhere, reverse_series. So I was not sure how to exactly import it for nmod. I would appreciate if someone familiar with flint could do that (or leave it out for now). You could use some other method in polynomial_zmod_flint.pyx as a template; reverse() for example. I guess you saw reverse_series in nmod_poly.pxd. This file is just out of date and should be updated to match the nmod_poly.h in the latest flint. 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/-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 The fast reversion algorithm basically does fewer polynomial multiplications than the naive algorithm (O(n^0.5) instead of O(n)), so it's an improvement regardless of whether polynomial multiplication is slow or fast. 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.
[sage-devel] Re: flint revert_series
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/-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.
[sage-devel] Re: flint revert_series
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/-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.
Re: [sage-devel] Re: flint revert_series
Hi Frederik On 20.07.2014 15:20, Fredrik Johansson wrote: 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. I agree, but somehow the flint import details are slightly different. I also saw a different name somewhere, reverse_series. So I was not sure how to exactly import it for nmod. I would appreciate if someone familiar with flint could do that (or leave it out for now). 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/-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. :-) I simply suggested a small, non-intrusive patch in the meantime which allows one to use flint. Also, the patch could be applied independent of the suggested improvement above. Best Jonas -- 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.
[sage-devel] Re: flint revert_series
I can have a look next week. Would you mind opening a ticket on trac for this? On Saturday, July 19, 2014 8:10:33 PM UTC+2, 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 -- 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.
Re: [sage-devel] Re: flint revert_series
Hi On 19.07.2014 23:48, Jean-Pierre Flori wrote: I can have a look next week. Thanks! Would you mind opening a ticket on trac for this? http://trac.sagemath.org/ticket/16685 Best Jonas On Saturday, July 19, 2014 8:10:33 PM UTC+2, 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 -- 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 mailto:sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com mailto: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. -- 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.
