Opened 14 years ago

Closed 12 years ago

#4376 closed enhancement (fixed)

Implement conversion of power series over more rings (e.g. GF(p)) to pari

Reported by: John Cremona Owned by: William Stein
Priority: major Milestone: sage-4.7
Component: interfaces Keywords: power series pari gp
Cc: salmanhb@…, David Loeffler, Niles Johnson, Jeroen Demeyer Merged in: sage-4.7.alpha3
Authors: Francis Clarke, Jeroen Demeyer Reviewers: Marco Streng, Jeroen Demeyer, Niles Johnson
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Marco Streng)

salmanhb@… would like to be able to do linear algebra over GF(p)[[X]] using pari, but currently conversion of power series in R[[X]] to pari is only implemented when R=QQ or R=ZZ (via strings).

We should improve the _pari_() function for power series rings to allow R to be any ring in which pari conversion is already defined.

Depends on #7644

Attachments (3)

trac_4376.patch (5.5 KB) - added by Francis Clarke 12 years ago.
4376_no_strings.patch (1.7 KB) - added by Jeroen Demeyer 12 years ago.
Apply on top of previous patch
4376_reversion_fixes.patch (3.1 KB) - added by Francis Clarke 12 years ago.
Apply after previous two patches

Download all attachments as: .zip

Change History (21)

comment:1 Changed 12 years ago by Francis Clarke

Report Upstream: N/A
Status: newneeds_review

Currently pari conversion doesn't even work for series with integer coefficients. This was pointed out in the docstring for sage.modular.overconvergent.genus0.OverconvergentModularFormElement._pari_.

The attached patch extends the range of possible base rings significantly, but is still limited by what sage.rings.polynomial.polynomial_element.Polynomial._pari_ can do; see its extensive docstring.

Changed 12 years ago by Francis Clarke

Attachment: trac_4376.patch added

comment:2 Changed 12 years ago by Francis Clarke

Cc: David Loeffler added

comment:3 Changed 12 years ago by Niles Johnson

Cc: Niles Johnson added

comment:4 Changed 12 years ago by Niles Johnson

I wonder if making a new comment will get Patch Buildbot to look at this . . .

comment:5 Changed 12 years ago by Marco Streng

Status: needs_reviewneeds_info

Applies and builds without any problems on top of 4.6.1.alpha2 on the machine that I tried it on. All tests pass, the code looks good, and the patch seems to do what it says.

I would have made it "positive review", but then there is the new "Buildbot" link at the top of this page, which says "TestsFailed? ..."

What should I do with that?

comment:6 Changed 12 years ago by Luis Felipe Tabera Alonso

Status: needs_infoneeds_review

The buildbot is a tool to help you. If you check the fail. You will see that the tests that fail are stratup.py and setup0.py. These two are failing in all tickets, the fail does not have to do with this ticket. So if you have checked that the code is ok and your tests pass, feel free to give a positive review.

comment:7 Changed 12 years ago by Marco Streng

Authors: Francis Clarke
Reviewers: Marco Streng
Status: needs_reviewpositive_review

comment:8 Changed 12 years ago by Jeroen Demeyer

Cc: Jeroen Demeyer added
Keywords: gp added
Milestone: sage-4.6.1sage-4.6.2

As a possible follow-up, we should also implement/check conversion to GP.

comment:9 Changed 12 years ago by Jeroen Demeyer

Status: positive_reviewneeds_work

Test failures on sage-4.6.2.alpha1:

sage -t  "devel/sage/sage/rings/power_series_poly.pyx"
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/devel/sage/sage/rings/power_series_poly.pyx", line 766:
    sage: g = f.reversion(); g
Expected:
    1/(2*b)*t - 1/(8*b^2)*t^2 + ((-3*b + 1)/(16*b^3))*t^3 + O(t^4)
Got:
    O(t^4)
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/devel/sage/sage/rings/power_series_poly.pyx", line 770:
    sage: f(g)
Expected:
    t + O(t^4)
Got:
    O(t^4)
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/devel/sage/sage/rings/power_series_poly.pyx", line 772:
    sage: g(f)
Expected:
    t + O(t^4)
Got:
    0
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/devel/sage/sage/rings/power_series_poly.pyx", line 779:                                      sage: b = a.reversion(); b                                                                                                            Exception raised:                                                                                                                             Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_32[31]>", line 1, in <module>
        b = a.reversion(); b###line 779:
    sage: b = a.reversion(); b
      File "power_series_poly.pyx", line 847, in sage.rings.power_series_poly.PowerSeries_poly.reversion (sage/rings/power_series_poly.c:6881)
      File "gen.pyx", line 9851, in sage.libs.pari.gen._pari_trap (sage/libs/pari/gen.c:46023)
    PariError:  (20)
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/devel/sage/sage/rings/power_series_poly.pyx", line 781:
    sage: a(b)
Expected:
    t + O(t^6)
Got:
    b^5 + 6*b^4 + b^2 + b
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/sage-4.7.alpha0/devel/sage/sage/rings/power_series_poly.pyx", line 783:
    sage: b(a)
Expected:
    t + O(t^6)
Got:
    t + t^2 + 6*t^4 + t^5 + O(t^6)
**********************************************************************

Changed 12 years ago by Jeroen Demeyer

Attachment: 4376_no_strings.patch added

Apply on top of previous patch

comment:10 Changed 12 years ago by Jeroen Demeyer

Authors: Francis ClarkeFrancis Clarke, Jeroen Demeyer

The attached patch removes the conversion PARI -> string -> PARI. It does not address the doctest failures.

comment:11 in reply to:  9 Changed 12 years ago by Francis Clarke

Replying to jdemeyer:

Test failures on sage-4.6.2.alpha1: ...

What's happened is that #7644 means that many more series can be converted to Pari and reversion performed using sereverse. But when the degree-one coefficient is not a unit, converting the result back to Sage has exposed the following problem:

sage: P.<x> = Q[]
sage: Q = P.fraction_field()
sage: Q(1/x)
1/x
sage: Q(pari(1/x))
0

This is caused by

sage: P(pari(1/x))
0

whereas P(1/x) raises TypeError: denominator must be a unit.

The other group of failures is caused when conversion to a Pari series is successful but reversion raises a Pari error.

I will shortly post a patch which sorts these difficulties out. I've added a doctest for reversion in order to provide another example where Pari fails and the Lagrange inversion code needs to be used.

comment:12 Changed 12 years ago by Francis Clarke

Status: needs_workneeds_review

The attached patch makes the changes made in the previous patchescompatible with those made in #7644.

comment:13 Changed 12 years ago by Marco Streng

Description: modified (diff)
Status: needs_reviewneeds_work

On lines 316 and 317 of sage/rings/polynomial/polynomial_ring.py, you write

except (NotImplementedError, ValueError): 
    raise TypeError, "denominator must be a unit" 

I don't think a NotImplementedError should lead to a TypeError: that would give a lot of confusion.

Otherwise, this all looks very good.

(this ticket now depends on #7644)

comment:14 Changed 12 years ago by Jeroen Demeyer

I'm wondering if we shouldn't simply do

if x.type() == 't_RFRAC':
    raise TypeError, "denominator must be a unit"

I doubt that a PARI RFRAC can ever have a denominator which *is* a unit.

Changed 12 years ago by Francis Clarke

Attachment: 4376_reversion_fixes.patch added

Apply after previous two patches

comment:15 in reply to:  14 Changed 12 years ago by Francis Clarke

Status: needs_workneeds_review

Replying to jdemeyer:

... I doubt that a PARI RFRAC can ever have a denominator which *is* a unit.

I agree. So I've replaced the patch with one which implements your suggestion.

comment:16 Changed 12 years ago by Jeroen Demeyer

Reviewers: Marco StrengMarco Streng, Jeroen Demeyer

Francis: your patches look fine to me. Can somebody review my patch and give this ticket positive review?

comment:17 Changed 12 years ago by Niles Johnson

Reviewers: Marco Streng, Jeroen DemeyerMarco Streng, Jeroen Demeyer, Niles Johnson
Status: needs_reviewpositive_review

4376_no_strings.patch looks good: it accomplishes the same thing as the "with strings" version of the code, but skips the step of converting a pari polynomial to a string and then back to a pari polynomial. The patch includes some good corner-case tests, and a comment referencing the ticket number and what's being fixed.

Therefore, positive review for this patch. If I understand the above correctly, the other patches here have already been positively reviewed, so I'm switching the whole ticket to positive review.

comment:18 Changed 12 years ago by Jeroen Demeyer

Merged in: sage-4.7.alpha3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.