Opened 3 years ago

Closed 3 years ago

#19969 closed enhancement (fixed)

asymptotic expansion generator: singularity analysis (log-type)

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: Clemens Heuberger, Daniel Krenn
Report Upstream: N/A Work issues:
Branch: b540598 (Commits) Commit: b540598bc12c3d4540b0d5114b2e399dff502157
Dependencies: #19532, #19993, #20043 Stopgaps:

Description

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

Change History (29)

comment:1 Changed 3 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:

5d6e9b2Trac #19957: Introduce parameter relative tolerance
00eae5dMerge branch 't/19957/asy/compare-with-values' into t/19510/asy/generators-binomial
78bdd0fTrac #19510: additional doctests using compare_with_values
148eabbTrac #19898: Merge #19510
a66c377Trac #19898: additional doctest using compare_with_values
5dc6f58Trac #19532: Merge #19898
2b95429Trac #19532: additional doctest using compare_with_values
63f18f2implement generator for beta not pos. integer
cab11f4add generalized lambda-coefficients
20d095eimplement log-generator for beta integer > 0

comment:2 Changed 3 years ago by git

  • Commit changed from 20d095e178a23e2aa97b89afc294f044a519c1d9 to c83baa89cb1f86815d85fd4cf9aa579ecc117d2a

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

a17ee52add name to file authors
2957212let ring work with given precision
c83baa8add doctests

comment:3 Changed 3 years ago by behackl

  • Status changed from new to needs_review

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

Replying to 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 3 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 3 years ago by cheuberg

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

Replying to cheuberg:

  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:

f39f484Trac #19993: Arb: parse symbolic expressions
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

comment:8 Changed 3 years ago by cheuberg

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

comment:9 Changed 3 years ago by dkrenn

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

comment:10 Changed 3 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:

ea85895new NotImplementedOZero in misc
d5c664eremove old NotImplementedOZero and use new one
143c048O(0) in asymptotic expansion
fb8a9d41*0 in asymptotic ring
b1c3f1bcorrect other empty sums
a87009dfix O(0)-doctest
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

comment:11 follow-up: Changed 3 years ago by git

  • Commit changed from 33f675dd3e3aa3af5e0f993ae1fb9c7019a15e4c to dd7dabf33622b4c2d7257d2e43f4970092b6867a

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

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

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

Replying to git:

dd7dabfTrac #19969: fix doctest

cross-reviewed the merge and the changes.

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

  • Commit changed from dd7dabf33622b4c2d7257d2e43f4970092b6867a to 456d8c383b55ab6ebbbd473370278180177326be

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

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

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=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 3 years ago by cheuberg

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

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 3 years ago by git

  • Commit changed from 456d8c383b55ab6ebbbd473370278180177326be to b540598bc12c3d4540b0d5114b2e399dff502157

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

b540598Trac #19969: add an additional doctest

comment:19 in reply to: ↑ 16 ; follow-up: Changed 3 years ago by dkrenn

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 cross-review this commit and the minor changes yesterday. It's a positive review from my side.

comment:20 in reply to: ↑ 19 Changed 3 years ago by cheuberg

  • Status changed from needs_review to positive_review

Replying to dkrenn:

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

  • Status changed from positive_review to needs_info

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

  • 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((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 3 years ago by dkrenn

  • 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((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: Changed 3 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:

d3b48c7Trac #20049: \zeta in GF in SingularityAnalysis-generator

comment:26 Changed 3 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: Changed 3 years ago by dkrenn

Replying to git:

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

d3b48c7Trac #20049: \zeta in GF in SingularityAnalysis-generator

Accidentally pushed on wrong ticket; is corrected now.

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

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

d3b48c7Trac #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 3 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.