Opened 5 years ago
Closed 5 years ago
#19944 closed enhancement (fixed)
asymptotic expansions: singularity analysis
Reported by:  behackl  Owned by:  

Priority:  major  Milestone:  sage7.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 5 years ago by
 Branch set to u/behackl/asy/singularityanalysis
 Commit set to 25a5dd52a7e68c5606b75fe76de25651f5e8d433
 Dependencies set to #19532
comment:2 Changed 5 years ago by
 Branch changed from u/behackl/asy/singularityanalysis to u/cheuberg/asy/singularityanalysismethod
 Commit changed from 25a5dd52a7e68c5606b75fe76de25651f5e8d433 to f6a233d2c5563a86ec2adb320a42f92e18d62bae
Rebased on top of #19532 instead of #17601.
New commits:
1529a4d  Trac #19510: Merge #19306 (due to #19879)

b30388b  Trac #19532: Merge #19510 to fix doctest

7f74b31  Trac #19532: Implement zeta != 1

0c600cf  add code for singularity analysis

b8a52c6  add example

e3588b6  fix: .summand > .summands

f6a233d  add precision keyword

comment:3 Changed 5 years ago by
 Commit changed from f6a233d2c5563a86ec2adb320a42f92e18d62bae to a7aec7ce6c7b7f2dc82a6fc8002ae1a111091481
comment:4 Changed 5 years ago by
 Commit changed from a7aec7ce6c7b7f2dc82a6fc8002ae1a111091481 to a832ebda59cd172d4738ac89130bc3a82f7f2dd8
comment:5 Changed 5 years ago by
 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 followup: ↓ 7 Changed 5 years ago by
 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 5 years ago by
 Branch changed from u/cheuberg/asy/singularityanalysismethod to u/behackl/asy/singularityanalysismethod
 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:
24c153c  Trac #19946: reviewer commit: ReSt error

7918417  Trac #19946: additional doctest

bfb72dc  Trac #19532: Merge #19946

21054cb  Trac #19532: get rid of workaround for #19946

53a35cf  Merge branch 'u/cheuberg/asy/singularityanalysisgenerator' of git://trac.sagemath.org/sage into asy/singularityanalysismethod

9f650b0  handle OZeroException in singularity_analysis

8aa55e2  implement exact_part

7276172  delete terms from copy instead of building new poset

742ce5b  Merge branch 'asy/exact_part' into asy/singularityanalysismethod

a2e430e  add doctest for NotImplementedOZero

comment:8 Changed 5 years ago by
 Branch changed from u/behackl/asy/singularityanalysismethod to u/dkrenn/asy/singularityanalysismethod
comment:9 followup: ↓ 14 Changed 5 years ago by
 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:
result.exact_part() == result
: Maybe create a follow up ticket implementingis_exact
.
 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).
(self.gen() ** (alpha  1)).O()
should depend on the singularity.
 In some sense the transfer term
(self.gen() ** (alpha  1)).O()
has the same status as the expansionasymptotic_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.
 Parameter description
function
: mentioned the word "callable"(?) Say that it is a function in one variable.
 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:
3743f9d  Trac #19944 minor changes during review

comment:10 Changed 5 years ago by
A few thoughts on your comments:
asymptotic_expansions.SingularityAnalysis
withprecision=0
could very well return the transfer error term; I think that this would be consistent withprecision=0
. Andprecision=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 withalpha=...
andbeta=0
) or a growth group inlog(T)
(call a yet to be written generator for(1z)^alpha (log(1u))^beta
)  A cartesian growth group would restrict its attention to cases where all nontrivial 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 5 years ago by
 Branch changed from u/dkrenn/asy/singularityanalysismethod to u/cheuberg/asy/singularityanalysismethod
comment:12 Changed 5 years ago by
 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:
c1dd748  Merge branch 'arb/parsesymbolic' into t/19969/asy/SAgeneratorlog

9488698  Trac 19969: remove parameter 'skip_constant_factor'

8938c97  Trac #19969: unique code for all three cases

e769bde  Trac #19969: smaller coefficient rings if possible

feec36a  Trac #19969: prefer coefficients as multiples of 1/Gamma(alpha)

7ad8f16  Trac #19969: remove obsolete comment

366a9da  Trac #19944: Merge #19969 (for SingularityAnalysis with precision=0)

dc39257  Trac #19944: Singularity analysis of generic growth element

5456873  Trac #19944: rename "singularity" and "rho" to "zeta"

e9849bc  Trac #19944: singularity analysis for monomial growth groups

comment:13 Changed 5 years ago by
 Commit changed from e9849bcc8e702b753858af5a6047236a49ac909b to 637147cb97d5a73e959c4063896bf8a413a67e1a
Branch pushed to git repo; I updated commit sha1. New commits:
91547aa  Trac #19944: typos and minor fixes in growth group

cee10dd  Trac #19944: singularity analysis in GenericTermMonoid

9b2835e  Trac #19944: singularity analysis on O terms

f2cb06b  Trac #19944: singularity analysis of exact terms

3065e27  Merge commit 'da853f87105d7e8ec4883141e1a98911cb91900c' of git://trac.sagemath.org/sage into t/19944/asy/singularityanalysismethod

7c1d207  Trac #19944: rewrite singularity analysis to use method of terms

5c66050  Trac #19944: be more explicit w.r.t. parameter function

e7fb7cc  Merge tag '7.1.beta1' into arb/parsesymbolic

2c2955f  Trac #19993: fix doctest results in complex_arb

637147c  Trac #19944: merge latest version of #19993

comment:14 in reply to: ↑ 9 Changed 5 years ago by
 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:
result.exact_part() == result
: Maybe create a follow up ticket implementingis_exact
.
done (#19981)
 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.
(self.gen() ** (alpha  1)).O()
should depend on the singularity.
Implicitly done by 2.
 In some sense the transfer term
(self.gen() ** (alpha  1)).O()
has the same status as the expansionasymptotic_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
).
 Parameter description
function
: mentioned the word "callable"(?) Say that it is a function in one variable.
Done.
 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 followup: ↓ 16 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/singularityanalysismethod to u/dkrenn/asy/singularityanalysismethod
comment:16 in reply to: ↑ 15 Changed 5 years ago by
 Commit changed from 637147cb97d5a73e959c4063896bf8a413a67e1a to 46d91b3d031cc10b885ab33c8e2d7838a7df45c9
crossreviewed your changes.
Last 10 new commits:
ba0a5ad  forbid asymptotic rings as base in growth groups

c2f30f5  move code of NotImplementedOZero to avoid mergeconflicts

ebac5c2  Trac #20043: add additional doctest to check parent

33f675d  Merge branch 'u/dkrenn/asy/onetimeszero' of trac.sagemath.org:sage into t/19969/asy/SAgeneratorlog

a9e618e  Merge branch 'u/dkrenn/asy/SAgeneratorlog' of trac.sagemath.org:sage into t/19944/asy/singularityanalysismethod

98e1fc7  Trac #20043: make error message more precise and flexibel

99d7292  Merge branch 't/20043/asy/onetimeszero' into t/19969/asy/SAgeneratorlog

dd7dabf  Trac #19969: fix doctest

88f278d  Merge branch 't/19969/asy/SAgeneratorlog' into HEAD

46d91b3  Trac #19944: fix doctests and code

comment:17 Changed 5 years ago by
 Commit changed from 46d91b3d031cc10b885ab33c8e2d7838a7df45c9 to ad62c3185d95d1711feb65c33f6096d0662e5c84
Branch pushed to git repo; I updated commit sha1. New commits:
617e5bf  Trac #19969: rewrite output of doctest so that comparison with Formula in FlajoletSedgewick is easier

456d8c3  Trac #19969: correct whitespaces

b540598  Trac #19969: add an additional doctest

984ca4d  Merge branch 'u/dkrenn/asy/SAgeneratorlog' of git://trac.sagemath.org/sage into t/19944/asy/singularityanalysismethod

e1e2ef3  Trac #19944: minor restructure of code

97249e7  Trac #19944: minor improvement of docstrings (whitespaces, punctation, ...)

ad62c31  Trac #19944: show element in NotImplementedError

comment:18 followup: ↓ 21 Changed 5 years ago by
Thanks you for your rewrite; it is much better and cleaner now; I consider the code as positively reviewed. However, please crossreview my minor changes and the following two documentation issues should be discussed (both concerning the private _singularity_analysis_
mathods:
 Is
(1z\zeta) \to 0
correct or should it be(1z/\zeta) \to 0
? Maybe usingz\to\zeta
instead of(1z/\zeta) \to 0
? (I don't have a strong preference for changing, but from an outside view, this would be easier to understand.
 Should it be mentioned that (in terms and growth groups) a variable (
_var_
of the parent) represents/equals1 / (1z/\zeta)
?
comment:19 followup: ↓ 22 Changed 5 years ago by
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 followup: ↓ 23 Changed 5 years ago by
...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 ; followup: ↓ 30 Changed 5 years ago by
Replying to dkrenn:
please crossreview my minor changes
done.
 Is
(1z\zeta) \to 0
correct or should it be(1z/\zeta) \to 0
? Maybe usingz\to\zeta
instead of(1z/\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 (1z/\zeta) \to 0
or perhaps T = 1/(1z/\zeta) \to \infty
.
 Should it be mentioned that (in terms and growth groups) a variable (
_var_
of the parent) represents/equals1 / (1z/\zeta)
?
This should change once asymptotics z>z_0
are implemented.
What about "T = 1/(1z/\zeta) \to \infty
where this element is a growth element (resp. monomial) in T
"?
comment:22 in reply to: ↑ 19 ; followup: ↓ 25 Changed 5 years ago by
comment:23 in reply to: ↑ 20 ; followup: ↓ 26 Changed 5 years ago by
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 5 years ago by
 Branch changed from u/dkrenn/asy/singularityanalysismethod to u/cheuberg/asy/singularityanalysismethod
comment:25 in reply to: ↑ 22 ; followup: ↓ 27 Changed 5 years ago by
 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 havezeta, var
.OK, I'll change the
_singularity_analysis_
routines.
Done.
New commits:
9ce7b35  Trac #19944: exchange order of parameters var and zeta in _singularity_analysis_

comment:26 in reply to: ↑ 23 Changed 5 years ago by
comment:27 in reply to: ↑ 25 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:28 followup: ↓ 29 Changed 5 years ago by
 Commit changed from 9ce7b354e32efbbb775157bf7c8232fd5df01cb5 to c79a6f7bbb3f17454a1c6238193696e525a8c0ec
Branch pushed to git repo; I updated commit sha1. New commits:
c79a6f7  Trac #19944: exchange zeta and var in docstrings

comment:29 in reply to: ↑ 28 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:30 in reply to: ↑ 21 ; followup: ↓ 32 Changed 5 years ago by
Replying to cheuberg:
Replying to dkrenn:
 Is
(1z\zeta) \to 0
correct or should it be(1z/\zeta) \to 0
? Maybe usingz\to\zeta
instead of(1z/\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
(1z/\zeta) \to 0
or perhapsT = 1/(1z/\zeta) \to \infty
.
 Should it be mentioned that (in terms and growth groups) a variable (
_var_
of the parent) represents/equals1 / (1z/\zeta)
?This should change once asymptotics
z>z_0
are implemented.What about "
T = 1/(1z/\zeta) \to \infty
where this element is a growth element (resp. monomial) inT
"?
I'm happy with this formulation.
All the other changes are positivly reviewed form my side.
comment:31 Changed 5 years ago by
 Commit changed from c79a6f7bbb3f17454a1c6238193696e525a8c0ec to 452c43bdcd74b18f166b9dda4c0936f51032eacc
Branch pushed to git repo; I updated commit sha1. New commits:
452c43b  Trac #19944: _singularity_analysis_ methods: more precise documentation

comment:32 in reply to: ↑ 30 ; followup: ↓ 33 Changed 5 years ago by
Replying to dkrenn:
What about "
T = 1/(1z/\zeta) \to \infty
where this element is a growth element (resp. monomial) inT
"?I'm happy with this formulation.
done. needs review.
comment:33 in reply to: ↑ 32 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:34 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/singularityanalysismethod to 452c43bdcd74b18f166b9dda4c0936f51032eacc
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
Trac #19532: Additional tests
Trac #19532: List log log factors, document missing implementations
Trac #19532: Add references
Merge branch 't/19532/asy/singularityanalysis' into t/17601/public/asy/trunk
Trac #19898: rename harmonic_number to HarmonicNumber
Merge branch 't/19898/asy/harmonicnumber' into t/17601/public/asy/trunk
add code for singularity analysis
add example
fix: .summand > .summands
add precision keyword