Implementation of power series using PARI

[pbruin]

Add a class PowerSeries_pari for power series based on PARI's t_SER type. At least if the base ring is a finite field, this is much faster than the existing implementation based on NTL polynomials.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ad5bd7c

two small fixes for PARI power series

[pbruin]

The current branch enables the new power series class if the base field is of type FiniteField_pari_ffelt, since it yields a noticeable improvement at least in that case.

Here is a more or less random example with power series over a PARI finite field.

Setup:

sage: F.<a> = FiniteField(29^10)
sage: v = [F.random_element() for i in range(100)]
sage: w = [F.random_element() for i in range(100)]
sage: R.<x> = PowerSeriesRing(F, implementation=....)
sage: f = R(v, 100); g = R(w, 100)

Timings (with -c -r 1, in milliseconds):

           pari     poly
R(v, 100)  0.252    23.6
f.list()   0.460    6.28
f + g      0.0328   0.204
f * g      6.24     6.64
~f         6.84     29.6
f^2        3.2      6.44

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​07f5508

fix infinite recursion in PowerSeries_pari.change_ring()

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a709d12

speed improvements for PARI power series

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2b1e6df	Merge branch 'develop' into ticket/15599-pari_series
​7fc9291	Merge branch 'ticket/15599-pari_series' into ticket/15601

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b796e06

Merge branch 'develop' into ticket/15601

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f287c7f

Merge branch 'develop' into ticket/15601

[rws]

I'm confused. If I click on the branch here the file power_series_poly.pyx containing class PowerSeries_poly is shown as deleted. Is this intended?

[pbruin]

Replying to rws:

I'm confused. If I click on the branch here the file power_series_poly.pyx containing class PowerSeries_poly is shown as deleted. Is this intended?

No, this is a Trac bug. If you check out this branch you can see the real changes with git diff develop...ticket/15601 (substitute your local branch name).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b9130ca

Merge branch 'develop' into ticket/15601

[pbruin]

There are a few doctest failures after merging in #15767, caused by what seems to be a PARI bug:

gp > f = Ser(Mod(0, 3), 'x)
%1 = Mod(0, 3) + O(x^16)
gp > valuation(f, 'x)
%2 = 0
gp > f * 1
%3 = Mod(0, 3)*x^15 + O(x^16)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​37fc8e8	Upgrade to PARI-2.7.1
​5db54b6	Trac 15767: reviewer patch
​1d103da	Trac 15767: fix doctest in Ser()
​62ca821	Trac 15767: explain application of Sturm's theorem
​7bde0ff	Merge branch 'ticket/15767-pari-2.7.1' into ticket/15601-power_series_pari
​1a587ed	Trac 15601: update error message
​bf435f8	Merge tag '6.4.beta1' into ticket/15767
​0bd609d	Merge branch 'ticket/15767-pari-2.7.1' into ticket/15601-power_series_pari
​5c5a857	Trac 15601: remove workaround for substitution of exact 0 in series

[pbruin]

Replied to related existing bug report at ​http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1587.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ac59217

Trac 15601: raise error when substituting series of negative valuation

[pbruin]

There were some glitches in PARI's handling of various kinds of zeroes in series. These are fixed by a sequence of upstream commits (e0167bc, 3e727c1, f6fece5, 480e7ae, f8e1592) related to PARI bug report 1587. It's probably easiest to wait for the next stable PARI version including these fixes.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d2aad36	Merge branch 'develop' into ticket/15601-power_series_pari
​0b3ebe6	Trac 15601: zero_element() -> zero(), fix doctest

[pbruin]

The bugs mentioned in comment:19 are fixed as of #16997.

[jdemeyer]

1. Replace PY_TYPE_CHECK by isinstance.

2. Is this still relevant?

   # Substitution of p-adic numbers in power series is
   # currently not implemented in PARI (2.5.5).
   

3. This looks fishy:

   if isinstance(n, slice):
       # get values from slice object
       start = n.start if n.start is not None else 0
       stop = self._prec if n.stop is None else n.stop
       if stop is infinity:
           stop = self.polynomial().degree() + 1
       step = 1 if n.step is None else n.step
   
       # find corresponding polynomial
       poly = self.polynomial()[start:stop]
       if step is not None:
           coeffs = poly.padded_list(stop)
           for i in range(start, stop):
               if (i - start) % step:
                   coeffs[i] = 0
           poly = self._parent._poly_ring()(coeffs)
   

I think you can (more or less) replace all the above code by

coeffs = self.padded_list()[n]
poly = self._parent._poly_ring()(coeffs)

[jdemeyer]

In error message like

raise ValueError('unknown power series implementation: %s' % implementation)

I prefer to see %r instead of %s (this will print strings with quotes and it might also print non-strings more nicely)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2ac2a0f	Trac 15601: replace PY_TYPE_CHECK by isinstance
​7fc3208	Trac 15601: update comments
​6a807a1	Trac 15601: use %r instead of %s in error message

[pbruin]

Replying to jdemeyer:

1. Replace PY_TYPE_CHECK by isinstance.

OK, done.

2. Is this still relevant?

   # Substitution of p-adic numbers in power series is
   # currently not implemented in PARI (2.5.5).
   

Yes, unfortunately.

3. This looks fishy: [...] I think you can (more or less) replace all the above code by

   coeffs = self.padded_list()[n]
   poly = self._parent._poly_ring()(coeffs)
   

This was adapted from power_series_poly.pyx. I would prefer to solve this using

poly = self.polynomial()[n]

to also handle negative start/stop/step correctly. Unfortunately, the __getitem__() methods of polynomials do not yet implement f[start:stop:step] with step != 1. Maybe we should open a ticket for this and then simplify __getitem__() for power series to use the one for polynomials?

[pbruin]

Replying to pbruin:

Unfortunately, the __getitem__() methods of polynomials do not yet implement f[start:stop:step] with step != 1. Maybe we should open a ticket for this and then simplify __getitem__() for power series to use the one for polynomials?

This is now #18940.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​9f2d04f

Trac 15601: use Polynomial.__getitem__() to slice power series

[pbruin]

(Note to reviewers: the dependency #18940 has not been merged into this ticket.)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​cebb8c3

Trac 15601: modernise Cython imports

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0b2b76c

Trac 15601: remove obsolete __richcmp__ method

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​46d41de

Merge branch 'develop' into ticket/15601-power_series_pari

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​97f9582	Trac 18940: use Polynomial.__getitem__() to slice power series
​b12ea0b	Trac 18940: document behaviour of __getitem__ for polynomials vs. lists
​6842d86	Trac 18940: forbid step < 0 in Polynomial.__getitem__()
​1c56779	Merge branch 'develop' into ticket/18940-getitem_step
​9478486	Deprecate slicing with start index
​b559028	Use __new__ to create an empty RealNumber
​44cca40	Deprecate slicing with start index also in padics
​a0600bc	Merge branch 'develop' into ticket/18940-getitem_step
​f6760c5	Merge branch 'ticket/18940-getitem_step' into ticket/15601-power_series_pari
​b9ba710	Trac 15601: remove doctests using deprecated/unsupported slice syntax

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​70b3583

Trac 15601: remove doctests using deprecated/unsupported slice syntax

[jdemeyer]

Why are you wrapping a Python gen instead of a PARI GEN (like for element_pari_ffelt)? Wrapping a wrapper sounds inefficient.

Edit: I'm not saying this is a needs_work issue, but I would like to know the reason.

[jdemeyer]

I would like to see some basic examples added to the top-level docstring of src/sage/rings/power_series_pari.pyx. In particular, it would be good to have examples over various base rings (it is the default implementation over ffelt, but it works over other rings too, right?).

[jdemeyer]

Replace

from sage.libs.pari.pari_instance cimport PariInstance
import sage.libs.pari.all
cdef PariInstance pari = sage.libs.pari.all.pari

by

from sage.libs.pari.pari_instance cimport pari_instance as pari

[jdemeyer]

def __init__(self, parent, f=0, prec=infinity, check=True)

is missing an INPUT: block. Moreover, it seems that the argument check makes functional changes to __init__ and I don't know if that is supposed to be like that.

I suggest to rename check=True to value_from_pari=False and replace if not check and isinstance(f, pari_gen): by if value_from_pari:.

EDIT: maybe it's better to move this code completely out of __init__ and make a new classmethod def construct_from_pari() which bypasses __init__ completely.

[jdemeyer]

Still in __init__, I don't think you use the fact that v is of type str, so replace

cdef str v = parent.variable_name()

by

v = parent.variable_name()

[jdemeyer]

Same thing in __invert__ and __pow__: replace

cdef pari_gen h = ~self.g

by

h = ~self.g

[jdemeyer]

Replace

use_lazy_mpoly_ring=False

by

use_lazy_mpoly_ring=None

and

if use_lazy_mpoly_ring:
    deprecation(...)

by

if use_lazy_mpoly_ring is not None:
    deprecation(...)

[jdemeyer]

Before:

sage: R.<x> = PowerSeriesRing(GF(31^20, 'a')); x.reverse()
x + O(x^20)

After:

sage: R.<x> = PowerSeriesRing(GF(31^20, 'a')); x.reverse()
...
AttributeError: 'sage.rings.power_series_pari.PowerSeries_pari' object has no attribute 'reverse'

[jdemeyer]

Before:

sage: R.<x> = PowerSeriesRing(GF(31^20, 'a')); x // x
1

After:

sage: R.<x> = PowerSeriesRing(GF(31^20, 'a')); x // x
...
TypeError: unsupported operand type(s) for //: 'sage.rings.power_series_pari.PowerSeries_pari' and 'sage.rings.power_series_pari.PowerSeries_pari'

(but note #2034)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4ed39dc

Trac 15601: address some reviewer comments

[pbruin]

Replying to jdemeyer:

Before:

sage: R.<x> = PowerSeriesRing(GF(31^20, 'a')); x // x
1

After:

sage: R.<x> = PowerSeriesRing(GF(31^20, 'a')); x // x
...
TypeError: unsupported operand type(s) for //: 'sage.rings.power_series_pari.PowerSeries_pari' and 'sage.rings.power_series_pari.PowerSeries_pari'

(but note #2034)

What is __floordiv__() supposed to do anyway? I can't immediately think of a case where it should behave differently from __div__, and the documentation of PowerSeries_poly.__floordiv__() doesn't help either.

[pbruin]

Replying to jdemeyer:

Why are you wrapping a Python gen instead of a PARI GEN (like for element_pari_ffelt)? Wrapping a wrapper sounds inefficient.

It seemed more efficient in terms of developer time... Power series are probably less time-critical than finite field elements.

[jdemeyer]

Replying to pbruin:

What is __floordiv__() supposed to do anyway?

Interesting question. Looking at the code, it seems to be the same as ordinary division.

It is very old code from

commit 4a1096784560180aa9497d70cffe1a9c93d41ab1
Author: robertwb <robertwb@math.washington.edu>
Date:   Tue Aug 8 23:43:19 2006 +0000

    [project @ ring and power series coercion, floordiv for polynomials]

[jdemeyer]

Anyway, my point was not very specific about floor division, just that certain things are implemented for ordinary power series, but not for PARI power series. This is bad because it might break existing code.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​64b8479	Merge branch 'develop' into ticket/15601-power_series_pari
​467726f	Trac 15601: new Cython function construct_from_pari()
​3850992	Trac 15601: remove obsolete attribute __params

[pbruin]

Replying to jdemeyer:

Anyway, my point was not very specific about floor division, just that certain things are implemented for ordinary power series, but not for PARI power series. This is bad because it might break existing code.

This is now #20062.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a37a8d9

Merge branch 'develop' into ticket/15601-power_series_pari

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5221fcd

Merge branch 'develop' into ticket/15601-power_series_pari

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c8aa5e4

Merge branch 'develop' into ticket/15601-power_series_pari

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0769069

Trac 15601: add examples to top-level docstring

[pbruin]

I think all reviewer comments so far have now been taken into account.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​952fdda

Merge branch 'develop' into ticket/15601-power_series_pari

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f558e08

Merge branch 'develop' into ticket/15601-power_series_pari

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f52aa9d

Trac 15601: remove argument and return types from arithmetic methods

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​015b2d0

Trac 15601: fix related to PARI gen no longer being an Element

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​e71808c	Trac 21755: export sage.libs.pari.gen.new_ref()
​58a6e8b	Merge branch 'ticket/21755-export_new_ref' into ticket/15601-power_series_pari
​968451d	Trac 15601: get_var() and new_ref() are now functions

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​af0d584	Merge branch 'develop' into ticket/15601-power_series_pari
​4c73d59	Trac 15601: fix imports from sage.libs.pari (moved to sage.libs.cypari2)

[pbruin]

Split off some parts as separate tickets, updated and squashed the branch.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ccfa224

Trac 15601: __nonzero__ -> __bool__ and xrange -> range (Python 3)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​73e7364

Trac 15601: gen has been renamed to Gen

[tscrim]

I made some minor revisions and python3 compatibility. I also removed the deprecation and the corresponding one in the PARI polynomials. If my changes are good, then you can set a positive review.

---

New commits:

​08b08de	Merge branch 'u/pbruin/15601-PowerSeries_pari' of git://trac.sagemath.org/sage into u/tscrim/pari_power_series-15601
​2c9cb8a	Some reviewer changes.

[pbruin]

Replying to tscrim:

I made some minor revisions and python3 compatibility. I also removed the deprecation and the corresponding one in the PARI polynomials. If my changes are good, then you can set a positive review.

Thanks. I see that the deprecated function alias is almost 2 years old, so removing it is fine.

Just out of curiosity: did you have a particular reason for changing """ to r""" in some docstrings? As far as I know this is only needed if the docstring contains backslashes that should be left alone.

[tscrim]

Replying to pbruin:

Just out of curiosity: did you have a particular reason for changing """ to r""" in some docstrings? As far as I know this is only needed if the docstring contains backslashes that should be left alone.

Either it was more of a habit (i.e., I didn't notice I did it) or I was being paranoid about things.