Opened 3 years ago
Closed 3 years ago
#23872 closed enhancement (fixed)
Singular expansion for implicitly defined function
Reported by:  behackl  Owned by:  

Priority:  major  Milestone:  sage8.1 
Component:  asymptotic expansions  Keywords:  
Cc:  cheuberg, dkrenn  Merged in:  
Authors:  Benjamin Hackl  Reviewers:  Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  317eb16 (Commits)  Commit:  317eb16079189d8e6f1b03c377fe36add34bc239 
Dependencies:  Stopgaps: 
Description (last modified by )
Given an implicitly defined function y(z) = z \Phi(y(z))
, there is a wellknown approach (Analytic Combinatorics, Flajolet+Sedgewick, Chapter VI.7) on how to determine a singular expansion for y(z)
.
This branch adds a new asymptotic generator which computes this singular expansion.
Change History (36)
comment:1 Changed 3 years ago by
 Description modified (diff)
comment:2 Changed 3 years ago by
comment:3 Changed 3 years ago by
 Commit changed from c73ce0c31678f8b126c8de0edcb820a9c28c5fe7 to a13e716cfd3f908ee6ee36f360d98df204af4ee9
comment:4 followup: ↓ 6 Changed 3 years ago by
(Note: I currently have no compiled version of 8.1.beta5 available; so I locally rebased your branch on 8.0 ... so it might be that this is an incompatibility between 8.0 and 8.1.beta5)
./sage docbuild u k
yields
[asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:8: WARNING: Inline interpreted text or phrase reference startstring without endstring. [asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:12: WARNING: Block quote ends without a blank line; unexpected unindent. [asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:35: WARNING: Block quote ends without a blank line; unexpected unindent. [asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:36: WARNING: Inline interpreted text or phrase reference startstring without endstring. [asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:39: WARNING: Inline interpreted text or phrase reference startstring without endstring. [asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:40: WARNING: Definition list ends without a blank line; unexpected unindent.
comment:5 Changed 3 years ago by
 Commit changed from a13e716cfd3f908ee6ee36f360d98df204af4ee9 to bcafc89f1be0e8fb613579f7d0c00010593b19f1
Branch pushed to git repo; I updated commit sha1. New commits:
bcafc89  changes in doc (raw string; period implemented)

comment:6 in reply to: ↑ 4 Changed 3 years ago by
Replying to cheuberg:
(Note: I currently have no compiled version of 8.1.beta5 available; so I locally rebased your branch on 8.0 ... so it might be that this is an incompatibility between 8.0 and 8.1.beta5)
./sage docbuild u k
yields [...]
Thanks, fixed.
As far as I was able to check, the code yields correct results in both the periodic as well as the aperiodic case. I am, however, inclined to improve the documentation a little bit before putting this up for review (more examples + tests; maybe even a description of the algorithm? Also, a reference to The Book would probably be a good idea).
comment:7 Changed 3 years ago by
 Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion
comment:8 Changed 3 years ago by
 Commit changed from bcafc89f1be0e8fb613579f7d0c00010593b19f1 to 987a3081dd7f959772ee138abfbc61cf54915642
comment:9 Changed 3 years ago by
 Branch changed from u/cheuberg/asy/implicit_singular_expansion to u/behackl/asy/implicit_singular_expansion
 Commit changed from 987a3081dd7f959772ee138abfbc61cf54915642 to bcafc89f1be0e8fb613579f7d0c00010593b19f1
 Reviewers set to Clemens Heuberger
I added two reviewer commits. Please
 Add function to toc and to docstring of class
AsymptoticExpansionGenerators
 "to be not" > "not to be"
 Phi must be analytic around 0
 tau: list assumption of FlajoletSedgewick.
 comparison with known expansion of Catalan GF
 Move all assumptions on Phi to the description
 Check input as far as reasonable (phi(0) != 0, phi not affine linear)
 examples: symbolic tau is possible
 examples: tau can be stupid.
 Cite FlajoletSedgewick
 examples: how to do singularity analysis afterwards.
comment:10 Changed 3 years ago by
 Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion
comment:11 Changed 3 years ago by
 Commit changed from bcafc89f1be0e8fb613579f7d0c00010593b19f1 to 987a3081dd7f959772ee138abfbc61cf54915642
comment:12 Changed 3 years ago by
After some more discussions with cheuberg, this is the current status:
 Take care of 110 mentioned in the comment above,
 Remove the part of
ImplicitExpansion
handling the periodic part,  Add another function (e.g.
ImplicitExpansionPeriodicPart
) returning the expansion forg(z)
wherey(z)/z = g(z^p)
.  And add yet another function (e.g.
InverseFunctionAnalysis
) returning the asymptotic expansion describing the coefficient growth.
comment:13 Changed 3 years ago by
 Branch changed from u/cheuberg/asy/implicit_singular_expansion to u/behackl/asy/implicit_singular_expansion
 Commit changed from 987a3081dd7f959772ee138abfbc61cf54915642 to 700c291046c65bc18a77e4847f7b50f810361f6c
comment:14 Changed 3 years ago by
 Commit changed from 700c291046c65bc18a77e4847f7b50f810361f6c to a041106b9214a2b1d1fd6a3102968f5ead1f7aee
comment:15 Changed 3 years ago by
 Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion
comment:16 Changed 3 years ago by
 Commit changed from a041106b9214a2b1d1fd6a3102968f5ead1f7aee to 4a6f4877c180634ed6bae900191f3a2c649d1c47
Branch pushed to git repo; I updated commit sha1. New commits:
4f3cfbe  Trac #23872: rename _fundamental_constant_

1212cbb  Trac #23872: add experimental decorator

ca161c2  Trac #23872: two rewordings

12e463b  Trac #23872: explicitly mention #20050

87512ba  Trac #23872: period without default

30305cf  Trac #23872: improve seealso block

4a6f487  Trac #23872: Move FS2009 to master reference list

comment:17 Changed 3 years ago by
 Status changed from new to needs_review
I had a look at your changes, thank you. I added a few reviewer commits, please crossreview. Setting to needs_review such that patchbots see the ticket.
comment:18 Changed 3 years ago by
 Commit changed from 4a6f4877c180634ed6bae900191f3a2c649d1c47 to ab7e2c2edbe8b3b79e88df4be554b32d990af5c5
Branch pushed to git repo; I updated commit sha1. New commits:
ab7e2c2  Trac #23872: move FS2009 according to label

comment:19 Changed 3 years ago by
 Branch changed from u/cheuberg/asy/implicit_singular_expansion to u/behackl/asy/implicit_singular_expansion
 Commit changed from ab7e2c2edbe8b3b79e88df4be554b32d990af5c5 to 9fc741e9e49b7b3ca3ccdeda6951e5d749a39135
comment:20 Changed 3 years ago by
Thanks, I've crossreviewed your changes, LGTM.
There is now also the "final" method, InverseFunctionAnalysis
, returning the asymptotic expansion of the coefficient growth via singularity analysis.
Note that currently there is a minor issue with this method: in case tau
is not specified when calling the method (or when tau
is symbolic), this leads to a coercion problem to be solved at #23921.
comment:21 Changed 3 years ago by
 Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion
comment:22 Changed 3 years ago by
 Commit changed from 9fc741e9e49b7b3ca3ccdeda6951e5d749a39135 to 065d1af95c5fa81908b3f6c2719a959730e18d0e
comment:23 Changed 3 years ago by
 Status changed from needs_review to needs_work
I reviewed the new method; added a few reviewer commits. Please fix the error documented in my last commit.
comment:24 Changed 3 years ago by
 Branch changed from u/cheuberg/asy/implicit_singular_expansion to u/behackl/asy/implicit_singular_expansion
 Commit changed from 065d1af95c5fa81908b3f6c2719a959730e18d0e to a6358f1b57e955f7f15ea6541ffa3edcea42949b
The bug should be fixed with my last commit  however, I'm not sure about leaving the doctest asis (of course with changed output and description), as the default precision is rather high and the computation of such a precise expansion might be too much.
What do you think?
New commits:
a6358f1  fix bug with omitted precision

comment:25 followup: ↓ 27 Changed 3 years ago by
142 seconds for the tests for this file on a patchbot vs. 51 seconds before on the same patchbot seem to be excessive; so we should remove the test. The variant would be to include a test where the default precision has been set to a small python integer.
comment:26 Changed 3 years ago by
 Commit changed from a6358f1b57e955f7f15ea6541ffa3edcea42949b to 9d40353bc8b0c425ca376387f8068108cd4e5b14
comment:27 in reply to: ↑ 25 ; followup: ↓ 30 Changed 3 years ago by
 Status changed from needs_work to needs_review
Replying to cheuberg:
142 seconds for the tests for this file on a patchbot vs. 51 seconds before on the same patchbot seem to be excessive; so we should remove the test. The variant would be to include a test where the default precision has been set to a small python integer.
It took me some time, but I finally managed to fix the issue with default_prec
. Up for review again.
comment:28 Changed 3 years ago by
 Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion
comment:29 Changed 3 years ago by
 Commit changed from 9d40353bc8b0c425ca376387f8068108cd4e5b14 to 317eb16079189d8e6f1b03c377fe36add34bc239
Branch pushed to git repo; I updated commit sha1. New commits:
317eb16  Trac #23872: test needs to simulate python integer

comment:30 in reply to: ↑ 27 ; followups: ↓ 31 ↓ 32 Changed 3 years ago by
 Cc dkrenn added
The test needed to be modified: we need to set a python integer to actually trigger the error fixed in a6358f1. For test purposes, I then reverted a6358f1 and the bug reappeared, so to be sure that the test now tests what needs to tested.
dkrenn: please have a look at commit e619e5d because it heavily modifies your commit 3214c83 from #19532. (The new code, however, is now equivalent to the comparable situations in Laurent series and power series rings).
comment:31 in reply to: ↑ 30 Changed 3 years ago by
Replying to cheuberg:
The test needed to be modified: we need to set a python integer to actually trigger the error fixed in a6358f1. For test purposes, I then reverted a6358f1 and the bug reappeared, so to be sure that the test now tests what needs to tested.
dkrenn: please have a look at commit e619e5d because it heavily modifies your commit 3214c83 from #19532. (The new code, however, is now equivalent to the comparable situations in Laurent series and power series rings).
Just FYI: I changed the default_prec
code for asymptotic rings, because the precision was cached upon creation of the first asymptotic ring and could then not be changed, i.e. changes of the series_precision()
parameter were not picked up.
comment:32 in reply to: ↑ 30 ; followup: ↓ 33 Changed 3 years ago by
Replying to cheuberg:
dkrenn: please have a look at commit e619e5d because it heavily modifies your commit 3214c83 from #19532. (The new code, however, is now equivalent to the comparable situations in Laurent series and power series rings).
Replying to behackl:
Just FYI: I changed the default_prec code for asymptotic rings, because the precision was cached upon creation of the first asymptotic ring and could then not be changed, i.e. changes of the series_precision() parameter were not picked up.
This change is fine for me (even preferable over the now old implementation).
comment:33 in reply to: ↑ 32 ; followup: ↓ 34 Changed 3 years ago by
Replying to dkrenn:
This change is fine for me (even preferable over the now old implementation).
Thanks for having a look.
@cheuberg: what remains to be done here? The patchbots also seem to be happy with the changes.
comment:34 in reply to: ↑ 33 Changed 3 years ago by
Replying to behackl:
@cheuberg: what remains to be done here? The patchbots also seem to be happy with the changes.
Please crossreview my last commit 317eb16 if this has not yet happened (Reviewing should include a check whether the test tests what it should be test; see my comments in cheuberg. If satisfied, set to positive review. (At the moment, we have an unhappy patchbot, but this is a timeout somewhere else).
comment:35 Changed 3 years ago by
 Status changed from needs_review to positive_review
In this case: I crossreviewed your commit, everything looks good to me, and the test tests the correct thing.
Thus this is positive_review
.
comment:36 Changed 3 years ago by
 Branch changed from u/cheuberg/asy/implicit_singular_expansion to 317eb16079189d8e6f1b03c377fe36add34bc239
 Resolution set to fixed
 Status changed from positive_review to closed
Before this can be properly reviewed, there are at least two things that I'd like to take care of beforehand:
Otherwise, I'm open for suggestions and improvements.