Opened 4 years ago

Closed 4 years ago

# asymptotic expansion generator: singularity analysis (log-type)

Reported by: Owned by: behackl major sage-7.1 asymptotic expansions dkrenn, cheuberg Benjamin Hackl, Clemens Heuberger Clemens Heuberger, Daniel Krenn N/A b540598 (Commits) b540598bc12c3d4540b0d5114b2e399dff502157 #19532, #19993, #20043

### Description

Follow-up to #19532. This ticket is for implementation of the case beta != 0.

### comment:1 Changed 4 years ago by behackl

• Branch set to u/behackl/asy/SA-generator-log
• Commit set to 20d095e178a23e2aa97b89afc294f044a519c1d9

Implemented the generator for beta != 0; some doctests still have to be written, but the method should work in general.

Last 10 new commits:

 ​5d6e9b2 Trac #19957: Introduce parameter relative tolerance ​00eae5d Merge branch 't/19957/asy/compare-with-values' into t/19510/asy/generators-binomial ​78bdd0f Trac #19510: additional doctests using compare_with_values ​148eabb Trac #19898: Merge #19510 ​a66c377 Trac #19898: additional doctest using compare_with_values ​5dc6f58 Trac #19532: Merge #19898 ​2b95429 Trac #19532: additional doctest using compare_with_values ​63f18f2 implement generator for beta not pos. integer ​cab11f4 add generalized lambda-coefficients ​20d095e implement log-generator for beta integer > 0

### comment:2 Changed 4 years ago by git

• Commit changed from 20d095e178a23e2aa97b89afc294f044a519c1d9 to c83baa89cb1f86815d85fd4cf9aa579ecc117d2a

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

 ​a17ee52 add name to file authors ​2957212 let ring work with given precision ​c83baa8 add doctests

### comment:3 Changed 4 years ago by behackl

• Status changed from new to needs_review

### comment:4 follow-ups: ↓ 5 ↓ 7 Changed 4 years ago by cheuberg

• Authors set to Benjamin Hackl
• Reviewers set to Clemens Heuberger
• Status changed from needs_review to needs_work

I had a first look at this implementation.

1. 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 single Gamma(alpha) is not really worthwhile. That would mean removing the parameter skip_constant_factor which seems to be less important here.
1. 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).
1. summation index k should be replaced by r in case beta not in ZZ in order to have consistent naming of summation indices.
1. Could you please post values for compare_with_values for alpha=2 and beta=1/2? With precision=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 cheuberg

1. 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.

1. Could you please post values for compare_with_values for alpha=2 and beta=1/2? With precision=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 cheuberg

• Branch changed from u/behackl/asy/SA-generator-log to u/cheuberg/asy/SA-generator-log

### comment:7 in reply to: ↑ 4 Changed 4 years ago by cheuberg

• Commit changed from c83baa89cb1f86815d85fd4cf9aa579ecc117d2a to 7ad8f1626cd0647f8de9105442cbe730dc1232da
• Status changed from needs_work to needs_review

1. 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 single Gamma(alpha) is not really worthwhile. That would mean removing the parameter skip_constant_factor which seems to be less important here.

done.

1. summation index k should be replaced by r 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/parse-symbolic' into t/19969/asy/SA-generator-log ​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 cheuberg

• Dependencies changed from #19532 to #19532, #19993

### comment:9 Changed 4 years ago by dkrenn

• Branch changed from u/cheuberg/asy/SA-generator-log to u/dkrenn/asy/SA-generator-log

### comment:10 Changed 4 years ago by dkrenn

• 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 merge-conflicts ​ebac5c2 Trac #20043: add additional doctest to check parent ​33f675d Merge branch 'u/dkrenn/asy/one-times-zero' of trac.sagemath.org:sage into t/19969/asy/SA-generator-log

### comment:11 follow-up: ↓ 12 Changed 4 years ago by git

• Commit changed from 33f675dd3e3aa3af5e0f993ae1fb9c7019a15e4c to dd7dabf33622b4c2d7257d2e43f4970092b6867a

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

 ​98e1fc7 Trac #20043: make error message more precise and flexibel ​99d7292 Merge branch 't/20043/asy/one-times-zero' into t/19969/asy/SA-generator-log ​dd7dabf Trac #19969: fix doctest

### comment:12 in reply to: ↑ 11 Changed 4 years ago by cheuberg

 ​dd7dabf Trac #19969: fix doctest

cross-reviewed the merge and the changes.

### comment:13 follow-up: ↓ 16 Changed 4 years ago by dkrenn

• 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=n-2)


does not seem to depend on the precision anymore for values at least 13.

### comment:14 Changed 4 years ago by git

• Commit changed from dd7dabf33622b4c2d7257d2e43f4970092b6867a to 456d8c383b55ab6ebbbd473370278180177326be

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

 ​617e5bf Trac #19969: rewrite output of doctest so that comparison with Formula in Flajolet-Sedgewick is easier ​456d8c3 Trac #19969: correct whitespaces

### comment:15 follow-up: ↓ 17 Changed 4 years ago by 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?

@Clemens: You should add yourself as author as well.

### comment:16 in reply to: ↑ 13 ; follow-up: ↓ 19 Changed 4 years ago by cheuberg

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=n-2)


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=n-2)
error = result[p] - result[p].exact_part()
if p >= 2:
print p, error, result[p] - result[p-1]


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 cheuberg

• Authors changed from Benjamin Hackl to Benjamin Hackl, Clemens Heuberger

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 git

• 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 ; follow-up: ↓ 20 Changed 4 years ago by dkrenn

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 cross-review 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 cheuberg

• Status changed from needs_review to positive_review

I'm finished my review. I've added an additional test. Please cross-review this commit and the minor changes yesterday. It's a positive review from my side.

Done, thanks.

### comment:21 follow-up: ↓ 23 Changed 4 years ago by dkrenn

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 dkrenn

• Status changed from positive_review to needs_info

### comment:23 in reply to: ↑ 21 ; follow-up: ↓ 24 Changed 4 years ago by cheuberg

• Status changed from needs_info to needs_review

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((1-z)^(-alpha) log(1/(1-z))^beta ) -> O(n^(alpha-1) 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^(alpha-1-precision)) 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 dkrenn

• Status changed from needs_review to positive_review

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((1-z)^(-alpha) log(1/(1-z))^beta ) -> O(n^(alpha-1) 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^(alpha-1-precision)) which does not seem to be that attractive --- and would cause pain later on in #19944.

Ok, thank you for your explanation.

### comment:25 follow-up: ↓ 27 Changed 4 years ago by git

• 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 SingularityAnalysis-generator

### comment:26 Changed 4 years ago by git

• 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 ; follow-up: ↓ 28 Changed 4 years ago by dkrenn

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 SingularityAnalysis-generator

Accidentally pushed on wrong ticket; is corrected now.

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

• Status changed from needs_review to positive_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 SingularityAnalysis-generator

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 vbraun

• Branch changed from u/dkrenn/asy/SA-generator-log to b540598bc12c3d4540b0d5114b2e399dff502157
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.