Implementation of power series using PARI #15601

pjbruin · 2013-12-28T17:06:24Z

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.

Depends on #20062
Depends on #21755
Depends on #22210
Depends on #22212

Component: algebra

Keywords: pari series performance

Author: Peter Bruin

Branch/Commit: 2c9cb8a

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/15601

The text was updated successfully, but these errors were encountered:

pjbruin · 2013-12-28T17:54:12Z

Branch: u/pbruin/15601-power_series_pari

sagetrac-git · 2013-12-28T18:59:02Z

Commit: ad5bd7c

sagetrac-git · 2013-12-28T18:59:02Z

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

`ad5bd7c`	`two small fixes for PARI power series`

pjbruin · 2013-12-28T19:04:06Z

comment:3

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

sagetrac-git · 2013-12-28T20:55:28Z

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

`07f5508`	`fix infinite recursion in PowerSeries_pari.change_ring()`

sagetrac-git · 2013-12-28T20:55:28Z

Changed commit from ad5bd7c to 07f5508

sagetrac-git · 2013-12-30T13:54:13Z

Changed commit from 07f5508 to a709d12

sagetrac-git · 2013-12-30T13:54:13Z

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

`a709d12`	`speed improvements for PARI power series`

sagetrac-git · 2014-01-13T12:22:07Z

Changed commit from a709d12 to 7fc9291

sagetrac-git · 2014-01-13T12:22:07Z

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`

sagetrac-git · 2014-01-17T22:34:19Z

Changed commit from 7fc9291 to b796e06

sagetrac-git · 2014-01-17T22:34:19Z

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

`b796e06`	`Merge branch 'develop' into ticket/15601`

sagetrac-git · 2014-03-25T15:35:36Z

Changed commit from b796e06 to f287c7f

sagetrac-git · 2014-03-25T15:35:36Z

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

`f287c7f`	`Merge branch 'develop' into ticket/15601`

rwst · 2014-04-22T13:24:29Z

comment:10

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?

pjbruin · 2014-04-22T13:38:15Z

comment:11

Replying to @rwst:

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).

sagetrac-git · 2014-05-25T15:37:31Z

Changed commit from f287c7f to b9130ca

sagetrac-git · 2014-05-25T15:37:31Z

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

`b9130ca`	`Merge branch 'develop' into ticket/15601`

sagetrac-git · 2016-11-18T08:56:17Z

Changed commit from 968451d to 4c73d59

sagetrac-git · 2016-11-18T08:56:17Z

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)`

pjbruin · 2017-01-23T09:30:31Z

Changed dependencies from #20062, #21755 to #20062, #21755, #22210, #22212

pjbruin · 2017-01-23T09:30:31Z

Changed commit from 4c73d59 to 251a93b

pjbruin · 2017-01-23T09:30:31Z

Changed branch from u/pbruin/15601-power_series_pari to u/pbruin/15601-PowerSeries_pari

pjbruin · 2017-01-23T09:30:31Z

comment:65

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

sagetrac-git · 2017-01-25T10:50:58Z

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

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

sagetrac-git · 2017-01-25T10:50:58Z

Changed commit from 251a93b to ccfa224

sagetrac-git · 2017-01-26T07:32:34Z

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

`73e7364`	`Trac 15601: gen has been renamed to Gen`

sagetrac-git · 2017-01-26T07:32:34Z

Changed commit from ccfa224 to 73e7364

tscrim · 2017-01-28T23:59:32Z

Reviewer: Travis Scrimshaw

tscrim · 2017-01-28T23:59:32Z

Changed branch from u/pbruin/15601-PowerSeries_pari to u/tscrim/pari_power_series-15601

tscrim · 2017-01-28T23:59:32Z

Changed commit from 73e7364 to 2c9cb8a

tscrim · 2017-01-28T23:59:32Z

comment:68

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.`

pjbruin · 2017-01-30T06:32:03Z

comment:69

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 · 2017-01-30T06:41:07Z

comment:70

Replying to @pjbruin:

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.

vbraun · 2017-02-02T22:09:31Z

Changed branch from u/tscrim/pari_power_series-15601 to 2c9cb8a

pjbruin added this to the sage-6.1 milestone Dec 28, 2013

pjbruin added c: algebra labels Dec 28, 2013

pjbruin added the s: needs review label Dec 28, 2013

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014

pjbruin added the s: needs review label Oct 25, 2016

dimpase modified the milestones: sage-7.1, sage-7.5 Nov 18, 2016

tscrim modified the milestones: sage-7.5, sage-7.6 Jan 28, 2017

pjbruin added s: positive review and removed s: needs review labels Jan 30, 2017

vbraun removed the s: positive review label Feb 2, 2017

vbraun closed this as completed in 94d93d0 Feb 2, 2017

This was referenced Nov 2, 2016

Export sage.libs.pari.gen.new_ref() #21755

Closed

Remove obsolete special case in PARI gen.eval() #22210

Closed

Improve method PowerSeries._pari_() #22212

Closed

fchapoton mentioned this issue Dec 28, 2018

remove various old deprecated stuff #26866

Closed

Implementation of power series using PARI #15601

Implementation of power series using PARI #15601

Comments

pjbruin commented Dec 28, 2013

pjbruin commented Dec 28, 2013

sagetrac-git mannequin commented Dec 28, 2013

sagetrac-git mannequin commented Dec 28, 2013

pjbruin commented Dec 28, 2013

sagetrac-git mannequin commented Dec 28, 2013

sagetrac-git mannequin commented Dec 28, 2013

sagetrac-git mannequin commented Dec 30, 2013

sagetrac-git mannequin commented Dec 30, 2013

sagetrac-git mannequin commented Jan 13, 2014

sagetrac-git mannequin commented Jan 13, 2014

sagetrac-git mannequin commented Jan 17, 2014

sagetrac-git mannequin commented Jan 17, 2014

sagetrac-git mannequin commented Mar 25, 2014

sagetrac-git mannequin commented Mar 25, 2014

rwst commented Apr 22, 2014

pjbruin commented Apr 22, 2014

sagetrac-git mannequin commented May 25, 2014

sagetrac-git mannequin commented May 25, 2014

sagetrac-git mannequin commented Nov 18, 2016

sagetrac-git mannequin commented Nov 18, 2016

pjbruin commented Jan 23, 2017

pjbruin commented Jan 23, 2017

pjbruin commented Jan 23, 2017

pjbruin commented Jan 23, 2017

sagetrac-git mannequin commented Jan 25, 2017

sagetrac-git mannequin commented Jan 25, 2017

sagetrac-git mannequin commented Jan 26, 2017

sagetrac-git mannequin commented Jan 26, 2017

tscrim commented Jan 28, 2017

tscrim commented Jan 28, 2017

tscrim commented Jan 28, 2017

tscrim commented Jan 28, 2017

pjbruin commented Jan 30, 2017

tscrim commented Jan 30, 2017

vbraun commented Feb 2, 2017