Opened 4 years ago

Closed 4 years ago

#19944 closed enhancement (fixed)

asymptotic expansions: singularity analysis

Reported by: behackl Owned by:
Priority: major Milestone: sage-7.1
Component: asymptotic expansions Keywords:
Cc: dkrenn, cheuberg Merged in:
Authors: Benjamin Hackl, Clemens Heuberger Reviewers: Daniel Krenn
Report Upstream: N/A Work issues:
Branch: 452c43b (Commits) Commit: 452c43bdcd74b18f166b9dda4c0936f51032eacc
Dependencies: #19532, #19969, #19981 Stopgaps:

Description

This ticket aims to implement singularity analysis as a callable method of asymptotic rings.

Change History (34)

comment:1 Changed 4 years ago by behackl

  • Authors set to Benjamin Hackl, Clemens Heuberger
  • Branch set to u/behackl/asy/singularity-analysis
  • Commit set to 25a5dd52a7e68c5606b75fe76de25651f5e8d433
  • Dependencies set to #19532

Last 10 new commits:

267718dTrac #19532: Additional tests
0860173Trac #19532: List log log factors, document missing implementations
a3a6dfdTrac #19532: Add references
3e23a35Merge branch 't/19532/asy/singularity-analysis' into t/17601/public/asy/trunk
bedd23aTrac #19898: rename harmonic_number to HarmonicNumber
e107b79Merge branch 't/19898/asy/harmonic-number' into t/17601/public/asy/trunk
e750ddeadd code for singularity analysis
af7c73badd example
f212deefix: .summand --> .summands
25a5dd5add precision keyword

comment:2 Changed 4 years ago by cheuberg

  • Branch changed from u/behackl/asy/singularity-analysis to u/cheuberg/asy/singularity-analysis-method
  • Commit changed from 25a5dd52a7e68c5606b75fe76de25651f5e8d433 to f6a233d2c5563a86ec2adb320a42f92e18d62bae

Rebased on top of #19532 instead of #17601.


New commits:

1529a4dTrac #19510: Merge #19306 (due to #19879)
b30388bTrac #19532: Merge #19510 to fix doctest
7f74b31Trac #19532: Implement zeta != 1
0c600cfadd code for singularity analysis
b8a52c6add example
e3588b6fix: .summand --> .summands
f6a233dadd precision keyword

comment:3 Changed 4 years ago by git

  • Commit changed from f6a233d2c5563a86ec2adb320a42f92e18d62bae to a7aec7ce6c7b7f2dc82a6fc8002ae1a111091481

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

f38cdfcTrac #19532: fix more issues with location of singularities
042849aTrac #19944: merge #19532
a7aec7cTrac #19944: use generating function (as function) instead of singular expansion

comment:4 Changed 4 years ago by git

  • Commit changed from a7aec7ce6c7b7f2dc82a6fc8002ae1a111091481 to a832ebda59cd172d4738ac89130bc3a82f7f2dd8

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

5d87b05Trac #19944: use precision for singular expansion
a832ebdTrac #19944: return singular expansions on request

comment:5 Changed 4 years ago by cheuberg

  • Status changed from new to needs_review

Once #19947 is done, input could also be as a symbolic expression plus a variable, which would probably be friendlier.

comment:6 follow-up: Changed 4 years ago by cheuberg

  • Status changed from needs_review to needs_work

Adapt to new version of #19532 and doctest OZero condition.

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

  • Branch changed from u/cheuberg/asy/singularity-analysis-method to u/behackl/asy/singularity-analysis-method
  • Commit changed from a832ebda59cd172d4738ac89130bc3a82f7f2dd8 to a2e430e09112e37cc301c27cf571ce1acf911b67
  • Status changed from needs_work to needs_review

Replying to cheuberg:

Adapt to new version of #19532 and doctest OZero condition.

Done.


Last 10 new commits:

24c153cTrac #19946: reviewer commit: ReSt error
7918417Trac #19946: additional doctest
bfb72dcTrac #19532: Merge #19946
21054cbTrac #19532: get rid of work-around for #19946
53a35cfMerge branch 'u/cheuberg/asy/singularity-analysis-generator' of git://trac.sagemath.org/sage into asy/singularity-analysis-method
9f650b0handle OZeroException in singularity_analysis
8aa55e2implement exact_part
7276172delete terms from copy instead of building new poset
742ce5bMerge branch 'asy/exact_part' into asy/singularity-analysis-method
a2e430eadd doctest for NotImplementedOZero

comment:8 Changed 4 years ago by dkrenn

  • Branch changed from u/behackl/asy/singularity-analysis-method to u/dkrenn/asy/singularity-analysis-method

comment:9 follow-up: Changed 4 years ago by dkrenn

  • Commit changed from a2e430e09112e37cc301c27cf571ce1acf911b67 to 3743f9d9c5794053bc31e2f434590d9cd53efbfd
  • Reviewers set to Daniel Krenn
  • Status changed from needs_review to needs_work

I've reviewed the patch and have the following comments:

  1. result.exact_part() == result: Maybe create a follow up ticket implementing is_exact.
  1. The code
                if isinstance(summand, ExactTerm):
                    expansion = asymptotic_expansions.\
                        SingularityAnalysis('Z', alpha=alpha, zeta=singularity,
                                            precision=precision).subs(Z=self.gen())
                    return summand.coefficient * expansion
                elif isinstance(summand, OTerm):
                    return (self.gen() ** (alpha - 1)).O()
    

is not ideal. It looks like the singularity analysis should be done by the terms themselves and eventually by the growth groups (since they know what they are).

  1. (self.gen() ** (alpha - 1)).O() should depend on the singularity.
  1. In some sense the transfer term (self.gen() ** (alpha - 1)).O() has the same status as the expansion asymptotic_expansions.SingularityAnalysis. So a generation in the generations would be an option. However, I understand, that it is much simpler, so I do *not* have a strong preference for this.
  1. Parameter description function: mentioned the word "callable"(?) Say that it is a function in one variable.
  1. Parameter return_singular_expansions: in an ideal world, there would not be a different kind of output (asymptotic expansions vs. named tuple). However, I understand it is as it is; it seems that there is no other satisfying solution to this. Am I right?

New commits:

3743f9dTrac #19944 minor changes during review

comment:10 Changed 4 years ago by cheuberg

A few thoughts on your comments:

  • asymptotic_expansions.SingularityAnalysis with precision=0 could very well return the transfer error term; I think that this would be consistent with precision=0. And precision=0 does not work anyway at the moment.
  • Then, indeed, an ExactTerm could do singularity analysis by calling singularity analysis on the growth element and multiply by its coefficient; and an OTerm could do singularity analysis by calling singularity analysis on the growth element with precision=0.
  • A monomial growth group would do singularity analysis by checking whether it is a growth group in T (then call the generator with alpha=... and beta=0) or a growth group in log(T) (call a yet to be written generator for (1-z)^alpha (log(1-u))^beta)
  • A cartesian growth group would restrict its attention to cases where all non-trivial contributions come from one factor (hand the question down to the factor) or from two factors (in that case, the cartesian growth group has to do the job on its own calling the above mentioned generator).

comment:11 Changed 4 years ago by cheuberg

  • Branch changed from u/dkrenn/asy/singularity-analysis-method to u/cheuberg/asy/singularity-analysis-method

comment:12 Changed 4 years ago by cheuberg

  • Commit changed from 3743f9d9c5794053bc31e2f434590d9cd53efbfd to e9849bcc8e702b753858af5a6047236a49ac909b
  • Dependencies changed from #19532 to #19532, #19969

I started rewriting this branch by introducing a method _singularity_analysis_ for growth groups.


Last 10 new commits:

c1dd748Merge branch 'arb/parse-symbolic' into t/19969/asy/SA-generator-log
9488698Trac 19969: remove parameter 'skip_constant_factor'
8938c97Trac #19969: unique code for all three cases
e769bdeTrac #19969: smaller coefficient rings if possible
feec36aTrac #19969: prefer coefficients as multiples of 1/Gamma(alpha)
7ad8f16Trac #19969: remove obsolete comment
366a9daTrac #19944: Merge #19969 (for SingularityAnalysis with precision=0)
dc39257Trac #19944: Singularity analysis of generic growth element
5456873Trac #19944: rename "singularity" and "rho" to "zeta"
e9849bcTrac #19944: singularity analysis for monomial growth groups

comment:13 Changed 4 years ago by git

  • Commit changed from e9849bcc8e702b753858af5a6047236a49ac909b to 637147cb97d5a73e959c4063896bf8a413a67e1a

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

91547aaTrac #19944: typos and minor fixes in growth group
cee10ddTrac #19944: singularity analysis in GenericTermMonoid
9b2835eTrac #19944: singularity analysis on O terms
f2cb06bTrac #19944: singularity analysis of exact terms
3065e27Merge commit 'da853f87105d7e8ec4883141e1a98911cb91900c' of git://trac.sagemath.org/sage into t/19944/asy/singularity-analysis-method
7c1d207Trac #19944: rewrite singularity analysis to use method of terms
5c66050Trac #19944: be more explicit w.r.t. parameter function
e7fb7ccMerge tag '7.1.beta1' into arb/parse-symbolic
2c2955fTrac #19993: fix doctest results in complex_arb
637147cTrac #19944: merge latest version of #19993

comment:14 in reply to: ↑ 9 Changed 4 years ago by cheuberg

  • Dependencies changed from #19532, #19969 to #19532, #19969, #19981
  • Status changed from needs_work to needs_review

The method is now completely rewritten; 7.1.beta1 has been merged implicitly by merging #19981.

Replying to dkrenn:

  1. result.exact_part() == result: Maybe create a follow up ticket implementing is_exact.

done (#19981)

  1. The code ...

is not ideal. It looks like the singularity analysis should be done by the terms themselves and eventually by the growth groups (since they know what they are).

Done.

  1. (self.gen() ** (alpha - 1)).O() should depend on the singularity.

Implicitly done by 2.

  1. In some sense the transfer term (self.gen() ** (alpha - 1)).O() has the same status as the expansion asymptotic_expansions.SingularityAnalysis. So a generation in the generations would be an option. However, I understand, that it is much simpler, so I do *not* have a strong preference for this.

Done (via precision=0).

  1. Parameter description function: mentioned the word "callable"(?) Say that it is a function in one variable.

Done.

  1. Parameter return_singular_expansions: in an ideal world, there would not be a different kind of output (asymptotic expansions vs. named tuple). However, I understand it is as it is; it seems that there is no other satisfying solution to this. Am I right?

No better solution found.

comment:15 follow-up: Changed 4 years ago by dkrenn

  • Branch changed from u/cheuberg/asy/singularity-analysis-method to u/dkrenn/asy/singularity-analysis-method

comment:16 in reply to: ↑ 15 Changed 4 years ago by cheuberg

  • Commit changed from 637147cb97d5a73e959c4063896bf8a413a67e1a to 46d91b3d031cc10b885ab33c8e2d7838a7df45c9

cross-reviewed your changes.


Last 10 new commits:

ba0a5adforbid asymptotic rings as base in growth groups
c2f30f5move code of NotImplementedOZero to avoid merge-conflicts
ebac5c2Trac #20043: add additional doctest to check parent
33f675dMerge branch 'u/dkrenn/asy/one-times-zero' of trac.sagemath.org:sage into t/19969/asy/SA-generator-log
a9e618eMerge branch 'u/dkrenn/asy/SA-generator-log' of trac.sagemath.org:sage into t/19944/asy/singularity-analysis-method
98e1fc7Trac #20043: make error message more precise and flexibel
99d7292Merge branch 't/20043/asy/one-times-zero' into t/19969/asy/SA-generator-log
dd7dabfTrac #19969: fix doctest
88f278dMerge branch 't/19969/asy/SA-generator-log' into HEAD
46d91b3Trac #19944: fix doctests and code

comment:17 Changed 4 years ago by git

  • Commit changed from 46d91b3d031cc10b885ab33c8e2d7838a7df45c9 to ad62c3185d95d1711feb65c33f6096d0662e5c84

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

617e5bfTrac #19969: rewrite output of doctest so that comparison with Formula in Flajolet-Sedgewick is easier
456d8c3Trac #19969: correct whitespaces
b540598Trac #19969: add an additional doctest
984ca4dMerge branch 'u/dkrenn/asy/SA-generator-log' of git://trac.sagemath.org/sage into t/19944/asy/singularity-analysis-method
e1e2ef3Trac #19944: minor restructure of code
97249e7Trac #19944: minor improvement of docstrings (whitespaces, punctation, ...)
ad62c31Trac #19944: show element in NotImplementedError

comment:18 follow-up: Changed 4 years ago by dkrenn

Thanks you for your rewrite; it is much better and cleaner now; I consider the code as positively reviewed. However, please cross-review my minor changes and the following two documentation issues should be discussed (both concerning the private _singularity_analysis_-mathods:

  1. Is (1-z\zeta) \to 0 correct or should it be (1-z/\zeta) \to 0? Maybe using z\to\zeta instead of (1-z/\zeta) \to 0? (I don't have a strong preference for changing, but from an outside view, this would be easier to understand.
  1. Should it be mentioned that (in terms and growth groups) a variable (_var_ of the parent) represents/equals 1 / (1-z/\zeta) ?

comment:19 follow-up: Changed 4 years ago by dkrenn

There is an inconsistency in the order of the parameters: in the generators we have var, zeta=1, ..., but in all the _singularity_analysis_ we have zeta, var.

comment:20 follow-up: Changed 4 years ago by dkrenn

...and maybe (but really, maybe): name argument precision in the doctests to make them better readable; e.g. `_singularity_analysis_('n', 1/2, precision=5)'.

comment:21 in reply to: ↑ 18 ; follow-up: Changed 4 years ago by cheuberg

Replying to dkrenn:

please cross-review my minor changes

done.

  1. Is (1-z\zeta) \to 0 correct or should it be (1-z/\zeta) \to 0? Maybe using z\to\zeta instead of (1-z/\zeta) \to 0? (I don't have a strong preference for changing, but from an outside view, this would be easier to understand.

I prefer (1-z/\zeta) \to 0 or perhaps T = 1/(1-z/\zeta) \to \infty.

  1. Should it be mentioned that (in terms and growth groups) a variable (_var_ of the parent) represents/equals 1 / (1-z/\zeta) ?

This should change once asymptotics z->z_0 are implemented.

What about "T = 1/(1-z/\zeta) \to \infty where this element is a growth element (resp. monomial) in T"?

comment:22 in reply to: ↑ 19 ; follow-up: Changed 4 years ago by cheuberg

Replying to dkrenn:

There is an inconsistency in the order of the parameters: in the generators we have var, zeta=1, ..., but in all the _singularity_analysis_ we have zeta, var.

OK, I'll change the _singularity_analysis_ routines.

Once we have #20050, the parameter zeta will be removed.

comment:23 in reply to: ↑ 20 ; follow-up: Changed 4 years ago by cheuberg

Replying to dkrenn:

...and maybe (but really, maybe): name argument precision in the doctests to make them better readable; e.g. `_singularity_analysis_('n', 1/2, precision=5)'.

I will do that.

comment:24 Changed 4 years ago by cheuberg

  • Branch changed from u/dkrenn/asy/singularity-analysis-method to u/cheuberg/asy/singularity-analysis-method

comment:25 in reply to: ↑ 22 ; follow-up: Changed 4 years ago by cheuberg

  • Commit changed from ad62c3185d95d1711feb65c33f6096d0662e5c84 to 9ce7b354e32efbbb775157bf7c8232fd5df01cb5

Replying to cheuberg:

Replying to dkrenn:

There is an inconsistency in the order of the parameters: in the generators we have var, zeta=1, ..., but in all the _singularity_analysis_ we have zeta, var.

OK, I'll change the _singularity_analysis_ routines.

Done.


New commits:

9ce7b35Trac #19944: exchange order of parameters var and zeta in _singularity_analysis_

comment:26 in reply to: ↑ 23 Changed 4 years ago by cheuberg

Replying to cheuberg:

Replying to dkrenn:

...and maybe (but really, maybe): name argument precision in the doctests to make them better readable; e.g. `_singularity_analysis_('n', 1/2, precision=5)'.

I will do that.

done.

comment:27 in reply to: ↑ 25 Changed 4 years ago by cheuberg

  • Status changed from needs_review to needs_work

Replying to cheuberg:

Done.


New commits:

9ce7b35Trac #19944: exchange order of parameters var and zeta in _singularity_analysis_

I forgot to change the docstrings. I will do so now.

comment:28 follow-up: Changed 4 years ago by git

  • Commit changed from 9ce7b354e32efbbb775157bf7c8232fd5df01cb5 to c79a6f7bbb3f17454a1c6238193696e525a8c0ec

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

c79a6f7Trac #19944: exchange zeta and var in docstrings

comment:29 in reply to: ↑ 28 Changed 4 years ago by cheuberg

  • Status changed from needs_work to needs_review

Replying to git:

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

c79a6f7Trac #19944: exchange zeta and var in docstrings

Done.

comment:30 in reply to: ↑ 21 ; follow-up: Changed 4 years ago by dkrenn

Replying to cheuberg:

Replying to dkrenn:

  1. Is (1-z\zeta) \to 0 correct or should it be (1-z/\zeta) \to 0? Maybe using z\to\zeta instead of (1-z/\zeta) \to 0? (I don't have a strong preference for changing, but from an outside view, this would be easier to understand.

I prefer (1-z/\zeta) \to 0 or perhaps T = 1/(1-z/\zeta) \to \infty.

  1. Should it be mentioned that (in terms and growth groups) a variable (_var_ of the parent) represents/equals 1 / (1-z/\zeta) ?

This should change once asymptotics z->z_0 are implemented.

What about "T = 1/(1-z/\zeta) \to \infty where this element is a growth element (resp. monomial) in T"?

I'm happy with this formulation.

All the other changes are positivly reviewed form my side.

comment:31 Changed 4 years ago by git

  • Commit changed from c79a6f7bbb3f17454a1c6238193696e525a8c0ec to 452c43bdcd74b18f166b9dda4c0936f51032eacc

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

452c43bTrac #19944: _singularity_analysis_ methods: more precise documentation

comment:32 in reply to: ↑ 30 ; follow-up: Changed 4 years ago by cheuberg

Replying to dkrenn:

What about "T = 1/(1-z/\zeta) \to \infty where this element is a growth element (resp. monomial) in T"?

I'm happy with this formulation.

done. needs review.

comment:33 in reply to: ↑ 32 Changed 4 years ago by dkrenn

  • Status changed from needs_review to positive_review

Replying to cheuberg:

Replying to dkrenn:

What about "T = 1/(1-z/\zeta) \to \infty where this element is a growth element (resp. monomial) in T"?

I'm happy with this formulation.

done. needs review.

Fine.

comment:34 Changed 4 years ago by vbraun

  • Branch changed from u/cheuberg/asy/singularity-analysis-method to 452c43bdcd74b18f166b9dda4c0936f51032eacc
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.