Opened 12 years ago

Closed 15 months ago

Last modified 9 months ago

#4618 closed enhancement (fixed)

Puiseux series

Reported by: ljpk Owned by: AlexGhitza
Priority: minor Milestone: sage-9.1
Component: algebra Keywords: Puiseux, days100
Cc: mmezzarobba, vdelecroix, dkrenn Merged in:
Authors: Chris Swierczewski Reviewers: Travis Scrimshaw, Frédéric Chapoton, Sebastian Oehms
Report Upstream: N/A Work issues:
Branch: 99f43aa (Commits, GitHub, GitLab) Commit:
Dependencies: #24420, #24431, #28239 Stopgaps:

Status badges

Description (last modified by vdelecroix)

We provide an implementation of Puiseux series, that is power series in x^(1/n) where n is an arbitrary integer.

When the base ring is an algebraically closed field, this is an algebraically closed field. In other words, any polynomial in QQ[X,Y] has a solution in Y as a Puiseux series in X over QQbar.

Change History (78)

comment:1 Changed 12 years ago by mabshoff

Hi ljpk,

requests like this shouls always go to [sage-devel] too since people generally do not look for things to do in trac. Sending the same request to [sage-devel] will make people aware of the problem and might get some design discussion going. Obviously if you are working on code this is different, but if you expect someone else to do the dirty work a little advertisement cannot hurt :)

Cheers,

Michael

comment:2 Changed 12 years ago by AlexGhitza

  • Type changed from defect to enhancement

comment:3 Changed 11 years ago by AlexGhitza

  • Component changed from linear algebra to algebra
  • Owner changed from was to AlexGhitza
  • Report Upstream set to N/A

comment:4 Changed 10 years ago by kcrisman

See also #9555.

comment:5 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 7 years ago by chapoton

  • Keywords Puiseux added

comment:8 Changed 7 years ago by rws

  • Description modified (diff)

comment:9 Changed 7 years ago by rws

  • Description modified (diff)

comment:10 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:12 Changed 6 years ago by kcrisman

See also #9289.

comment:13 Changed 6 years ago by rws

  • Milestone changed from sage-6.4 to sage-wishlist

comment:15 Changed 5 years ago by cswiercz

As mentioned in an email correspondence with chapoton I believe my implementation of PuiseuxSeriesRing and PuiseuxSeriesRingElementto be pretty complete in regards to fitting into Sage's coercion model. Hopefully it will, at the very least, be a good starting point.

Thanks to chapoton for offering to plug this code into Sage!

On a side note, I also have some code for computing Puiseux series representations of places on a plane algebraic curve. The entry function is abelfunctions.puiseux_series.puiseux_series. I'm sure someone with better Sage skills than myself can improve the algorithm and plug that in as well.

comment:16 Changed 5 years ago by chapoton

  • Branch set to public/4618
  • Commit set to 7c6e9fbd65e4b19eed62d8cc8d8694659b49e996

just made a git branch, not tested at all


New commits:

7c6e9fbtrac #4618 creating a branch from Chris Swierczewski code

comment:17 Changed 5 years ago by git

  • Commit changed from 7c6e9fbd65e4b19eed62d8cc8d8694659b49e996 to a828db5df2268a20bea62b83033c2325f7cfeaca

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

a828db5trac #4618 details, not working yet

comment:18 Changed 5 years ago by git

  • Commit changed from a828db5df2268a20bea62b83033c2325f7cfeaca to 0e38712d192a35f9cf35d1c92e053b412ad8e940

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

0e38712trac #4618 now working

comment:19 Changed 5 years ago by git

  • Commit changed from 0e38712d192a35f9cf35d1c92e053b412ad8e940 to 8fe475bada98e8b7a2912693525f56d036dcaa10

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

8fe475btrac #4618, now working a little bit more, and added some doc

comment:20 Changed 5 years ago by git

  • Commit changed from 8fe475bada98e8b7a2912693525f56d036dcaa10 to 2e05bc8e741b8f943f4fedff664e24a1f8ba9bc7

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

5ecc828Merge branch 'public/4618' into 7.2.b1
2e05bc8trac #4618 some more doc, and removed puiseux.py

comment:21 Changed 5 years ago by mmezzarobba

  • Cc mmezzarobba added

comment:22 Changed 5 years ago by git

  • Commit changed from 2e05bc8e741b8f943f4fedff664e24a1f8ba9bc7 to 9af42db0e6db06161e484f318e456e664cbf9ebc

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

9af42dbtrac #4618 some more doc and tests

comment:23 Changed 5 years ago by git

  • Commit changed from 9af42db0e6db06161e484f318e456e664cbf9ebc to 98afe229b00ae434a5a2bd4849bf94081ff39bca

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

ec9dbc3Merge branch 'public/4618' into 7.2.rc1
98afe22puiseux series, more doc, moved a method to Laurent series

comment:24 Changed 4 years ago by mmarco

This is a nice addition. Is it ready for review?

A few comments:

  • Is it planned to extend it to the multivariate case?
  • It would be nice to add a more detailed mathematical explanation about what a Puiseux series is in the docstring.

comment:25 Changed 4 years ago by chapoton

It is probably not ready, there seems to be a bug lurking around.

No plan to implement the multivariate case.

and the coverage is not 100%

Last edited 4 years ago by chapoton (previous) (diff)

comment:26 Changed 3 years ago by vdelecroix

  • Cc vdelecroix added

comment:27 Changed 3 years ago by vdelecroix

This is needed to allow extend=True for the nth_root method in #10720 (see also this sage-devel thread).

comment:28 follow-up: Changed 3 years ago by vdelecroix

An innocent operation like the following will multiply the memory footprint by 24 with no change in information

sage: p = prod(1 - q^n + O(q^100) for n in range(1,100))   # fine: 100 * coeff size
sage: q^(1/24) * p   # bad: 100 * 24 * coeff size

The above example is the q-series expansion of the Dedekind eta function. There might be a more clever data structure to use as this kind of series is frequently encountered when dealing with modular forms.

comment:29 Changed 3 years ago by vdelecroix

  • Dependencies set to #24420, #24431

comment:30 Changed 3 years ago by vdelecroix

  • Description modified (diff)
  • Milestone changed from sage-wishlist to sage-8.2
  • Summary changed from Request for Puiseux series in SAGE to Puiseux series

comment:31 Changed 3 years ago by dkrenn

  • Cc dkrenn added

comment:32 Changed 2 years ago by git

  • Commit changed from 98afe229b00ae434a5a2bd4849bf94081ff39bca to a922e2acef3c871a23600de9d299d210673fcee4

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

927b88dMerge branch 'public/4618' of git://trac.sagemath.org/sage into puiseux_series_4618
a922e2atrac #4618: have it compile again and some corrections

comment:33 Changed 2 years ago by soehms

I do the following changes:

  1. Adaptation to current version 8.8.beta3 in order to have the code compile again.
  2. I replace the method _cmp_ of PuiseuxSeries by _richcmp_ and let it completely rely on the corresponding method of class LaurentSeries. The reason for this is not only modernisation, but also that the former method doesn't work correctly (for example comparison with zero returns wrong results).
  3. I add a specification of the representative of the Puiseux series inside the constructor of PuiseuxSeries in such a way that the ramification index is minimized. This improves the methods laurent_series and power_series (the examples given there would not work else-wise).
  4. I add more doctests.

There is still work to do, for example:

  1. There are several workarounds on other bugs in Sage. In general I think, these workarounds should be removed and the corresponding bugs should be treated in separate tickets. Examples:
    1. In the methods _repr_, exponents and coefficients there is the following comment: NOTE: self.__l.coefficients() is bugged when the coefficients are in QQbar but coerced into SR .... I have no idea how far it makes sense to consider Puiseux series (Laurent series, polynomial rings, ...) over the SymbolicRing. But since these constructions are possible, they should work (or should be blocked). There are simple examples where this is not the case:
      sage: PS = PolynomialRing(SR,'x')
      sage: P = PolynomialRing(QQ,'x')
      sage: q = P((1,1,5)); q
      5*x^2 + x + 1
      sage: p = PS(q)
      sage: p.coefficients()
      [5*x^2 + x + 1]
      sage: p in SR
      True
      
      Is this a known bug? Concerning the methods in question, I think that they should rely more directly on the according methods of LaurentSeries.
    2. In the method add_bigoh the following error is caught:
      sage: L.<x> = LaurentSeriesRing(QQ)
      sage: q = x^2 + x^3
      sage: q.add_bigoh(-1)
      Traceback (most recent call last):
      ...
      ValueError: prec (= -3) must be non-negative
      
      This should be fixed in LaurentSeries.
  1. I think we should clarify the following behavior of the method add_bigoh:
    sage: R.<x> = PuiseuxSeriesRing(ZZ)
    sage: p = x**(-1/3) + 2*x**(1/5)
    sage: p.add_bigoh(1/2)
    x^(-1/3) + 2*x^(1/5) + O(x^(7/15))
    
    is this acceptable?
  1. The method _repr_ needs work:
    sage: R.<x> = PuiseuxSeriesRing(Zp(5))
    sage: x**(1/2) + 5 * x^(1/3)
    5 + O(5^21)*x^(1/3) + (1 + O(5^20))*x^(1/2)
    
  1. Further doctests are needed.
  2. Integration into documentation.

I will continue to work on this ticket according to feedback!

comment:34 Changed 21 months ago by soehms

  • Keywords days100 added

comment:35 Changed 21 months ago by vdelecroix

  • Milestone changed from sage-8.2 to sage-8.9

comment:36 follow-up: Changed 21 months ago by chapoton

There is a hash doctest failure with python3:

sage -t --long src/sage/rings/puiseux_series_ring_element.pyx
**********************************************************************
File "src/sage/rings/puiseux_series_ring_element.pyx", line 549, in sage.rings.puiseux_series_ring_element.PuiseuxSeries.__hash__
Failed example:
    hash(p)  # indirect doctest
Expected:
    -15360174648385722
Got:
    8039939419124139326

comment:37 Changed 21 months ago by soehms

In agreement with Frédéric I have created the tickets #28238 and #28239 to treat the external bugs mentioned in comment 32. The according workarounds in the code can be removed.

comment:38 in reply to: ↑ 36 Changed 21 months ago by soehms

Replying to chapoton:

There is a hash doctest failure with python3:

sage -t --long src/sage/rings/puiseux_series_ring_element.pyx
**********************************************************************
File "src/sage/rings/puiseux_series_ring_element.pyx", line 549, in sage.rings.puiseux_series_ring_element.PuiseuxSeries.__hash__
Failed example:
    hash(p)  # indirect doctest
Expected:
    -15360174648385722
Got:
    8039939419124139326

I will look at that at home (since I have no sage with python3 on the computer I am carrying with me)!

comment:39 Changed 21 months ago by git

  • Commit changed from a922e2acef3c871a23600de9d299d210673fcee4 to 506d2dce9874e9bd913a04928cb60da9e168ccda

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

afb0accMerge branch 'public/4618' of git://trac.sagemath.org/sage into puiseux_series_4618
506d2dc4618: fixing doctest of __hash__ and remove workaround for #28239

comment:40 in reply to: ↑ 28 ; follow-ups: Changed 21 months ago by vdelecroix

Replying to vdelecroix:

An innocent operation like the following will multiply the memory footprint by 24 with no change in information

sage: p = prod(1 - q^n + O(q^100) for n in range(1,100))   # fine: 100 * coeff size
sage: q^(1/24) * p   # bad: 100 * 24 * coeff size

The above example is the q-series expansion of the Dedekind eta function. There might be a more clever data structure to use as this kind of series is frequently encountered when dealing with modular forms.

Concerning this example, you might want to read https://oscar.computeralgebra.de/blogs/2018/08/03/PuiseuxSeries/

comment:41 Changed 21 months ago by git

  • Commit changed from 506d2dce9874e9bd913a04928cb60da9e168ccda to e0c03113eaa38ec5ce101d16332b81ecf9ce70d8

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

e0c03114618: remove workaround for #28238 and add a Note to add_bigoh

comment:42 in reply to: ↑ 40 Changed 21 months ago by soehms

Replying to vdelecroix:

Replying to vdelecroix:

An innocent operation like the following will multiply the memory footprint by 24 with no change in information

sage: p = prod(1 - q^n + O(q^100) for n in range(1,100))   # fine: 100 * coeff size
sage: q^(1/24) * p   # bad: 100 * 24 * coeff size

The above example is the q-series expansion of the Dedekind eta function. There might be a more clever data structure to use as this kind of series is frequently encountered when dealing with modular forms.

Concerning this example, you might want to read https://oscar.computeralgebra.de/blogs/2018/08/03/PuiseuxSeries/

The multiplication of memory-size is caused by the call of the V-method (implemented for Puiseux series) in the Laurent series class but it happens in the polynomial attached to the power series of the attached Laurent series.

sage: P.<q> = PuiseuxSeriesRing(QQ)
sage: p = prod((1 - q^n).add_bigoh(100) for n in range(1,100))
sage: t = q^(1/24) * p
sage: s = t.laurent_part().valuation_zero_part().polynomial()
sage: len(s.list())
2209
sage: len(p.laurent_part().valuation_zero_part().polynomial().list())
93

So the most generic option would be to implement a data-compression in the corresponding polynomial class. But this may involve external software as in the case of the example:

sage: type(s)
<type 'sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint'>

The same thing is true concerening the level of power series (for exmaple choosing implementation='pari'). So I think, the best place for implementing a smarter data structure would be the Laurent series class and could be done there by a scale factor as it is mentined in the article concerning the implementation in OSCAR: "Laurent series themselves are also stored with a valuation, precision and a scale factor".

My suggestion is, to open a new ticket on that task concerning such an implementation for the Laurent series. The method V should than just change the scale factor (instead of stretching the data volume). The implementaion of the Puiseux series could stay as it is. In opposite to ramifications_index to new scale factor could be named covering_index, for instance.

BTW: what does this V stand for?

comment:43 follow-up: Changed 21 months ago by chapoton

I think that V stand for Verschiebung.

comment:44 in reply to: ↑ 43 ; follow-up: Changed 21 months ago by soehms

Replying to chapoton:

I think that V stand for Verschiebung.

That sounds as if we should look for a better name! I even don't see a connection. The only mathematical meaning of Verschiebung I know is that of a translation in euclidean geometry. What about to replace V by power_inflation?

comment:45 in reply to: ↑ 44 ; follow-up: Changed 20 months ago by kcrisman

Replying to soehms:

Replying to chapoton:

I think that V stand for Verschiebung.

That sounds as if we should look for a better name! I even don't see a connection. The only mathematical meaning of Verschiebung I know is that of a translation in euclidean geometry.

It is probably from Witt vector terminology, where that is a standard term?

comment:46 in reply to: ↑ 45 Changed 20 months ago by soehms

  • Status changed from new to needs_info

Replying to kcrisman:

Replying to soehms:

Replying to chapoton:

I think that V stand for Verschiebung.

That sounds as if we should look for a better name! I even don't see a connection. The only mathematical meaning of Verschiebung I know is that of a translation in euclidean geometry.

It is probably from Witt vector terminology, where that is a standard term?

Thanks for the explanation! Indeed, that meaning of Verschiebung hasn't been present in my mind. But anyway, I would prefer a method name that doesn't dependent on any special context (and has more than just one letter). The V could by kept as an alias (together with an appropriate explanation). Opinions?

comment:47 Changed 16 months ago by git

  • Commit changed from e0c03113eaa38ec5ce101d16332b81ecf9ce70d8 to 637cf8622d84158c6120ba92381676f9d937455c

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

33bf6afMerge branch 'public/4618' of git://trac.sagemath.org/sage into public/4618
637cf86Updating the framework to use UniqueRepresentation and a few other misc changes.

comment:48 Changed 16 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

I added a long form verschiebung to the Laurent series with V as an alias. I also brought the class up to our current framework with UniqueRepresentation and better use of the category framework. I also fixed a bunch of places in the doc and other misc code changes. There are still some doctests missing, but code-wise I think this is acceptable for inclusion (we can always make additional changes later).

Although there is a substantial overlap with the code for Laurent series. I almost feel like we should just extend the Laurent series class with the necessary features with _e to avoid duplication (that one extra little bit of information shouldn't change the speed or have a real affect on memory).

comment:49 Changed 16 months ago by git

  • Commit changed from 637cf8622d84158c6120ba92381676f9d937455c to c18596e7831a8f050221f0069b1397e4fc81341c

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

c18596e4618: some more fixes and doctests

comment:50 follow-up: Changed 16 months ago by soehms

  • Authors set to Chris Swierczewski
  • Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Frédéric Chapoton, Sebastian Oehms
  • Status changed from needs_info to needs_review

Thanks for bringing this ahead that much, Travis!

The only tasks being left from my comment #33 are 3) and 5). With respect to the former item I rewrite _repr_ such that it just transforms the representation string of the corresponding Laurent series. Concerning the latter I include the docs. They look well formatted.

Furthermore I add some more doctests and fix the bugs I've detected along that. The verschiebung method did allow negative input on finite precision. I fixed that, as well. I've just realized that the V method in the PowerSeries-class is previous code. So, the naming has been overtaken from there. Shall we introduce the alias there, as well?

Furthermore, I think we could speed up these methods (in LaurentSeries and PowerSeries) replacing the operations on the coefficient list by operations on the corresponding dictionaries. I made some tests and observed improvements up to 250 times faster. Shall I work that out?

Although there is a substantial overlap with the code for Laurent series. I almost feel like we should just extend the Laurent series class with the necessary features with _e to avoid duplication (that one extra little bit of information shouldn't change the speed or have a real affect on memory).

Do you mean to make the Laurent series be Puiseux series with ramification index 1? I like this idea, but wouldn't this lead to larger changes in the Laurent series classes? Shall we deal with that in this ticket?

comment:51 in reply to: ↑ 40 Changed 16 months ago by soehms

Replying to vdelecroix:

Replying to vdelecroix:

An innocent operation like the following will multiply the memory footprint by 24 with no change in information

sage: p = prod(1 - q^n + O(q^100) for n in range(1,100))   # fine: 100 * coeff size
sage: q^(1/24) * p   # bad: 100 * 24 * coeff size

The above example is the q-series expansion of the Dedekind eta function. There might be a more clever data structure to use as this kind of series is frequently encountered when dealing with modular forms.

Concerning this example, you might want to read https://oscar.computeralgebra.de/blogs/2018/08/03/PuiseuxSeries/

Vincent, I had a look at that problem, again. Did you declare a sparse PuiseuxSeriesRing? How did you measure the consumption of memory? Declaring a sparse ring at least produces a 9 times smaller dump string:

sage: P.<q> = PuiseuxSeriesRing(ZZ)
sage: p = prod((1 - q^n).add_bigoh(100) for n in range(1,100))
sage: t = q^(1/24) * p
sage: len(p.dumps())
826
sage: len(t.dumps())
8688

sage: P.<q> = PuiseuxSeriesRing(ZZ, sparse=True)
sage: p = prod((1 - q^n).add_bigoh(100) for n in range(1,100))
sage: t = q^(1/24) * p
sage: len(p.dumps())
903
sage: len(t.dumps())
923

I think, it would make sense to have the default on sparse to be True in the case of Puiseux series, since for non trivial ramification index its attached Laurent series is sparse by construction.

Btw, in the blog you have linked to the ticket William Bruce Hart seems to have worked out his 'SageMath example' using a dense representation (see for example R.<q> = PowerSeriesRing(ZZ, default_prec=9001) and this citation "Because of the dense representation in Sage, this would kill performance"). A reason for this choice is not given. I guess that Sage would have produced better scores with a sparse representation.

comment:52 in reply to: ↑ 50 ; follow-up: Changed 16 months ago by tscrim

Replying to soehms:

The only tasks being left from my comment:33 are 3) and 5). With respect to the former item I rewrite _repr_ such that it just transforms the representation string of the corresponding Laurent series. Concerning the latter I include the docs. They look well formatted.

I didn't see your comment when I was making my changes. Thank you for taking care of it.

Furthermore I add some more doctests and fix the bugs I've detected along that. The verschiebung method did allow negative input on finite precision. I fixed that, as well. I've just realized that the V method in the PowerSeries-class is previous code. So, the naming has been overtaken from there. Shall we introduce the alias there, as well?

That would be something for a separate ticket (well, ideally adding such methods to the Laurent series should be done on another ticket as well, but it was already included here so, I continued to be lazy about it).

Furthermore, I think we could speed up these methods (in LaurentSeries and PowerSeries) replacing the operations on the coefficient list by operations on the corresponding dictionaries. I made some tests and observed improvements up to 250 times faster. Shall I work that out?

Please do, although that might depend on the sparsity too. However, I leave it to people who are more expert in the area to determine whether or not the default should be sparse or not.

Although there is a substantial overlap with the code for Laurent series. I almost feel like we should just extend the Laurent series class with the necessary features with _e to avoid duplication (that one extra little bit of information shouldn't change the speed or have a real affect on memory).

Do you mean to make the Laurent series be Puiseux series with ramification index 1? I like this idea, but wouldn't this lead to larger changes in the Laurent series classes? Shall we deal with that in this ticket?

Yes, that is correct. It shouldn't require many changes I would think as it should be a matter of just (re)moving methods from the Laurent series and setting the Laurent series as a subclass. However, I haven't looked too closely at it.

comment:53 in reply to: ↑ 52 Changed 16 months ago by soehms

Replying to tscrim:

Replying to soehms:

Furthermore, I think we could speed up these methods (in LaurentSeries and PowerSeries) replacing the operations on the coefficient list by operations on the corresponding dictionaries. I made some tests and observed improvements up to 250 times faster. Shall I work that out?

Please do, although that might depend on the sparsity too. However, I leave it to people who are more expert in the area to determine whether or not the default should be sparse or not.

In the meantime I've realized, that it isn't a good idea to have sparse=True as the default, since inversion (explicitly the method inverse_series_trunc) becomes very slow for this setting. Probably that's the reason why William Bruce Hurt worked with the dense representation.

comment:54 Changed 16 months ago by embray

  • Milestone changed from sage-8.9 to sage-9.1

Ticket retargeted after milestone closed

comment:55 Changed 15 months ago by git

  • Commit changed from c18596e7831a8f050221f0069b1397e4fc81341c to 9b06df9fe48da577b5e4d22d352d049ed6f7a778

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

e46101dMerge branch 'public/4618' of git://trac.sagemath.org/sage into puiseux_series_4618
9a3554128239: initial version
07a2e34Merge branch 'u/soehms/neg_prec_laurent_series_28239' of git://trac.sagemath.org/sage into puiseux_series_4618
9b06df94618: add keyword prec to _element_constructor_ and include Puiseux series in bigoh

comment:56 Changed 15 months ago by soehms

  • Dependencies changed from #24420, #24431 to #24420, #24431, #28239

I do the following changes:

  1. I add a dependency to ticket #28239, since this bug of the Laurent series, becomes much more relevant for Puiseux series.
  1. I add the keyword prec to the _element constructor_, to achieve compatibility with the power series (see ticket #28993, but observe that my implementation is independent of that ticket).
  1. I let the Puiseux series be recognized by the global bigoh function O.
  1. I add the still missing doctests and do related small fixes.
  1. I insert missing copyright notes.

Concerning the introduction of a scale factor according to comment 42, I've opened ticket #28992.

comment:57 Changed 15 months ago by git

  • Commit changed from 9b06df9fe48da577b5e4d22d352d049ed6f7a778 to 4ccc93f7947d6c9b0babe12c09cc828886abf766

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

4ccc93f4618: fix python2 import error and non ascii

comment:58 follow-up: Changed 15 months ago by tscrim

The EXAMPLES:: in _coerce_map_from_ needs a blank line after it. Also, you are not passing prec in the _element_constructor_ it seems. There might be some more comments later on.

We can include this implementation in since it is mostly in good shape without #28992 and then make the relevant changes here in that ticket. It would be good to at least have some implementation of Puiseux series, which we can then improve upon later.

comment:59 Changed 15 months ago by git

  • Commit changed from 4ccc93f7947d6c9b0babe12c09cc828886abf766 to da3718d67462656efd2fa023ba83a3c308920b60

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

da3718d4618: small doc fixes according to review

comment:60 in reply to: ↑ 58 Changed 15 months ago by soehms

Replying to tscrim:

We can include this implementation in since it is mostly in good shape without #28992 and then make the relevant changes here in that ticket. It would be good to at least have some implementation of Puiseux series, which we can then improve upon later.

I agree! Shall we switch to positive review, now?

comment:61 Changed 15 months ago by tscrim

Unfortunately I have some more comments that I think should be addressed before a positive review:

In _coerce_map_from_:

         EXAMPLES::
+
             sage: R.<x> = PuiseuxSeriesRing(ZZ)

Also, some small doc tweaks:

 cdef class PuiseuxSeries(AlgebraElement):
     r"""
+    A Puiseux series.
+
     We store a Puiseux series

Common practice is to have the __init__ be the first method, and all of its doc should be moved to the class-level doc (with some formatting improvements done) with a TestSuite(foo).run() being in the __init__'s docstring.

IIRC long is going away in Python3, and better overall I think would be a size_t for the _e attribute. Also, since _l is a Laurent series, shouldn't it also be a LaurentSeries object.

Why also is laurent_part a @property and not just a normal method? (I think p.laurent_part() is actually wrong because of this and should be p.laurent_part, but that is moot if that changes.)

Probably good idea to break encapsulation and not have the function call here: return self._l.laurent_polynomial()(t) (i.e., just access the underlying polynomial).

For the _richcmp_, I think it would be a good idea to not call V on the underlying Laurent polynomials and instead implement a proper comparison as this will be significantly faster.

I think we should change the MIT license to our standard license. I believe this is compatible.

comment:62 Changed 15 months ago by git

  • Commit changed from da3718d67462656efd2fa023ba83a3c308920b60 to 485102c85493c40bbc67f56a7ab25d2d3ac7fc44

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

485102c4618: corrections according to reviewers suggestions

comment:63 Changed 15 months ago by soehms

All your suggestions seem to be reasonable to me.

comment:64 follow-up: Changed 15 months ago by tscrim

Thank you. Some last little things: all INPUT: blocks should not end in a period/full-stop (unless it is really long). Also these specific changes:

         - ``prec`` -- (default: ``infinity``) the precision of the series
-            as a rational number.
+          as a rational number
-    - ``parent`` -- Ring, the target parent.
+    - ``parent`` -- the parent ring
 
     - ``f``  -- one of the following types of inputs:
-        - instance of :class:`PuiseuxSeries`
-        - instance that can be coerced into the Laurent sersies ring of the parent.
+
+      * instance of :class:`PuiseuxSeries`
+      * instance that can be coerced into the Laurent series ring of the parent
 
-    - ``e`` -- integer (optional, default 1) for setting the ramification index.
+    - ``e`` -- integer (default: 1); the ramification index
     def __init__(self, parent, f, e=1):
         r"""
+        Initialize ``self``.
+
-        TESTS:
+        TESTS::
-Applies :meth:`shift` using the operator `<<`
+Apply :meth:`shift` using the operator `<<`.

comment:65 Changed 15 months ago by git

  • Commit changed from 485102c85493c40bbc67f56a7ab25d2d3ac7fc44 to 99f43aab805490868299fa16d2b8f7e57d7e8003

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

99f43aa4618: docstring formatting

comment:66 in reply to: ↑ 64 Changed 15 months ago by soehms

Replying to tscrim:

Thank you. Some last little things:

Done!

comment:67 Changed 15 months ago by tscrim

  • Status changed from needs_review to positive_review

Thank you. Positive review.

comment:68 Changed 15 months ago by soehms

Thanks a lot, as well!

comment:69 Changed 15 months ago by vbraun

  • Branch changed from public/4618 to 99f43aab805490868299fa16d2b8f7e57d7e8003
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:70 follow-up: Changed 9 months ago by slelievre

  • Commit 99f43aab805490868299fa16d2b8f7e57d7e8003 deleted

Did this also solve #9289 (Implement Puiseux polynomials)?

comment:71 in reply to: ↑ 70 ; follow-up: Changed 9 months ago by tscrim

Replying to slelievre:

Did this also solve #9289 (Implement Puiseux polynomials)?

Implicitly, but not really since we should have a dedicated parent and element for the polynomials.

comment:72 in reply to: ↑ 71 Changed 9 months ago by soehms

Replying to tscrim:

Replying to slelievre:

Did this also solve #9289 (Implement Puiseux polynomials)?

Implicitly, but not really since we should have a dedicated parent and element for the polynomials.

But maybe it's a good idea to have the implementation of the Puiseux polynomial rely as much as possible on the Puiseux series. That would avoid having a lot of duplicated code. At the moment the code attached to ticket #9289 is not far away from being copy pasted from the corresponding classes for Laurent polynomials with some name refactoring done. So we would not loose that much if we decide to implement the Puiseux polynomials as "restricted Puiseux series".

What is standing against that?

comment:73 follow-up: Changed 9 months ago by tscrim

That would work, but it would likely be slow. I think the thing to do is follow the same pattern as here: extend the Laurent polynomials by wrapping them as a Puiseux polynomial with the ramification index and associated methods. Perhaps to avoid some code duplication, one could be clever with a template class or common ABC.

comment:74 in reply to: ↑ 73 Changed 9 months ago by soehms

Replying to tscrim:

That would work, but it would likely be slow.

Travis, I don't see the point of what would make that noticeable slower. I think all calculation that could harm performance will be executed inside polynomial classes independent on how we translate it to them. A little bit more time used for the translation because there is one step more cannot amount that much.

What I have in mind is similar to how I did the embedding of the localization into the fraction field (via a value attribute). In the meantime I've seen that there is a special class ElementWrapper for such constructions (I hadn't been aware of it when implementing the localization).

comment:75 follow-up: Changed 9 months ago by tscrim

It is a bit more than that one step. IIRC, there are also a lot more optimizations than can and are done for polynomials that are not available for power series. For one, they don't have to worry about precision. So arithmetic starts to get bogged down by this. Plus that extra level of indirection does add a bit of time (also in creating the extra elements, which is much slower than the function call). While it is not much, perhaps 2-5%, because arithmetic operations are often used in tight loops (and frequently), this can have an outsized impact on algorithm run times.

comment:76 in reply to: ↑ 75 Changed 9 months ago by soehms

Replying to tscrim:

Thanks for the explanations! I will think about your suggestion to capsule common functionalities in a template class. Do you mean a class that will be put in between CommutativeAlgebraElement and PuiseuxPolynomial repectively in between AlgebraElement and PuiseuxSeries? But maybe, we should have done #28992 before.

BTW: is there a special reason why the series are not inherited from CommutativeAlgebraElement?

comment:77 Changed 9 months ago by tscrim

There is the Polynomial class IIRC, but between that and PuiseuxPolynomial, yes. It would mostly be the Laurent polynomial code with the rammification index, but for the more time critical operations, it would just use the fact that the index is 1. Hopefully this would be minimal, but definitely all of the arithmetic operations would fall under this.

comment:78 Changed 9 months ago by tscrim

I also don't remember if there was some specific reason why it doesn't.

Note: See TracTickets for help on using tickets.