Opened 3 years ago
Last modified 3 years ago
#27347 closed enhancement
Lazy laurent series — at Version 25
Reported by:  klee  Owned by:  

Priority:  minor  Milestone:  sage8.8 
Component:  algebra  Keywords:  
Cc:  Merged in:  
Authors:  Kwankyu Lee  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/klee/27347 (Commits, GitHub, GitLab)  Commit:  e12fd5b6511f90ccb9b5b7bc59cb61e30d75cc93 
Dependencies:  Stopgaps: 
Description (last modified by )
Introduce lazy Laurent series to Sage.
A lazy Laurent series computes coefficients only when demanded or needed. In a sense, lazy Laurent series are Laurent series of infinite precision.
A generating function example from the code:
Generating functions are laurent series over the integer ring:: sage: from sage.rings.lazy_laurent_series_ring import LazyLaurentSeriesRing sage: L = LazyLaurentSeriesRing(ZZ, 'z') This defines the generating function of Fibonacci sequence:: sage: def coeff(s, i): ....: if i in [0, 1]: ....: return 1 ....: else: ....: return s.coefficient(i  1) + s.coefficient(i  2) ....: sage: f = L.series(coeff, valuation=0); f 1 + z + 2*z^2 + 3*z^3 + 5*z^4 + 8*z^5 + 13*z^6 + ... The 100th element of Fibonacci sequence can be obtained from the generating function:: sage: f.coefficient(100) 573147844013817084101
Lazy Laurent series is of course useful for other things. This will be used to implement infinite precision Laurent series expansion of algebraic functions in function fields, as a sequel to #27418.
Change History (25)
comment:1 Changed 3 years ago by
 Branch set to u/klee/27347
comment:2 Changed 3 years ago by
 Commit set to 5d24a347b3f5bd6273bf678958c94d18b273b28f
comment:3 Changed 3 years ago by
 Status changed from new to needs_review
comment:4 Changed 3 years ago by
 Commit changed from 5d24a347b3f5bd6273bf678958c94d18b273b28f to ace42826cd8782e1aee3c596707b33f5102291d6
Branch pushed to git repo; I updated commit sha1. New commits:
ace4282  pyflakes fixes

comment:5 Changed 3 years ago by
 Commit changed from ace42826cd8782e1aee3c596707b33f5102291d6 to 389798e1d7057545c7914f1456e32f9c47aff5be
Branch pushed to git repo; I updated commit sha1. New commits:
389798e  Add series method

comment:6 Changed 3 years ago by
 Commit changed from 389798e1d7057545c7914f1456e32f9c47aff5be to 43ba7859f92d707e2f6f3cf93aafbc4f7f4b453a
Branch pushed to git repo; I updated commit sha1. New commits:
43ba785  Small fixes on docstrings

comment:7 Changed 3 years ago by
 Description modified (diff)
comment:8 Changed 3 years ago by
 Milestone changed from sage8.7 to sage8.8
Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)
comment:9 Changed 3 years ago by
 Commit changed from 43ba7859f92d707e2f6f3cf93aafbc4f7f4b453a to e7ff9993551778c67c6a6168f0e26c5943f14925
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
e7ff999  Add lazy laurent series

comment:10 Changed 3 years ago by
 Commit changed from e7ff9993551778c67c6a6168f0e26c5943f14925 to 15e1b1c671d61ef279f1c32a715ddd56a2fa7997
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
15e1b1c  Add lazy laurent series

comment:11 Changed 3 years ago by
 Commit changed from 15e1b1c671d61ef279f1c32a715ddd56a2fa7997 to f70fca8e3303c51b98c3f9311da277fd954b1ebe
Branch pushed to git repo; I updated commit sha1. New commits:
f70fca8  Add __bool__

comment:12 followups: ↓ 13 ↓ 17 ↓ 18 Changed 3 years ago by
Some comments:
Is there a reason why you do not use the LazyPowerSeriesRing
for the main element (with a nonzero constant term until the whole series is zero) and then just store the valuation? This is how things are done for the Laurent polynomials. That way there is less duplication of code and improvements to one improve both.
Why do you override __eq__
and not use the one provided by Element
and the coercion framework? It is more flexible and allows you do implement comparisons (if you want) all in one function of _richcmp_
.
Do not have bare except:
statements (see coefficient
).
Does the elements pickle? I am a little worried that the addition of two power series will not pickling because of the little helper add
function. You should add a loads(dumps(foo))
test if it does work.
Typo laurent
> Laurent
(it is proper noun).
if len(s) == 0:
> if not s:
comment:13 in reply to: ↑ 12 Changed 3 years ago by
 Status changed from needs_review to needs_work
Replying to tscrim:
Is there a reason why you do not use the
LazyPowerSeriesRing
for the main element (with a nonzero constant term until the whole series is zero) and then just store the valuation? This is how things are done for the Laurent polynomials. That way there is less duplication of code and improvements to one improve both.
I looked into the LazyPowerSeriesRing
many years ago:
I think I didn't like it in several ways :) Still I don't understand this behavior:
sage: L.<t>=LazyPowerSeriesRing(QQ) sage: s=L([0,0,1,2]) sage: s.coefficient(0) 0 sage: s.coefficient(1) 0 sage: s.coefficient(2) 1 sage: s.coefficient(3) 2 sage: s t^2 + 2*t^3 + O(x^4) sage: s.get_order() 1 sage: s.get_aorder() 1
The reason was that it was easy to implement lazy laurent series with an interface and behaviors that I prefer, while I could not understand well enough LazyPowerSeriesRing
...
I would reconsider basing lazy laurent series on LazyPowerSeriesRing
, if you help me understand the strange behaviour above.
comment:14 Changed 3 years ago by
So here is what refine_aorder
does. It first checks if self.order
has been set, if it has, do not do anything. Then it goes through all of the n
computed entries if self.aorder
is 0 and we have already computed at least one entry. Then find the first nonzero entry. If we have found one, set the order.
The problem is the bold part. After the first iteration when n = 1
, the self.aorder
gets set to 1
, then on the second run through, that block does not get run, which then means self.aorder < n
and we set the order to be 1
.
sage: s.coefficient(1) 0 sage: s.aorder 1 sage: s.order Unknown series order sage: s.coefficient(2) 1 sage: s.aorder 1 sage: s.order 1
IMO, this is a bug.
comment:15 Changed 3 years ago by
 Commit changed from f70fca8e3303c51b98c3f9311da277fd954b1ebe to fb4d65d9dfdb53a735ca33e7800ef79e4ea8ece4
comment:16 Changed 3 years ago by
 Commit changed from fb4d65d9dfdb53a735ca33e7800ef79e4ea8ece4 to 41f3a4237cc0f574334a6e26e00f16d73d23972a
Branch pushed to git repo; I updated commit sha1. New commits:
41f3a42  Lazy Laurent series is not picklable

comment:17 in reply to: ↑ 12 Changed 3 years ago by
Why do you override
__eq__
and not use the one provided byElement
and the coercion framework? It is more flexible and allows you do implement comparisons (if you want) all in one function of_richcmp_
.
Ok. Fixed.
Do not have bare
except:
statements (seecoefficient
).
Fixed.
Does the elements pickle? I am a little worried that the addition of two power series will not pickling because of the little helper
add
function. You should add aloads(dumps(foo))
test if it does work.
No. Your worry is real; lazy Laurent series is not picklable in general. This seems an inherent nature of my implementation...
I added a test to show this.
Typo
laurent
>Laurent
(it is proper noun).
Right. Fixed.
if len(s) == 0:
>if not s:
Done.
New commits:
41f3a42  Lazy Laurent series is not picklable

comment:18 in reply to: ↑ 12 ; followup: ↓ 20 Changed 3 years ago by
Replying to tscrim:
Some comments:
Is there a reason why you do not use the
LazyPowerSeriesRing
for the main element (with a nonzero constant term until the whole series is zero) and then just store the valuation? This is how things are done for the Laurent polynomials. That way there is less duplication of code and improvements to one improve both.
I thought about this. Now I think:
Lazy Laurent series is not just about Laurent series but also about how coefficients are computed lazily. A LazyPowerSeriesRing
element gets its coefficients from a stream object, which essentially yields coefficients as required. On the other hand, lazy Laurent series s
gets its coefficients from a python function that outputs nth coefficient for input s
and n
. This allows coefficients to be computed recursively. For example, it is very easy to define the Fibonacci series.
So it is impossible to base my lazy Laurent series code on LazyPowerSeriesRing
without abandoning the essential feature of the implementation.
Frankly, I would rather provide new lazy power series as a subclass of my lazy Laurent series. But this is of course highly biased opinion :)
You may be reluctant to accept my implementation of lazy Laurent series into sage.rings
as it then gets kind of standard status among different possible implementations of lazy Laurent series in Sage. Then I am willing to relocate it into sage.rings.function_field
.
comment:19 Changed 3 years ago by
 Commit changed from 41f3a4237cc0f574334a6e26e00f16d73d23972a to b09cd84220dc5878d03db5d1ee1d721388457b4e
Branch pushed to git repo; I updated commit sha1. New commits:
b09cd84  Fix pickling doctest

comment:20 in reply to: ↑ 18 ; followup: ↓ 22 Changed 3 years ago by
Replying to klee:
Replying to tscrim:
Some comments:
Is there a reason why you do not use the
LazyPowerSeriesRing
for the main element (with a nonzero constant term until the whole series is zero) and then just store the valuation? This is how things are done for the Laurent polynomials. That way there is less duplication of code and improvements to one improve both.I thought about this. Now I think:
Lazy Laurent series is not just about Laurent series but also about how coefficients are computed lazily. A
LazyPowerSeriesRing
element gets its coefficients from a stream object, which essentially yields coefficients as required. On the other hand, lazy Laurent seriess
gets its coefficients from a python function that outputs nth coefficient for inputs
andn
. This allows coefficients to be computed recursively. For example, it is very easy to define the Fibonacci series.
Well, I am fairly certain you could do this with an RecursivelyEnumeratedSet
and a bit of knowhow, but I agree that it is more complicated and less intuitive. I also agree that having general functions as input would probably be a good thing for LazyPowerSeriesRing
to have, but I believe that was designed for more specific use for the combinat/species
code.
One benefit I do see is that you do not need to explicitly know the valuation at creationtime. With my suggested implementation, it does need to be computed at element creation.
Frankly, I would rather provide new lazy power series as a subclass of my lazy Laurent series. But this is of course highly biased opinion :)
I don't have an opinion on this matter, but there are likely some considerations required to replace or extend the current implementation.
You may be reluctant to accept my implementation of lazy Laurent series into
sage.rings
as it then gets kind of standard status among different possible implementations of lazy Laurent series in Sage. Then I am willing to relocate it intosage.rings.function_field
.
This I don't really care about. I just am a little unhappy with the large difference between the semantics (and syntax) between the two implementations. I guess that is a bit unavoidable here because this definitely is serving a purpose.
However, I do think we should at least try to address the pickling issues. I believe this means you cannot use this in parallel implementations (IIRC this uses pickling to communicate between the processes). It also means you cannot (easily) store the data you compute. I think it is sufficient to separate out the add
and similar operations into functions, but maybe they need to be small little helper class, such as
class LaurentSeriesOperator(object): def __init__(self, lps, op): self.lps = lps self.op = op def __call__(self, s, n): return self.op(self.lps[n], s[n]) def __reduce__(self): return (type(self), (self.lps, self.op), {}) def __eq__(self, other): return (isinstance(other, LaurentSeriesOperator) and self.lps == other.lps and self.op == other.op)
where op
is, e.g., operator.add
. This way you might be able to do something with comparisons in some semireasonable capacity too.
comment:21 Changed 3 years ago by
 Commit changed from b09cd84220dc5878d03db5d1ee1d721388457b4e to 89992b806e2d534343bb57c2a6cec1d0fecd9394
Branch pushed to git repo; I updated commit sha1. New commits:
89992b8  Reimplement arithmetic operations for series to be picklable

comment:22 in reply to: ↑ 20 Changed 3 years ago by
Replying to tscrim:
However, I do think we should at least try to address the pickling issues. I believe this means you cannot use this in parallel implementations (IIRC this uses pickling to communicate between the processes). It also means you cannot (easily) store the data you compute. I think it is sufficient to separate out the
add
and similar operations into functions, but maybe they need to be small little helper class, such asclass LaurentSeriesOperator(object): def __init__(self, lps, op): self.lps = lps self.op = op def __call__(self, s, n): return self.op(self.lps[n], s[n]) def __reduce__(self): return (type(self), (self.lps, self.op), {}) def __eq__(self, other): return (isinstance(other, LaurentSeriesOperator) and self.lps == other.lps and self.op == other.op)where
op
is, e.g.,operator.add
. This way you might be able to do something with comparisons in some semireasonable capacity too.
Using modulelevel classes to define operators is a good idea. Hinted by your template class, I could reimplement lazy Laurent series to be picklable. Great!
comment:23 Changed 3 years ago by
 Commit changed from 89992b806e2d534343bb57c2a6cec1d0fecd9394 to 989a3ac561bed35c9466a848e2a9ef441f94f560
Branch pushed to git repo; I updated commit sha1. New commits:
989a3ac  Comparison now works in semireasonable capacity

comment:24 Changed 3 years ago by
 Commit changed from 989a3ac561bed35c9466a848e2a9ef441f94f560 to e12fd5b6511f90ccb9b5b7bc59cb61e30d75cc93
comment:25 Changed 3 years ago by
 Description modified (diff)
Branch pushed to git repo; I updated commit sha1. New commits:
Introduce lazy laurent series