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: sage-8.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 behackl)

Given an implicitly defined function y(z) = z \Phi(y(z)), there is a well-known 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 behackl

  • Description modified (diff)

comment:2 Changed 3 years ago by behackl

Before this can be properly reviewed, there are at least two things that I'd like to take care of beforehand:

  • There is still a small bit of functionality missing, namely the handling of periodicities.
  • I'd also like to have some more (verified) doctests.

Otherwise, I'm open for suggestions and improvements.

Last edited 3 years ago by behackl (previous) (diff)

comment:3 Changed 3 years ago by git

  • Commit changed from c73ce0c31678f8b126c8de0edcb820a9c28c5fe7 to a13e716cfd3f908ee6ee36f360d98df204af4ee9

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

9442680handle period p > 1
0b75114fix imports and other errors
a13e716add doctest for period

comment:4 follow-up: Changed 3 years ago by 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

[asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:8: WARNING: Inline interpreted text or phrase reference start-string without end-string.
[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 start-string without end-string.
[asymptoti] ...:docstring of sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.ImplicitExpansion:39: WARNING: Inline interpreted text or phrase reference start-string without end-string.
[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 git

  • Commit changed from a13e716cfd3f908ee6ee36f360d98df204af4ee9 to bcafc89f1be0e8fb613579f7d0c00010593b19f1

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

bcafc89changes in doc (raw string; period implemented)

comment:6 in reply to: ↑ 4 Changed 3 years ago by behackl

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 cheuberg

  • Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion

comment:8 Changed 3 years ago by git

  • Commit changed from bcafc89f1be0e8fb613579f7d0c00010593b19f1 to 987a3081dd7f959772ee138abfbc61cf54915642

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

2c17000Trac #23872: PEP8
987a308Trac #23872: sum of sequence

comment:9 Changed 3 years ago by cheuberg

  • 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

  1. Add function to toc and to docstring of class AsymptoticExpansionGenerators
  2. "to be not" -> "not to be"
  3. Phi must be analytic around 0
  4. tau: list assumption of Flajolet-Sedgewick.
  5. comparison with known expansion of Catalan GF
  6. Move all assumptions on Phi to the description
  7. Check input as far as reasonable (phi(0) != 0, phi not affine linear)
  8. examples: symbolic tau is possible
  9. examples: tau can be stupid.
  10. Cite Flajolet-Sedgewick
  11. examples: how to do singularity analysis afterwards.
Last edited 3 years ago by cheuberg (previous) (diff)

comment:10 Changed 3 years ago by cheuberg

  • Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion

comment:11 Changed 3 years ago by cheuberg

  • Commit changed from bcafc89f1be0e8fb613579f7d0c00010593b19f1 to 987a3081dd7f959772ee138abfbc61cf54915642

I forgot to add: I am not convinced by the code for periodic phi.


New commits:

2c17000Trac #23872: PEP8
987a308Trac #23872: sum of sequence

comment:12 Changed 3 years ago by behackl

After some more discussions with cheuberg, this is the current status:

  • Take care of 1-10 mentioned in the comment above,
  • Remove the part of ImplicitExpansion handling the periodic part,
  • Add another function (e.g. ImplicitExpansionPeriodicPart) returning the expansion for g(z) where y(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 behackl

  • Branch changed from u/cheuberg/asy/implicit_singular_expansion to u/behackl/asy/implicit_singular_expansion
  • Commit changed from 987a3081dd7f959772ee138abfbc61cf54915642 to 700c291046c65bc18a77e4847f7b50f810361f6c

New commits:

79c3c47remove separate handling of period
7a75adcimprove documentation
588ffefcheck phi for requirements
022a19dtests for phi; don't pass int(0) to phi
c0c2772test: tau cannot be determined
b656293add more examples to ImplicitExpansion
700c291references, toc

comment:14 Changed 3 years ago by git

  • Commit changed from 700c291046c65bc18a77e4847f7b50f810361f6c to a041106b9214a2b1d1fd6a3102968f5ead1f7aee

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

68e5f88fix doctests
d0a2563separate method for determining tau
b807e05new method: ImplictExpansionPeriodicPart
a041106fix typo, toc

comment:15 Changed 3 years ago by cheuberg

  • Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion

comment:16 Changed 3 years ago by git

  • Commit changed from a041106b9214a2b1d1fd6a3102968f5ead1f7aee to 4a6f4877c180634ed6bae900191f3a2c649d1c47

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

4f3cfbeTrac #23872: rename _fundamental_constant_
1212cbbTrac #23872: add experimental decorator
ca161c2Trac #23872: two rewordings
12e463bTrac #23872: explicitly mention #20050
87512baTrac #23872: period without default
30305cfTrac #23872: improve seealso block
4a6f487Trac #23872: Move FS2009 to master reference list

comment:17 Changed 3 years ago by cheuberg

  • Status changed from new to needs_review

I had a look at your changes, thank you. I added a few reviewer commits, please cross-review. Setting to needs_review such that patchbots see the ticket.

comment:18 Changed 3 years ago by git

  • Commit changed from 4a6f4877c180634ed6bae900191f3a2c649d1c47 to ab7e2c2edbe8b3b79e88df4be554b32d990af5c5

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

ab7e2c2Trac #23872: move FS2009 according to label

comment:19 Changed 3 years ago by behackl

  • Branch changed from u/cheuberg/asy/implicit_singular_expansion to u/behackl/asy/implicit_singular_expansion
  • Commit changed from ab7e2c2edbe8b3b79e88df4be554b32d990af5c5 to 9fc741e9e49b7b3ca3ccdeda6951e5d749a39135

New commits:

eaf9e8finitial version of InverseFunctionAnalysis
a6f66a2Merge branch 'u/cheuberg/asy/implicit_singular_expansion' of git://trac.sagemath.org/sage into u/behackl/asy/implicit_singular_expansion
9fc741eadd doctest for InverseFunctionAnalysis

comment:20 Changed 3 years ago by behackl

Thanks, I've cross-reviewed 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 cheuberg

  • Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion

comment:22 Changed 3 years ago by git

  • Commit changed from 9fc741e9e49b7b3ca3ccdeda6951e5d749a39135 to 065d1af95c5fa81908b3f6c2719a959730e18d0e

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

92b2267Trac #23872: rewording; exchange order of params
e40edb2Trac #23872: include in toc
7079781Trac #23872: see also blocks
fc91313Trac #23872: add doctest for aperiodic case
065d1afTrac #23872: document bug

comment:23 Changed 3 years ago by cheuberg

  • 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 behackl

  • 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 as-is (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:

a6358f1fix bug with omitted precision

comment:25 follow-up: Changed 3 years ago by 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.

comment:26 Changed 3 years ago by git

  • Commit changed from a6358f1b57e955f7f15ea6541ffa3edcea42949b to 9d40353bc8b0c425ca376387f8068108cd4e5b14

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

e619e5dfix caching issue with default_prec of AsymptoticRing
9d40353adapt default_prec-doctest

comment:27 in reply to: ↑ 25 ; follow-up: Changed 3 years ago by behackl

  • 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 cheuberg

  • Branch changed from u/behackl/asy/implicit_singular_expansion to u/cheuberg/asy/implicit_singular_expansion

comment:29 Changed 3 years ago by git

  • Commit changed from 9d40353bc8b0c425ca376387f8068108cd4e5b14 to 317eb16079189d8e6f1b03c377fe36add34bc239

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

317eb16Trac #23872: test needs to simulate python integer

comment:30 in reply to: ↑ 27 ; follow-ups: Changed 3 years ago by cheuberg

  • 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 behackl

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 ; follow-up: Changed 3 years ago by dkrenn

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 ; follow-up: Changed 3 years ago by behackl

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 cheuberg

Replying to behackl:

@cheuberg: what remains to be done here? The patchbots also seem to be happy with the changes.

Please cross-review 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 behackl

  • Status changed from needs_review to positive_review

In this case: I cross-reviewed 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 vbraun

  • Branch changed from u/cheuberg/asy/implicit_singular_expansion to 317eb16079189d8e6f1b03c377fe36add34bc239
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.