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

behackl · 2016-01-27T10:16:14Z

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

Depends on #19532
Depends on #19993
Depends on #20043

CC: @dkrenn @cheuberg

Component: asymptotic expansions

Author: Benjamin Hackl, Clemens Heuberger

Branch/Commit: b540598

Reviewer: Clemens Heuberger, Daniel Krenn

Issue created by migration from https://trac.sagemath.org/ticket/19969

The text was updated successfully, but these errors were encountered:

behackl · 2016-01-27T19:01:59Z

Branch: u/behackl/asy/SA-generator-log

behackl · 2016-01-27T19:01:59Z

Commit: 20d095e

behackl · 2016-01-27T19:01:59Z

comment:1

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`

sagetrac-git · 2016-01-28T23:49:51Z

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`

sagetrac-git · 2016-01-28T23:49:51Z

Changed commit from 20d095e to c83baa8

cheuberg · 2016-01-30T16:43:52Z

Reviewer: Clemens Heuberger

cheuberg · 2016-01-30T16:43:52Z

comment:4

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 single Gamma(alpha) is not really worthwhile. That would mean removing the parameter skip_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 by r in case beta not in ZZ in order to have consistent naming of summation indices.
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.

cheuberg · 2016-01-30T16:43:52Z

Author: Benjamin Hackl

cheuberg · 2016-02-07T13:46:58Z

comment:5

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

cheuberg · 2016-02-07T16:34:00Z

Changed branch from u/behackl/asy/SA-generator-log to u/cheuberg/asy/SA-generator-log

cheuberg · 2016-02-07T16:36:19Z

comment:7

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

done.

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`

cheuberg · 2016-02-07T16:36:19Z

Changed commit from c83baa8 to 7ad8f16

cheuberg · 2016-02-07T16:37:19Z

Changed dependencies from #19532 to #19532, #19993

dkrenn · 2016-02-12T13:36:27Z

Changed branch from u/cheuberg/asy/SA-generator-log to u/dkrenn/asy/SA-generator-log

dkrenn · 2016-02-12T13:37:16Z

Changed commit from 7ad8f16 to 33f675d

dkrenn · 2016-02-12T13:37:16Z

comment:10

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`

dkrenn · 2016-02-12T13:37:16Z

Changed dependencies from #19532, #19993 to #19532, #19993, #20043

sagetrac-git · 2016-02-12T13:51:41Z

Changed commit from 33f675d to dd7dabf

sagetrac-git · 2016-02-12T13:51:41Z

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`

cheuberg · 2016-02-12T18:04:46Z

comment:12

Replying to @sagetrac-git:


dd7dabf	`Trac #19969: fix doctest`

cross-reviewed the merge and the changes.

dkrenn · 2016-02-12T18:20:58Z

comment:13

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.

dkrenn · 2016-02-13T09:43:10Z

comment:19

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.

cheuberg · 2016-02-13T13:00:27Z

comment:20

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.

dkrenn · 2016-02-13T19:25:31Z

comment:21

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?

cheuberg · 2016-02-14T10:34:10Z

comment:23

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.

dkrenn · 2016-02-14T10:42:19Z

comment:24

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.

sagetrac-git · 2016-02-14T11:17:28Z

Changed commit from b540598 to d3b48c7

sagetrac-git · 2016-02-14T11:17:28Z

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`

sagetrac-git · 2016-02-14T11:20:06Z

Changed commit from d3b48c7 to b540598

sagetrac-git · 2016-02-14T11:20:06Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

dkrenn · 2016-02-14T11:21:18Z

comment:27

Replying to @sagetrac-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 SingularityAnalysis-generator`

Accidentally pushed on wrong ticket; is corrected now.

cheuberg · 2016-02-14T12:13:49Z

comment:28

Replying to @dkrenn:

Replying to @sagetrac-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 SingularityAnalysis-generator

Accidentally pushed on wrong ticket; is corrected now.

In that case, let's set it back to positive_review.

vbraun · 2016-02-15T19:28:35Z

Changed branch from u/dkrenn/asy/SA-generator-log to b540598

behackl added this to the sage-7.1 milestone Jan 27, 2016

behackl added c: asymptotic expansions labels Jan 27, 2016

behackl added the s: needs review label Jan 29, 2016

cheuberg added s: needs work and removed s: needs review labels Jan 30, 2016

cheuberg added s: needs review and removed s: needs work labels Feb 7, 2016

cheuberg added s: positive review and removed s: needs review labels Feb 13, 2016

dkrenn added s: needs info and removed s: positive review labels Feb 13, 2016

cheuberg added s: needs review and removed s: needs info labels Feb 14, 2016

dkrenn added s: positive review and removed s: needs review labels Feb 14, 2016

sagetrac-git mannequin added s: needs review and removed s: positive review labels Feb 14, 2016

cheuberg added s: positive review and removed s: needs review labels Feb 14, 2016

vbraun removed the s: positive review label Feb 15, 2016

vbraun closed this as completed in e514ec1 Feb 15, 2016

This was referenced Dec 29, 2022

Meta ticket: Asymptotic Expansions in SageMath #17601

Open

asymptotic expansions: singularity analysis #19944

Closed

cheuberg mentioned this issue Feb 15, 2016

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

Closed

dkrenn mentioned this issue Feb 15, 2016

singularity in formula in docstring of SingularityAnalysis-generator #20049

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

behackl commented Jan 27, 2016

behackl commented Jan 27, 2016

behackl commented Jan 27, 2016

behackl commented Jan 27, 2016

sagetrac-git mannequin commented Jan 28, 2016

sagetrac-git mannequin commented Jan 28, 2016

cheuberg commented Jan 30, 2016

cheuberg commented Jan 30, 2016

cheuberg commented Jan 30, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 12, 2016

sagetrac-git mannequin commented Feb 12, 2016

sagetrac-git mannequin commented Feb 12, 2016

cheuberg commented Feb 12, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 13, 2016

cheuberg commented Feb 13, 2016

dkrenn commented Feb 13, 2016

cheuberg commented Feb 14, 2016

dkrenn commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

dkrenn commented Feb 14, 2016

cheuberg commented Feb 14, 2016

vbraun commented Feb 15, 2016

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

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

Comments

behackl commented Jan 27, 2016

behackl commented Jan 27, 2016

behackl commented Jan 27, 2016

behackl commented Jan 27, 2016

sagetrac-git mannequin commented Jan 28, 2016

sagetrac-git mannequin commented Jan 28, 2016

cheuberg commented Jan 30, 2016

cheuberg commented Jan 30, 2016

cheuberg commented Jan 30, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

cheuberg commented Feb 7, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 12, 2016

sagetrac-git mannequin commented Feb 12, 2016

sagetrac-git mannequin commented Feb 12, 2016

cheuberg commented Feb 12, 2016

dkrenn commented Feb 12, 2016

dkrenn commented Feb 13, 2016

cheuberg commented Feb 13, 2016

dkrenn commented Feb 13, 2016

cheuberg commented Feb 14, 2016

dkrenn commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

sagetrac-git mannequin commented Feb 14, 2016

dkrenn commented Feb 14, 2016

cheuberg commented Feb 14, 2016

vbraun commented Feb 15, 2016