Opened 7 years ago
Closed 6 years ago
#17716 closed enhancement (fixed)
AsymptoticRing and AsymptoticExpression
Reported by:  behackl  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  asymptotic expansions  Keywords:  asymptotics, gsoc15 
Cc:  dkrenn, cheuberg, ncohen, vdelecroix, tmonteil  Merged in:  
Authors:  Benjamin Hackl, Daniel Krenn  Reviewers:  Daniel Krenn, Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  e8e2501 (Commits, GitHub, GitLab)  Commit:  e8e2501fd4b08280cbca5aca749191a743c0ff01 
Dependencies:  #17693, #17715, #19017  Stopgaps: 
Description (last modified by )
We want to implement asymptotic expressions like (5 * n * 2^{n}  2 * n^{2/3} + O(n * log(n))) based on our implementation of asymptotic terms (i.e. objects which contain a growth and possibly some additional information; see ticket #17715) and the MutablePoset data structure (see ticket #17693).
Basically, an asymptotic expression represents the sum of asymptotic terms. The terms are stored within an MutablePoset, which is helpful for the management of the terms, as absorption of terms (and their predecessors w.r.t. growth) can be handled efficiently.
For example:
(n^{3} + n^{2} + n + 1) + (O(n^{2})) evaluates to (n^{3} + O(n^{2})), because the O term absorbs n^{2} and its predecessors, which is information that is stored in the MutablePoset.
Another more complex example would be:
(4 * n^{2} * t + 3 * n * t^{2} + O(n)) + (O(n^{2} * t^{3/2})) evaluates to (3 * n * t^{2} + O(n^{2} * t^{3/2})). Here, the MutablePoset behind the term (4 * n^{2} * t + 3 * n * t^{2} + O(n)) incorporates the relations
n <= 4 * n^2 * t
andn <= 3 * n * t^2
, whereas the expression (O(n^{2} * t^{3/2})) only contains the term n^{2} * t^{3/2}, and thus the corresponding MutablePoset contains no relations. Adding these two terms translates into merging the two underlying posets. By inserting the term O(n^{2} * t^{3/2}) into the first poset, new relations4 * n^2 * t <= n^2 * t^(3/2)
andn <= n^2 * t^(3/2)
are discovered. As O terms absorb terms of weaker or equal growth, the term 4 * n^{2} * t and O(n) are removed from the poset. As noted above, the remaining elements form the asymptotic expression (3 * n * t^{2} + O(n^{2} * t^{3/2})).
Concretely, we plan to implement the elements AsymptoticExpression (with parent AsymptoticRing) whose objects act as described above.
Within this ticket, a minimal working prototype shall be implemented, such that univariate, polynomial expressions can be handeled.
See metaticket #17601 for the planned structure and a roadmap.
Change History (48)
comment:1 Changed 7 years ago by
 Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 7 years ago by
 Cc ncohen vdelecroix tmonteil added
comment:3 Changed 6 years ago by
 Branch set to u/behackl/asy/asymptoticExpression
 Commit set to 8dc7df1fd1c8cee8ff4ac8f6eb8eb2fc4d1b3e3b
 Dependencies set to #17600, #17693, #17715
 Description modified (diff)
 Keywords gsoc15 added
comment:4 Changed 6 years ago by
 Commit changed from 8dc7df1fd1c8cee8ff4ac8f6eb8eb2fc4d1b3e3b to f2d04482a41c65c597e939dbf6b0a8c3df7aa2ad
comment:5 Changed 6 years ago by
 Commit changed from f2d04482a41c65c597e939dbf6b0a8c3df7aa2ad to fb9e828ecf3e7444a983924275ba6aaee0c11d48
comment:6 Changed 6 years ago by
 Commit changed from fb9e828ecf3e7444a983924275ba6aaee0c11d48 to 9b24fa77d1e94fa61593d10b4c6a645430799c10
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
a5fd74d  introduction of short notation for growth groups + factory

6e9652b  comparison with mul_vararg

637d4cb  header modified

8404c32  Merge branch 'asy/asymptoticTerm' into

8bf88cf  doctests fixed

d34a451  asymptotic ring, classcall: short notation can be used to specify the

2c59df1  doctests fixed ('monomial' > gone)

8833c6a  adapted documentation and header

371a53a  representation: 1*x > x; 1*x > x etc.

9b24fa7  Merge branch 'asy/asymptoticTerm' into

comment:7 Changed 6 years ago by
 Dependencies changed from #17600, #17693, #17715 to #17600, #17693, #17715, #18930
comment:8 Changed 6 years ago by
 Commit changed from 9b24fa77d1e94fa61593d10b4c6a645430799c10 to 8b1d0213349d676a7722bdf25c545b0d100069c1
Branch pushed to git repo; I updated commit sha1. New commits:
8b1d021  doctests fixed

comment:9 Changed 6 years ago by
 Branch changed from u/behackl/asy/asymptoticExpression to u/dkrenn/asy/asymptoticExpression
comment:10 Changed 6 years ago by
 Commit changed from 8b1d0213349d676a7722bdf25c545b0d100069c1 to bb75902c876d7c8a0a834995044aa44e5a4634bb
 Reviewers set to Daniel Krenn
Last 10 new commits:
8584f57  write __len__

a1678ed  remove TODOlist of methods (list is now in separat branch)

1c6b196  write methods for maximal/minimal elements

ec5c3b7  Merge branch 'asy/poset' into asy/ring

f6bc337  implement __nonzero__

001d921  adapt O (previous merge and __nonzero__)

825bcbc  remove reverse from _repr_ and reverse by default

0cfa751  fix doctests (_repr_ reverse)

4a2f31a  minor rewrite of docstring

bb75902  _repr_: handle a minus correct

comment:11 Changed 6 years ago by
 Commit changed from bb75902c876d7c8a0a834995044aa44e5a4634bb to 12d88c95c4f0718ac59a0cf75171356d46eb8392
comment:12 Changed 6 years ago by
 Branch changed from u/dkrenn/asy/asymptoticExpression to u/behackl/asy/asymptoticExpression
 Commit changed from 12d88c95c4f0718ac59a0cf75171356d46eb8392 to b5e76acb1104af129176af6d40eb035cb986466a
Last 10 new commits:
12d88c9  restructure creation of empty data structures (give them their own method)

f141775  typos in module description fixed

62d824f  Merge branch 'asy/growthGroup' into asy/growthGroupfactory

116ab14  Merge branch 'asy/growthGroupfactory' into asy/asymptoticTerm

164e39c  experimental warning: refer to #17601

7eecfe2  improved representation strings

c35a63d  Merge branch 'asy/asymptoticTerm' into asy/asymptoticExpression

618de1c  experimental warning for terms: refer to #17601

df6346f  typo fixed

b5e76ac  use len(poset) instead of len(poset._shells_)

comment:13 Changed 6 years ago by
 Commit changed from b5e76acb1104af129176af6d40eb035cb986466a to 556a263b637708766158efab3ca4c7f013b07449
Branch pushed to git repo; I updated commit sha1. New commits:
ea67ace  call x.O(**kwds) if possible

b018387  code simplification

6b111ce  add keywords to all constructors

b4e2526  improved docstring

3145afd  improved code formatting (PEP 8)

556a263  merged branch 'asy/big_oh' into asy/asymptoticExpression and resolved a small conflict

comment:14 Changed 6 years ago by
 Dependencies changed from #17600, #17693, #17715, #18930 to #17600, #17693, #17715, #18930, #19017
comment:15 Changed 6 years ago by
 Commit changed from 556a263b637708766158efab3ca4c7f013b07449 to 8016a1dea945f23ff61a083519d56bc42cca7875
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
b766273  Merge branch 'asy/asymptoticTerm' into asy/asymptoticExpression

d92d3ec  parsing of logoperands fixed

63f4cfe  Merge branch 'asy/asymptoticTerm' into asy/asymptoticExpression

25ce229  added some line wraps

1aa0648  fixed two doctests

eb32b4c  bracket notation only works if the underlying growth group has a generator

3749fa1  refactored handling of generators

ba16c0f  Merge branch 'asy/growthGroup' into asy/growthGroupfactory

4616535  Merge branch 'asy/growthGroupfactory' into asy/asymptoticTerm

8016a1d  Merge branch 'asy/asymptoticTerm' into asy/asymptoticExpression

comment:16 Changed 6 years ago by
 Commit changed from 8016a1dea945f23ff61a083519d56bc42cca7875 to 914271a79482f8202326aef6b0ab7aa62c2df02f
Branch pushed to git repo; I updated commit sha1. New commits:
c6d8584  error with the element constructor fixed, doctest added

3564d23  Merge branch 'asy/growthGroup' into asy/growthGroupfactory

0b53b76  Merge branch 'asy/growthGroupfactory' into asy/asymptoticTerm

914271a  Merge branch 'asy/asymptoticTerm' into asy/asymptoticExpression

comment:17 Changed 6 years ago by
 Summary changed from AsymptoticExpression to AsymptoticRing and AsymptoticExpression
comment:18 Changed 6 years ago by
 Branch changed from u/behackl/asy/asymptoticExpression to u/dkrenn/asy/asymptoticExpression
comment:19 Changed 6 years ago by
 Branch changed from u/dkrenn/asy/asymptoticExpression to u/behackl/asy/asymptoticExpression
 Commit changed from 914271a79482f8202326aef6b0ab7aa62c2df02f to f11877232543a2d08b45f2a1924793ad129b7576
Last 10 new commits:
8263e39  include asymptotic ring in reference manual

c756025  correct broken link

22fcbc4  rewrite docstring of AsymptoticRing

acfb983  rewrite docstring of AsymptoticExpression

fc61df6  write module description and introductory examples

aa4c647  Merge branch 'u/dkrenn/asy/asymptoticExpression' into asy/asymptoticExpression

5911564  typo fixed and line break introduced

7aa3e60  `QQ` > `\mathbb{Q}`

3e2a7b3  typo fixed

f118772  some SEEALSOblocks added

comment:20 Changed 6 years ago by
 Branch changed from u/behackl/asy/asymptoticExpression to u/dkrenn/asy/asymptoticExpression
comment:21 Changed 6 years ago by
 Commit changed from f11877232543a2d08b45f2a1924793ad129b7576 to 64563002a4d2579b7eb280c1807d108af51e3ea3
Branch pushed to git repo; I updated commit sha1. New commits:
6456300  minor rewording in docstring

comment:22 Changed 6 years ago by
 Status changed from new to needs_review
comment:23 Changed 6 years ago by
During the project #17601 (the last months in course of GSOC2015 as mentor) I did a very careful reviewing of all code. This includes the code of this ticket. Now this is clearly a positive_review from my side.
comment:24 Changed 6 years ago by
 Branch changed from u/dkrenn/asy/asymptoticExpression to u/behackl/asy/asymptoticExpression
 Commit changed from 64563002a4d2579b7eb280c1807d108af51e3ea3 to c7afc80e1ff9218390aa501b8f1a94a517e0bab9
Last 10 new commits:
7774ff2  fixed doctests

878ef2a  fixed documentation build

5fd9662  Merge branch 'asy/growthGroup' into asy/growthGroupfactory

f20c42e  fixing doctests

38e73c8  Merge branch 'asy/growthGroupfactory' into asy/asymptoticTerm

ae6a9bb  fixed doctests

79be7d6  documentation builds again

6d01815  Merge branch 'asy/asymptoticTerm' into asy/asymptoticExpression

f6c4d80  doctests fixed

c7afc80  building documentation fixed

comment:25 Changed 6 years ago by
 Commit changed from c7afc80e1ff9218390aa501b8f1a94a517e0bab9 to 4e7b080f1e7da508c319d7b0c7a7ea40ccd97521
Branch pushed to git repo; I updated commit sha1. New commits:
9305ca5  add . after seealsolists

50d7166  \mathbb{Q} > \QQ

2f8146d  doctests: add growth_group= and coefficient_ring= to AsymptoticRing(...) generation

6456300  minor rewording in docstring

4e7b080  Merge branch 'u/dkrenn/asy/asymptoticExpression' into asy/asymptoticExpression and fixed some merge conflicts

comment:26 Changed 6 years ago by
 Commit changed from 4e7b080f1e7da508c319d7b0c7a7ea40ccd97521 to 83f74d397fab0ceb49865e3d8dade30a4d7aa758
comment:27 Changed 6 years ago by
 Branch changed from u/behackl/asy/asymptoticExpression to u/dkrenn/asy/asymptoticExpression
comment:28 Changed 6 years ago by
 Commit changed from 83f74d397fab0ceb49865e3d8dade30a4d7aa758 to 2c1c39d91e323921dd02427799c1912fb02a2aa1
Merged 6.9.beta5
New commits:
1c81c12  language oddities fixed

032d8b8  Merge branch 'asy/growthGroup' into asy/growthGroupfactory

3a05be7  Merge tag '6.9.beta5' into t/17600/asy/growthGroup

58f931d  add asymptotic_expansions index

9d6f2da  Merge branch 't/17600/asy/growthGroup' into t/18930/asy/growthGroupfactory

6da5ade  Merge branch 't/18930/asy/growthGroupfactory' into t/17715/asy/asymptoticTerm

2c1c39d  Merge branch 't/17715/asy/asymptoticTerm' into t/17716/asy/asymptoticExpression

comment:29 Changed 6 years ago by
 Component changed from symbolics to asymptotic expansions
comment:30 Changed 6 years ago by
 Branch changed from u/dkrenn/asy/asymptoticExpression to u/behackl/asy/asymptoticExpression
 Commit changed from 2c1c39d91e323921dd02427799c1912fb02a2aa1 to d1336d3a96ec370504172b3897f72783ca4c9be5
Merged positively reviewed version of #17715 into this branch.
Last 10 new commits:
67a73ca  improved some doctests

fe906ca  reintroduce _le_ for TermWithCoefficient

5cb54ae  equality comparison for terms

14e3e63  improve documentation: information on comparison

ce7e2a3  Trac #17715: avoid the use of repr in doctest

7b29b28  Trac #17715: do not include "the" in internal link texts

b22a24b  Trac #17715: Fix ReSt error

abc6a16  Merge branch 'u/cheuberg/asy/asymptoticTerm' of git://trac.sagemath.org/sage into asy/asymptoticTerm

aea0ae8  Trac #17715: Minor language adjustments

d1336d3  Merge branch 'asy/asymptoticTerm' into asy/asymptoticExpression

comment:31 Changed 6 years ago by
 Commit changed from d1336d3a96ec370504172b3897f72783ca4c9be5 to 5f54aecc2a188ccf2711946c655c271386ae32c6
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
33c4102  mark doctests in .le as indirect

b31fac8  rewrite a couple of oneline descriptions

17e921f  remove sorted_set_by_tuple

7af4b6b  remove reverse keyword from shells

a49a20d  add comment in code to make it clear what happens

89b8209  change left/right to self/other

1d52f6c  add a note to the set operations methods

3b3b2fb  object > SageObject

572a95d  Merge branch 'asy/mutableposet' into asy/asymptoticExpression

5f54aec  explicitly forbid coercion from MutablePoset into the AsymptoticRing

comment:32 Changed 6 years ago by
 Branch changed from u/behackl/asy/asymptoticExpression to u/cheuberg/asy/asymptoticExpression
comment:33 Changed 6 years ago by
 Commit changed from 5f54aecc2a188ccf2711946c655c271386ae32c6 to 4bb745f5d9f796c8485d23536cd456dde8a2201e
 Milestone changed from sage6.5 to sage6.9
 Reviewers changed from Daniel Krenn to Daniel Krenn, Clemens Heuberger
 Status changed from needs_review to needs_work
I have read the code and the documentation. I have pushed a few reviewer commits (please crossreview). Apart from that, I have a few comments/questions:
 Introductory examples,
A.an_element()
: why is this not tested? AsymptoticExpression.__init__
: all doctests are indirect; however seeingsimplify
in action as well as a poset might be more interesting.AsymptoticExpression.__pow__
: How difficult would it be to allow the computation of(y^2)^(3/2)
?AsymptoticExpression.__pow__
: move powers of asymptotic terms to the respective classes instead of the hack here.AsymptoticRing
: "TEST": what is the purpose of this test? Isn't all that already tested?AsymptoticRing.__classcall__
: the if clauseif names is not None
does not seem to be prepared to multiple generators.AsymptoticRing.__classcall__
: deal with parametercategory
AsymptoticRing.__init__
: include doctests for error conditions.AsymptoticRing._element_constructor_
: clarify thatdata=0
is required ifsummands is not None
AsymptoticRing._element_constructor_
: doctests for use ofsummands
, for error conditionsAsymptoticRing._coerce_map_from_
: why is the testif R == MutablePoset
required?
Last 10 new commits:
b92eb2a  Trac #17716: minor language issues

61017c7  Trac #17716: use next function instead of next method (Python3 compatible)

0dc81e8  Trac #17716: language

6f0d60f  Trac #17716: simplified doctest

8b29f92  Trac #17716: additional doctests

451b5e8  Trac #17716: PEP8 compliance

7381430  Trac #17716: "not implemented" instead of "not tested"

9bf196a  Trac #17716: fix errors

a188101  Trac #17716: fix TeX errors in docstrings

4bb745f  Trac #17716: Heading "Classes and Methods"

comment:34 followup: ↓ 41 Changed 6 years ago by
One more comment:
 In my opinion, with this ticket, the documentation should no longer be hidden, because the asymptotic ring in this version does something which was previously impossible in SageMath (fractional exponents).
comment:35 Changed 6 years ago by
Code breaks on 6.9.rc0 (change of imports in sage/rings/all.py
). Merge 6.9.rc0 and adapt.
comment:36 Changed 6 years ago by
 Branch changed from u/cheuberg/asy/asymptoticExpression to u/behackl/asy/asymptoticExpression
 Commit changed from 4bb745f5d9f796c8485d23536cd456dde8a2201e to f5f7dcf8bb0c20bd3fc6212015b82e9cfd8691e1
comment:37 Changed 6 years ago by
 Commit changed from f5f7dcf8bb0c20bd3fc6212015b82e9cfd8691e1 to abb08ff241086ac0faee88969a4d6f190244de7f
comment:38 Changed 6 years ago by
 Status changed from needs_work to needs_review
Hello Clemens!
I crossreviewed your changes (they look fine), and here are some answers to your comments:
Replying to cheuberg:
I have read the code and the documentation. I have pushed a few reviewer commits (please crossreview). Apart from that, I have a few comments/questions:
 Introductory examples,
A.an_element()
: why is this not tested?
Because this already gives the result of our implementation of an_element
from #19048. It is tested there.
AsymptoticExpression.__init__
: all doctests are indirect; however seeingsimplify
in action as well as a poset might be more interesting.
I copied and adapted a doctest from _simplify_
.
AsymptoticExpression.__pow__
: How difficult would it be to allow the computation of(y^2)^(3/2)
?AsymptoticExpression.__pow__
: move powers of asymptotic terms to the respective classes instead of the hack here.
Both 3. and 4. are fixed in #19083: especially the __pow__
methods were heavily changed and split.
AsymptoticRing
: "TEST": what is the purpose of this test? Isn't all that already tested?
Cannot recall the intention behind this test. Deleted.
AsymptoticRing.__classcall__
: the if clauseif names is not None
does not seem to be prepared to multiple generators.
This is because this world works entirely without cartesian products. Our efforts on the "cartesian product" front get merged with the "asymptotic ring" font in #19073.
AsymptoticRing.__classcall__
: deal with parametercategory
The entire __classcall__
has been rewritten in #19083, categories are handled correctly there.
AsymptoticRing.__init__
: include doctests for error conditions.
Done.
AsymptoticRing._element_constructor_
: clarify thatdata=0
is required ifsummands is not None
Added a similar note as for the element constructor of the growth group.
AsymptoticRing._element_constructor_
: doctests for use ofsummands
, for error conditions
Done. (And fixed the typo in 'ambiguous' ;)
)
AsymptoticRing._coerce_map_from_
: why is the testif R == MutablePoset
required?
This is a premature fix for a problem arising in #19083: when passing a MutablePoset
to the ring such that the element constructor builds an expansion, coerce_map_from
is called with the class of the poset (as the poset has no parent). Without this, a lot of bad stuff happens.
comment:39 Changed 6 years ago by
 Branch changed from u/behackl/asy/asymptoticExpression to u/cheuberg/asy/asymptoticExpression
comment:40 Changed 6 years ago by
 Commit changed from abb08ff241086ac0faee88969a4d6f190244de7f to 055e35bf7632c403be96371ce4f56f128534a307
comment:41 in reply to: ↑ 34 ; followup: ↓ 43 Changed 6 years ago by
Replying to cheuberg:
One more comment:
 In my opinion, with this ticket, the documentation should no longer be hidden, because the asymptotic ring in this version does something which was previously impossible in SageMath (fractional exponents).
any thoughts on that?
Apart from that, I reviewed your changes and added two minor reviewer commits.
comment:42 Changed 6 years ago by
 Branch changed from u/cheuberg/asy/asymptoticExpression to u/dkrenn/asy/asymptoticExpression
comment:43 in reply to: ↑ 41 Changed 6 years ago by
 Commit changed from 055e35bf7632c403be96371ce4f56f128534a307 to e8e2501fd4b08280cbca5aca749191a743c0ff01
Replying to cheuberg:
Replying to cheuberg:
One more comment:
 In my opinion, with this ticket, the documentation should no longer be hidden, because the asymptotic ring in this version does something which was previously impossible in SageMath (fractional exponents).
any thoughts on that?
Included.
Apart from that, I reviewed your changes and added two minor reviewer commits.
...ok.
New commits:
e8e2501  make entry in reference/index

comment:44 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:45 followup: ↓ 46 Changed 6 years ago by
.. toctree:: :hidden: asymptotic_expansions_index
could now be removed from src/doc/en/reference/rings/index.rst
.
But this can wait until one of the followup tickets.
And in src/doc/output/html/en/reference/rings/asymptotic_expansions_index.html
, the very first line could be a pointer towards the introductory material in the asymptotic ring instead of a logical listing starting with the growth group.
comment:46 in reply to: ↑ 45 Changed 6 years ago by
Replying to cheuberg:
.. toctree:: :hidden: asymptotic_expansions_indexcould now be removed from
src/doc/en/reference/rings/index.rst
.But this can wait until one of the followup tickets.
Ok (probably #19083).
And in
src/doc/output/html/en/reference/rings/asymptotic_expansions_index.html
, the very first line could be a pointer towards the introductory material in the asymptotic ring instead of a logical listing starting with the growth group.
This is done in #19083.
comment:47 Changed 6 years ago by
 Dependencies changed from #17600, #17693, #17715, #18930, #19017 to #17693, #17715, #19017
comment:48 Changed 6 years ago by
 Branch changed from u/dkrenn/asy/asymptoticExpression to e8e2501fd4b08280cbca5aca749191a743c0ff01
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
implemented __pow__ for asymptotic expressions
doctests for _simplify_