Opened 4 years ago
Closed 4 years ago
#19969 closed enhancement (fixed)
asymptotic expansion generator: singularity analysis (logtype)
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:  Clemens Heuberger, Daniel Krenn 
Report Upstream:  N/A  Work issues:  
Branch:  b540598 (Commits)  Commit:  b540598bc12c3d4540b0d5114b2e399dff502157 
Dependencies:  #19532, #19993, #20043  Stopgaps: 
Description
Followup to #19532. This ticket is for implementation of the case beta != 0
.
Change History (29)
comment:1 Changed 4 years ago by
 Branch set to u/behackl/asy/SAgeneratorlog
 Commit set to 20d095e178a23e2aa97b89afc294f044a519c1d9
comment:2 Changed 4 years ago by
 Commit changed from 20d095e178a23e2aa97b89afc294f044a519c1d9 to c83baa89cb1f86815d85fd4cf9aa579ecc117d2a
comment:3 Changed 4 years ago by
 Status changed from new to needs_review
comment:4 followups: ↓ 5 ↓ 7 Changed 4 years ago by
 Reviewers set to Clemens Heuberger
 Status changed from needs_review to needs_work
I had a first look at this implementation.
 I am not sure that three different implementations (beta=0, beta in ZZ and beta>0, otherwise) are needed: the only difference is the range over with
k
,l
,r
iterate and possibly the growth groups. But the basic coefficients stay the same. Perhaps we should even abolish the function_sa_coefficients_e_
because collecting for a singleGamma(alpha)
is not really worthwhile. That would mean removing the parameterskip_constant_factor
which seems to be less important here.
 the error term in the case of beta not in NN is not good, it should depend on beta (I very much prefer the strategy for beta in ZZ).
 summation index
k
should be replaced byr
in case beta not in ZZ in order to have consistent naming of summation indices.
 Could you please post values for
compare_with_values
foralpha=2
andbeta=1/2
? Withprecision=10
, I get[(5, 140.014037108338), (10, 432.585380667007), (20, 1894.51971835043), (40, 5905.52939497361), (80, 13574.5908343596)]
which I do not find convincing. Of course, convergence will be bad due to slow growth of logarithms, so larger values might be of interest, but I do currently lack computer power to test it myself. But that might be a consequence of 2.
comment:5 in reply to: ↑ 4 Changed 4 years ago by
Replying to cheuberg:
 the error term in the case of beta not in NN is not good, it should depend on beta (I very much prefer the strategy for beta in ZZ).
at second glance, the error term seems to be fine.
 Could you please post values for
compare_with_values
foralpha=2
andbeta=1/2
? Withprecision=10
, I get[(5, 140.014037108338), (10, 432.585380667007), (20, 1894.51971835043), (40, 5905.52939497361), (80, 13574.5908343596)]which I do not find convincing. Of course, convergence will be bad due to slow growth of logarithms, so larger values might be of interest, but I do currently lack computer power to test it myself. But that might be a consequence of 2.
this is settled, much larger values apparently lead to convergence.
comment:6 Changed 4 years ago by
 Branch changed from u/behackl/asy/SAgeneratorlog to u/cheuberg/asy/SAgeneratorlog
comment:7 in reply to: ↑ 4 Changed 4 years ago by
 Commit changed from c83baa89cb1f86815d85fd4cf9aa579ecc117d2a to 7ad8f1626cd0647f8de9105442cbe730dc1232da
 Status changed from needs_work to needs_review
Replying to cheuberg:
 I am not sure that three different implementations (beta=0, beta in ZZ and beta>0, otherwise) are needed: the only difference is the range over with
k
,l
,r
iterate and possibly the growth groups. But the basic coefficients stay the same. Perhaps we should even abolish the function_sa_coefficients_e_
because collecting for a singleGamma(alpha)
is not really worthwhile. That would mean removing the parameterskip_constant_factor
which seems to be less important here.
done.
 summation index
k
should be replaced byr
in case beta not in ZZ in order to have consistent naming of summation indices.
done.
This amounts to a major rewrite of the code (old case beta=0 as well as new case). Please review.
New commits:
f39f484  Trac #19993: Arb: parse symbolic expressions

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

comment:8 Changed 4 years ago by
 Dependencies changed from #19532 to #19532, #19993
comment:9 Changed 4 years ago by
 Branch changed from u/cheuberg/asy/SAgeneratorlog to u/dkrenn/asy/SAgeneratorlog
comment:10 Changed 4 years ago by
 Commit changed from 7ad8f1626cd0647f8de9105442cbe730dc1232da to 33f675dd3e3aa3af5e0f993ae1fb9c7019a15e4c
 Dependencies changed from #19532, #19993 to #19532, #19993, #20043
Merged #20043 due to a conflict; is now on 7.1.beta3.
New commits:
ea85895  new NotImplementedOZero in misc

d5c664e  remove old NotImplementedOZero and use new one

143c048  O(0) in asymptotic expansion

fb8a9d4  1*0 in asymptotic ring

b1c3f1b  correct other empty sums

a87009d  fix O(0)doctest

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

comment:11 followup: ↓ 12 Changed 4 years ago by
 Commit changed from 33f675dd3e3aa3af5e0f993ae1fb9c7019a15e4c to dd7dabf33622b4c2d7257d2e43f4970092b6867a
comment:12 in reply to: ↑ 11 Changed 4 years ago by
comment:13 followup: ↓ 16 Changed 4 years ago by
 Reviewers changed from Clemens Heuberger to Clemens Heuberger, Daniel Krenn
I'm in the middle of the review.
I didn't investigate further, but the (correct) result of
sage: asymptotic_expansions.SingularityAnalysis('n', ....: alpha=0, beta=2, precision=23).subs(n=n2)
does not seem to depend on the precision anymore for values at least 13.
comment:14 Changed 4 years ago by
 Commit changed from dd7dabf33622b4c2d7257d2e43f4970092b6867a to 456d8c383b55ab6ebbbd473370278180177326be
comment:15 followup: ↓ 17 Changed 4 years ago by
Code looks good. I didn't review the extension of _sa_coefficients_lambda_
directly (only indirectly, since the overall results are correct). Git blame says Benjamin has done these changes; Clemens, did you have a look at these changes?
@Clemens: You should add yourself as author as well.
comment:16 in reply to: ↑ 13 ; followup: ↓ 19 Changed 4 years ago by
Replying to dkrenn:
I'm in the middle of the review.
I didn't investigate further, but the (correct) result of
sage: asymptotic_expansions.SingularityAnalysis('n', ....: alpha=0, beta=2, precision=23).subs(n=n2)does not seem to depend on the precision anymore for values at least 13.
What is n
? Could it be that it is the generator of an asymptotic ring with lower default precision?
I cannot reproduce the problem:
result = {} for p in range(1, 20): a = asymptotic_expansions.SingularityAnalysis('n', alpha=0, beta=2, precision=p) n = a.parent().gen() result[p] = a.subs(n=n2) error = result[p]  result[p].exact_part() if p >= 2: print p, error, result[p]  result[p1]
yields
2 O(n^(1)) O(n^(1)*log(n)) 3 O(n^(2)*log(n)^2) O(n^(1)) 4 O(n^(2)*log(n)) O(n^(2)*log(n)^2) 5 O(n^(2)) O(n^(2)*log(n)) 6 O(n^(3)*log(n)^2) O(n^(2)) 7 O(n^(3)*log(n)) O(n^(3)*log(n)^2) 8 O(n^(3)) O(n^(3)*log(n)) 9 O(n^(4)*log(n)^2) O(n^(3)) 10 O(n^(4)*log(n)) O(n^(4)*log(n)^2) 11 O(n^(4)) O(n^(4)*log(n)) 12 O(n^(5)*log(n)^2) O(n^(4)) 13 O(n^(5)*log(n)) O(n^(5)*log(n)^2) 14 O(n^(5)) O(n^(5)*log(n)) 15 O(n^(6)*log(n)^2) O(n^(5)) 16 O(n^(6)*log(n)) O(n^(6)*log(n)^2) 17 O(n^(6)) O(n^(6)*log(n)) 18 O(n^(7)*log(n)^2) O(n^(6)) 19 O(n^(7)*log(n)) O(n^(7)*log(n)^2)
so the result gets better in every iteration. Due to cancellations, some of the coefficients are not present ...
comment:17 in reply to: ↑ 15 Changed 4 years ago by
Replying to dkrenn:
Code looks good. I didn't review the extension of
_sa_coefficients_lambda_
directly (only indirectly, since the overall results are correct). Git blame says Benjamin has done these changes; Clemens, did you have a look at these changes?
Yes. The only difference is that (1+1/v) * (1+v*t).log()
representing the logarithm of the denominator z^(n+1)
has been changed to (1+1/v+beta) * (1+v*t).log()
representing the logarithm of the denominator z^(n+1+beta)
where the additional factor z^beta
comes from the renormalization of the logarithmic factor.
@Clemens: You should add yourself as author as well.
Done, thanks for the reminder.
comment:18 Changed 4 years ago by
 Commit changed from 456d8c383b55ab6ebbbd473370278180177326be to b540598bc12c3d4540b0d5114b2e399dff502157
Branch pushed to git repo; I updated commit sha1. New commits:
b540598  Trac #19969: add an additional doctest

comment:19 in reply to: ↑ 16 ; followup: ↓ 20 Changed 4 years ago by
Replying to cheuberg:
What is
n
? Could it be that it is the generator of an asymptotic ring with lower default precision?
Indeed, n
was the problem. Thanks for pointing this out.
I'm finished my review. I've added an additional test. Please crossreview this commit and the minor changes yesterday. It's a positive review from my side.
comment:20 in reply to: ↑ 19 Changed 4 years ago by
 Status changed from needs_review to positive_review
Replying to dkrenn:
I'm finished my review. I've added an additional test. Please crossreview this commit and the minor changes yesterday. It's a positive review from my side.
Done, thanks.
comment:21 followup: ↓ 23 Changed 4 years ago by
During review of #19944 I've noticed that
sage: asymptotic_expansions.SingularityAnalysis('n', 2, 1, precision=1)
raises a NotImplementedOZero
error, but
sage: asymptotic_expansions.SingularityAnalysis('n', 2, 1, precision=0) O((1/2)^n*n^(2))
which is not incorrect, but also seems not to be consistent to the above. Is there a particular reason for this?
comment:22 Changed 4 years ago by
 Status changed from positive_review to needs_info
comment:23 in reply to: ↑ 21 ; followup: ↓ 24 Changed 4 years ago by
 Status changed from needs_info to needs_review
Replying to dkrenn:
which is not incorrect, but also seems not to be consistent to the above. Is there a particular reason for this?
It was an easy option to implement the transfer theorem: O((1z)^(alpha) log(1/(1z))^beta )
> O(n^(alpha1) log^beta(n))
.
Having this for precision=0
allows us to reuse the same logic for handling the location of the singularity, for constructing the ring etc. It even does not require us the write any specific code, apart from the one position where we explicitly do not raise NotImplementedOZero
.
Finally, setting precision=0
calls for an O
term to be returned, so returning the O
term which arises naturally seems to be a good option.
In some sense, returning NotImplementedOZero
at all is perhaps some kind of hack, but the alternative would be to return something like O(n^(alpha1precision))
which does not seem to be that attractive  and would cause pain later on in #19944.
comment:24 in reply to: ↑ 23 Changed 4 years ago by
 Status changed from needs_review to positive_review
Replying to cheuberg:
Replying to dkrenn:
which is not incorrect, but also seems not to be consistent to the above. Is there a particular reason for this?
It was an easy option to implement the transfer theorem:
O((1z)^(alpha) log(1/(1z))^beta )
>O(n^(alpha1) log^beta(n))
.Having this for
precision=0
allows us to reuse the same logic for handling the location of the singularity, for constructing the ring etc. It even does not require us the write any specific code, apart from the one position where we explicitly do notraise NotImplementedOZero
.Finally, setting
precision=0
calls for anO
term to be returned, so returning theO
term which arises naturally seems to be a good option.In some sense, returning
NotImplementedOZero
at all is perhaps some kind of hack, but the alternative would be to return something likeO(n^(alpha1precision))
which does not seem to be that attractive  and would cause pain later on in #19944.
Ok, thank you for your explanation.
comment:25 followup: ↓ 27 Changed 4 years ago by
 Commit changed from b540598bc12c3d4540b0d5114b2e399dff502157 to d3b48c7070f8b3a7e0851c5ed6d62e5d95472a0a
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
d3b48c7  Trac #20049: \zeta in GF in SingularityAnalysisgenerator

comment:26 Changed 4 years ago by
 Commit changed from d3b48c7070f8b3a7e0851c5ed6d62e5d95472a0a to b540598bc12c3d4540b0d5114b2e399dff502157
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:27 in reply to: ↑ 25 ; followup: ↓ 28 Changed 4 years ago by
comment:28 in reply to: ↑ 27 Changed 4 years ago by
 Status changed from needs_review to positive_review
Replying to dkrenn:
Replying to git:
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
d3b48c7 Trac #20049: \zeta in GF in SingularityAnalysisgenerator
Accidentally pushed on wrong ticket; is corrected now.
In that case, let's set it back to positive_review
.
comment:29 Changed 4 years ago by
 Branch changed from u/dkrenn/asy/SAgeneratorlog to b540598bc12c3d4540b0d5114b2e399dff502157
 Resolution set to fixed
 Status changed from positive_review to closed
Implemented the generator for
beta != 0
; some doctests still have to be written, but the method should work in general.Last 10 new commits:
Trac #19957: Introduce parameter relative tolerance
Merge branch 't/19957/asy/comparewithvalues' into t/19510/asy/generatorsbinomial
Trac #19510: additional doctests using compare_with_values
Trac #19898: Merge #19510
Trac #19898: additional doctest using compare_with_values
Trac #19532: Merge #19898
Trac #19532: additional doctest using compare_with_values
implement generator for beta not pos. integer
add generalized lambdacoefficients
implement loggenerator for beta integer > 0