Opened 9 years ago
Closed 6 years ago
#15601 closed enhancement (fixed)
Implementation of power series using PARI
Reported by:  pbruin  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  algebra  Keywords:  pari series performance 
Cc:  Merged in:  
Authors:  Peter Bruin  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  2c9cb8a (Commits, GitHub, GitLab)  Commit:  2c9cb8a5b1b7e7b2f36289f56f57fb50f7a1213d 
Dependencies:  #20062, #21755, #22210, #22212  Stopgaps: 
Description
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.
Change History (71)
comment:1 Changed 9 years ago by
 Branch set to u/pbruin/15601power_series_pari
 Created changed from 12/28/13 17:06:24 to 12/28/13 17:06:24
 Modified changed from 12/28/13 17:06:24 to 12/28/13 17:06:24
comment:2 Changed 9 years ago by
 Commit set to ad5bd7c94aa04bfc05de1dcd55a1fb211b69fba1
comment:3 Changed 9 years ago by
 Status changed from new to needs_review
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
comment:4 Changed 9 years ago by
 Commit changed from ad5bd7c94aa04bfc05de1dcd55a1fb211b69fba1 to 07f550886a773e26603b014ff4446f873920de90
Branch pushed to git repo; I updated commit sha1. New commits:
07f5508  fix infinite recursion in PowerSeries_pari.change_ring()

comment:5 Changed 9 years ago by
 Commit changed from 07f550886a773e26603b014ff4446f873920de90 to a709d129319d22effa6967ee9e52f36fe634587c
Branch pushed to git repo; I updated commit sha1. New commits:
a709d12  speed improvements for PARI power series

comment:6 Changed 9 years ago by
 Commit changed from a709d129319d22effa6967ee9e52f36fe634587c to 7fc9291a64af97305b103d5ecc32a1c441859e8c
comment:7 Changed 9 years ago by
 Commit changed from 7fc9291a64af97305b103d5ecc32a1c441859e8c to b796e0654b2d56cdd55582e6108a534cb18b1282
Branch pushed to git repo; I updated commit sha1. New commits:
b796e06  Merge branch 'develop' into ticket/15601

comment:8 Changed 9 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:9 Changed 8 years ago by
 Commit changed from b796e0654b2d56cdd55582e6108a534cb18b1282 to f287c7f6c1f355cd29bed47f91577a4a41fbc72f
Branch pushed to git repo; I updated commit sha1. New commits:
f287c7f  Merge branch 'develop' into ticket/15601

comment:10 followup: ↓ 11 Changed 8 years ago by
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?
comment:11 in reply to: ↑ 10 Changed 8 years ago by
Replying to rws:
I'm confused. If I click on the branch here the file
power_series_poly.pyx
containingclass 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).
comment:12 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:13 Changed 8 years ago by
 Commit changed from f287c7f6c1f355cd29bed47f91577a4a41fbc72f to b9130ca7e14038a5923a5fd2b6f6018ef1281292
Branch pushed to git repo; I updated commit sha1. New commits:
b9130ca  Merge branch 'develop' into ticket/15601

comment:14 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:15 Changed 8 years ago by
 Dependencies changed from #15599 to #15599, #15767
 Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.
 Status changed from needs_review to needs_work
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)
comment:16 Changed 8 years ago by
 Commit changed from b9130ca7e14038a5923a5fd2b6f6018ef1281292 to 5c5a857153089623e461997862c4fd0e7c014a68
Branch pushed to git repo; I updated commit sha1. New commits:
37fc8e8  Upgrade to PARI2.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/15767pari2.7.1' into ticket/15601power_series_pari

1a587ed  Trac 15601: update error message

bf435f8  Merge tag '6.4.beta1' into ticket/15767

0bd609d  Merge branch 'ticket/15767pari2.7.1' into ticket/15601power_series_pari

5c5a857  Trac 15601: remove workaround for substitution of exact 0 in series

comment:17 Changed 8 years ago by
 Report Upstream changed from Not yet reported upstream; Will do shortly. to Reported upstream. No feedback yet.
Replied to related existing bug report at http://pari.math.ubordeaux.fr/cgibin/bugreport.cgi?bug=1587.
comment:18 Changed 8 years ago by
 Commit changed from 5c5a857153089623e461997862c4fd0e7c014a68 to ac592175072360a0bd8a295dfa68defa19b4c609
Branch pushed to git repo; I updated commit sha1. New commits:
ac59217  Trac 15601: raise error when substituting series of negative valuation

comment:19 Changed 8 years ago by
 Report Upstream changed from Reported upstream. No feedback yet. to Fixed upstream, but not in a stable release.
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.
comment:20 Changed 7 years ago by
 Commit changed from ac592175072360a0bd8a295dfa68defa19b4c609 to 0b3ebe6f6787289acaeaa640d417e275e0d5ee07
comment:21 Changed 7 years ago by
 Report Upstream changed from Fixed upstream, but not in a stable release. to N/A
 Status changed from needs_work to needs_review
The bugs mentioned in comment:19 are fixed as of #16997.
comment:22 followup: ↓ 25 Changed 7 years ago by
 Status changed from needs_review to needs_work
 Replace
PY_TYPE_CHECK
byisinstance
.
 Is this still relevant?
# Substitution of padic numbers in power series is # currently not implemented in PARI (2.5.5).
 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)
comment:23 Changed 7 years ago by
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 nonstrings more nicely)
comment:24 Changed 7 years ago by
 Commit changed from 0b3ebe6f6787289acaeaa640d417e275e0d5ee07 to 6a807a19c95debc2a62dc791c33bd4702867ae49
comment:25 in reply to: ↑ 22 ; followup: ↓ 26 Changed 7 years ago by
Replying to jdemeyer:
 Replace
PY_TYPE_CHECK
byisinstance
.
OK, done.
 Is this still relevant?
# Substitution of padic numbers in power series is # currently not implemented in PARI (2.5.5).
Yes, unfortunately.
 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?
comment:26 in reply to: ↑ 25 Changed 7 years ago by
 Dependencies changed from #15599, #15767 to #15599, #15767, #18940
comment:27 Changed 7 years ago by
 Commit changed from 6a807a19c95debc2a62dc791c33bd4702867ae49 to 9f2d04f67bc1ebb75b7dd3bca3aa9d9235ee68be
Branch pushed to git repo; I updated commit sha1. New commits:
9f2d04f  Trac 15601: use Polynomial.__getitem__() to slice power series

comment:28 Changed 7 years ago by
 Status changed from needs_work to needs_review
(Note to reviewers: the dependency #18940 has not been merged into this ticket.)
comment:29 Changed 7 years ago by
 Commit changed from 9f2d04f67bc1ebb75b7dd3bca3aa9d9235ee68be to cebb8c3f66eccf7f33f67d9bee01aef4753995e6
Branch pushed to git repo; I updated commit sha1. New commits:
cebb8c3  Trac 15601: modernise Cython imports

comment:30 Changed 7 years ago by
 Commit changed from cebb8c3f66eccf7f33f67d9bee01aef4753995e6 to 0b2b76c9beeb5ff08fd192a39a22c4a1a1926895
Branch pushed to git repo; I updated commit sha1. New commits:
0b2b76c  Trac 15601: remove obsolete __richcmp__ method

comment:31 Changed 7 years ago by
 Commit changed from 0b2b76c9beeb5ff08fd192a39a22c4a1a1926895 to 46d41de74a7117a4298d2d32f266048b046db0c9
Branch pushed to git repo; I updated commit sha1. New commits:
46d41de  Merge branch 'develop' into ticket/15601power_series_pari

comment:32 Changed 7 years ago by
 Commit changed from 46d41de74a7117a4298d2d32f266048b046db0c9 to b9ba710b4df49732c899e5ea2f9777d7fddec873
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/18940getitem_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/18940getitem_step

f6760c5  Merge branch 'ticket/18940getitem_step' into ticket/15601power_series_pari

b9ba710  Trac 15601: remove doctests using deprecated/unsupported slice syntax

comment:33 Changed 7 years ago by
 Commit changed from b9ba710b4df49732c899e5ea2f9777d7fddec873 to 70b35834896dfc2b67aa84651cac04087f38ad3a
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

comment:34 Changed 7 years ago by
 Dependencies #15599, #15767, #18940 deleted
 Milestone changed from sage6.4 to sage7.1
comment:35 followup: ↓ 46 Changed 7 years ago by
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.
comment:36 Changed 7 years ago by
I would like to see some basic examples added to the toplevel 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?).
comment:37 Changed 7 years ago by
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
comment:38 Changed 7 years ago by
 Status changed from needs_review to needs_work
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.
comment:39 Changed 7 years ago by
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()
comment:40 Changed 7 years ago by
Same thing in __invert__
and __pow__
: replace
cdef pari_gen h = ~self.g
by
h = ~self.g
comment:41 Changed 7 years ago by
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(...)
comment:42 Changed 7 years ago by
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'
comment:43 followup: ↓ 45 Changed 7 years ago by
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)
comment:44 Changed 7 years ago by
 Commit changed from 70b35834896dfc2b67aa84651cac04087f38ad3a to 4ed39dc5e57792ae6c31af0040ac7c2b6053d80e
Branch pushed to git repo; I updated commit sha1. New commits:
4ed39dc  Trac 15601: address some reviewer comments

comment:45 in reply to: ↑ 43 ; followup: ↓ 47 Changed 7 years ago by
Replying to jdemeyer:
Before:
sage: R.<x> = PowerSeriesRing(GF(31^20, 'a')); x // x 1After:
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.
comment:46 in reply to: ↑ 35 Changed 7 years ago by
Replying to jdemeyer:
Why are you wrapping a Python
gen
instead of a PARIGEN
(like forelement_pari_ffelt
)? Wrapping a wrapper sounds inefficient.
It seemed more efficient in terms of developer time... Power series are probably less timecritical than finite field elements.
comment:47 in reply to: ↑ 45 Changed 7 years ago by
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]
comment:48 followup: ↓ 50 Changed 7 years ago by
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.
comment:49 Changed 6 years ago by
 Commit changed from 4ed39dc5e57792ae6c31af0040ac7c2b6053d80e to 3850992772bb5f343dd9bf3bc808609dae640a16
comment:50 in reply to: ↑ 48 Changed 6 years ago by
 Dependencies set to #20062
comment:51 Changed 6 years ago by
 Commit changed from 3850992772bb5f343dd9bf3bc808609dae640a16 to a37a8d9b240cab1d734288b9bf11ba9007d6775d
Branch pushed to git repo; I updated commit sha1. New commits:
a37a8d9  Merge branch 'develop' into ticket/15601power_series_pari

comment:52 Changed 6 years ago by
 Commit changed from a37a8d9b240cab1d734288b9bf11ba9007d6775d to 5221fcd52fc4ead03f8240109d627828e256ff93
Branch pushed to git repo; I updated commit sha1. New commits:
5221fcd  Merge branch 'develop' into ticket/15601power_series_pari

comment:53 Changed 6 years ago by
 Commit changed from 5221fcd52fc4ead03f8240109d627828e256ff93 to c8aa5e4f86ce623cc1ba3d0cfab0c982a7dda121
Branch pushed to git repo; I updated commit sha1. New commits:
c8aa5e4  Merge branch 'develop' into ticket/15601power_series_pari

comment:54 Changed 6 years ago by
 Commit changed from c8aa5e4f86ce623cc1ba3d0cfab0c982a7dda121 to 07690693dedfe7697213c6271ccbb84d2678bce6
Branch pushed to git repo; I updated commit sha1. New commits:
0769069  Trac 15601: add examples to toplevel docstring

comment:55 Changed 6 years ago by
 Status changed from needs_work to needs_review
I think all reviewer comments so far have now been taken into account.
comment:56 Changed 6 years ago by
 Commit changed from 07690693dedfe7697213c6271ccbb84d2678bce6 to 952fdda3b84dfde5833976e779f6b5718cd2de3f
Branch pushed to git repo; I updated commit sha1. New commits:
952fdda  Merge branch 'develop' into ticket/15601power_series_pari

comment:57 Changed 6 years ago by
 Commit changed from 952fdda3b84dfde5833976e779f6b5718cd2de3f to f558e08b91460520d5fee24bbe0660bafcfedcb8
Branch pushed to git repo; I updated commit sha1. New commits:
f558e08  Merge branch 'develop' into ticket/15601power_series_pari

comment:58 Changed 6 years ago by
 Commit changed from f558e08b91460520d5fee24bbe0660bafcfedcb8 to f52aa9d5f70ec927c5da35c08823862903ecd872
Branch pushed to git repo; I updated commit sha1. New commits:
f52aa9d  Trac 15601: remove argument and return types from arithmetic methods

comment:59 Changed 6 years ago by
 Commit changed from f52aa9d5f70ec927c5da35c08823862903ecd872 to 015b2d072df2d2d02664b37204d58d5ae6fadb2e
Branch pushed to git repo; I updated commit sha1. New commits:
015b2d0  Trac 15601: fix related to PARI gen no longer being an Element

comment:60 Changed 6 years ago by
 Dependencies changed from #20062 to #20062, #21755
 Status changed from needs_review to needs_work
comment:61 Changed 6 years ago by
 Commit changed from 015b2d072df2d2d02664b37204d58d5ae6fadb2e to 968451d64747c68959163ce76c5e6bc154afc018
comment:62 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:63 Changed 6 years ago by
 Commit changed from 968451d64747c68959163ce76c5e6bc154afc018 to 4c73d5952d08b3868adcdf7101e521764d85b6d8
comment:64 Changed 6 years ago by
 Milestone changed from sage7.1 to sage7.5
comment:65 Changed 6 years ago by
 Branch changed from u/pbruin/15601power_series_pari to u/pbruin/15601PowerSeries_pari
 Commit changed from 4c73d5952d08b3868adcdf7101e521764d85b6d8 to 251a93b8af9a530c74dc2c10426f2c5054a7afbe
 Dependencies changed from #20062, #21755 to #20062, #21755, #22210, #22212
Split off some parts as separate tickets, updated and squashed the branch.
comment:66 Changed 6 years ago by
 Commit changed from 251a93b8af9a530c74dc2c10426f2c5054a7afbe to ccfa224b109bead02d4472bf7eb8dd88bc5843a5
Branch pushed to git repo; I updated commit sha1. New commits:
ccfa224  Trac 15601: __nonzero__ > __bool__ and xrange > range (Python 3)

comment:67 Changed 6 years ago by
 Commit changed from ccfa224b109bead02d4472bf7eb8dd88bc5843a5 to 73e73643bf80558337252cade01b703fb5e4c42a
Branch pushed to git repo; I updated commit sha1. New commits:
73e7364  Trac 15601: gen has been renamed to Gen

comment:68 followup: ↓ 69 Changed 6 years ago by
 Branch changed from u/pbruin/15601PowerSeries_pari to u/tscrim/pari_power_series15601
 Commit changed from 73e73643bf80558337252cade01b703fb5e4c42a to 2c9cb8a5b1b7e7b2f36289f56f57fb50f7a1213d
 Milestone changed from sage7.5 to sage7.6
 Reviewers set to Travis Scrimshaw
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/15601PowerSeries_pari' of git://trac.sagemath.org/sage into u/tscrim/pari_power_series15601

2c9cb8a  Some reviewer changes.

comment:69 in reply to: ↑ 68 ; followup: ↓ 70 Changed 6 years ago by
 Status changed from needs_review to positive_review
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.
comment:70 in reply to: ↑ 69 Changed 6 years ago by
Replying to pbruin:
Just out of curiosity: did you have a particular reason for changing
"""
tor"""
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.
comment:71 Changed 6 years ago by
 Branch changed from u/tscrim/pari_power_series15601 to 2c9cb8a5b1b7e7b2f36289f56f57fb50f7a1213d
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
two small fixes for PARI power series