Opened 5 years ago
Closed 5 years ago
#17715 closed enhancement (fixed)
AsymptoticTerm
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  Reviewers:  Daniel Krenn, Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  aea0ae8 (Commits)  Commit:  aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c 
Dependencies:  #17600, #18930, #19237  Stopgaps: 
Description (last modified by )
Asymptotic terms are expressions like O(n^{2}), 7 * n * 2^{n}, or 42 * n * log(n). They build upon the asymptotic growth elements from #17600, which are elements like n^{2}, n*2^{n} and n * log(n) (that is, they handle only the asymptotic growth).
All asymptotic terms have an attribute 'growth' (which is some growth element), and then they may have additional information (like, for example, a coefficient in the case of exact terms).
Currently, we implemented the following asymptotic terms (plus their monoid parents):
 GenericTerm
 Implements the base structure of asymptotic terms.
 OTerm
 Class for big O terms. These terms may "absorb" other asymptotic terms with weaker or equal growth.
 TermWithCoefficient
 Generic base class for asymptotic terms with coefficient. Base class for asymptotic exact terms and asymptotic L terms.
 ExactTerm
 Class for asymptotic exact terms. These terms correspond to symbolic expressions like, for example, 2 * x^{3}, 7 * x^{2/5}, or 42 * x^{1/3} * log(x).
Asymptotic terms may be multiplied and absorbed; addition will be handled by AsymptoticExpression.
See metaticket #17601 for the planned structure.
Change History (44)
comment:1 Changed 5 years ago by
 Cc ncohen vdelecroix tmonteil added
comment:2 Changed 5 years ago by
 Branch set to u/behackl/asy/asymptoticTerm
 Commit set to cd4c640179f27a8516a119e11415f8116b452635
comment:3 Changed 5 years ago by
 Commit changed from cd4c640179f27a8516a119e11415f8116b452635 to 7ef7cb402e0d99c6e59346d7412b25993d41d745
comment:4 Changed 5 years ago by
 Commit changed from 7ef7cb402e0d99c6e59346d7412b25993d41d745 to eb4c8af525e41e334dc8241ec9daf2ace3e3c1f6
Branch pushed to git repo; I updated commit sha1. New commits:
0a603f3  import have_same_parent from sage.structure.element instead of .sage_object

1eef695  merge fix of import deprecation (have_same_parent) for asy/growthElement into asy/asymptoticTerm

eb4c8af  import have_same_parent from sage.structure.element

comment:5 Changed 5 years ago by
 Commit changed from eb4c8af525e41e334dc8241ec9daf2ace3e3c1f6 to 042e9c1b85a2dd1b0a5805699697baa0cf369744
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
4e80522  repr: checking for integers with isinstance introduces problems with

4207fce  a base is valid, if it inherits from Parent

e48afc9  minor documentation improvements

73017ab  conversion from multivariate polynomial rings and multivariate power

167dec3  merge the clean and crossreviewed version of asy/growthGroup into asy/asymptoticTerm

ae273d8  fixed doctests due to changes to asy/growthGroup

ea07028  growth group has to be specified; choice no longer defaults to GenericGrowthGroup.

8a206a3  replaced most double quotes by single quotes (consistency with asy/growthGroup)

1ee90ea  improved and simplified documentation (consistency with asy/growthGroup)

042e9c1  coefficients have to be specified explicitly; no default values.

comment:6 Changed 5 years ago by
 Commit changed from 042e9c1b85a2dd1b0a5805699697baa0cf369744 to a589d8d4e3dbfbc25e453f7f33529ca599df3ef8
Branch pushed to git repo; I updated commit sha1. New commits:
2dfe905  added a factory for asymptotic terms

234945c  adapted import statements (consistency with asy/growthGroup)

5f513a7  module description added

cc6a431  _mul_ calls the parent to construct a new element

414a2c6  simplified documentation of _repr_

95f98c8  various improvements of the documentation.

ce7a2a3  reworked the element constructor and added doctests for growth group conversion

a589d8d  generation of L terms using the factory documented

comment:7 Changed 5 years ago by
 Commit changed from a589d8d4e3dbfbc25e453f7f33529ca599df3ef8 to 0c8099e644102fcae9407b6f7200f80ffd07aa0e
Branch pushed to git repo; I updated commit sha1. New commits:
a2840b3  fixed can_absorb for generic L terms

a4d5c5f  _coerce_map_from_ > has_coerce_map_from in doctests

ee8272c  fixed conversion from multivariate power series rings; replaced PolynomialRing and PowerSeriesRing in doc by bracketnotation

fde1604  Merge branch 'asy/growthGroup' into asy/asymptoticTerm

66e4d4e  can_absorb now calls helper functions _can_absorb_

c7ef699  implemented the conversion of suitable monomials with coefficient to terms with coefficient

a5b0ba0  postponed the implementation of L terms after having a minimal working example

0c8099e  implemented a flag for can_absorb

comment:8 Changed 5 years ago by
 Commit changed from 0c8099e644102fcae9407b6f7200f80ffd07aa0e to 0d7ce6b628ef3ae399cf00d874ccbfc4de97734e
comment:9 Changed 5 years ago by
 Branch changed from u/behackl/asy/asymptoticTerm to u/dkrenn/asy/asymptoticTerm
comment:10 Changed 5 years ago by
 Commit changed from 0d7ce6b628ef3ae399cf00d874ccbfc4de97734e to 373dda9bc08ca928dda27998035d0860e0cb556c
 Reviewers set to Daniel Krenn
Last 10 new commits:
28dc2a8  moved _can_absorb_ in code directly below can_absorb

3546ed4  docstring enhancements in GenericTerm

4f53a8b  improve docstrings of term monoid

5128036  remove default None from constructor of generic term monoid

16c407e  simplify code of _coerce_map_from_

ae361b5  remove else branch and move block to the left (_element_constructor_) to increase readability

f6799c5  improve docstrings

f189e1c  some minor code rewritings

253556f  add an additional doctest

373dda9  fixed broken doctests

comment:11 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/asymptoticTerm to u/behackl/asy/asymptoticTerm
 Commit changed from 373dda9bc08ca928dda27998035d0860e0cb556c to 0d7ce6b628ef3ae399cf00d874ccbfc4de97734e
 Dependencies set to #17600
 Keywords gsoc15 added
Last 10 new commits:
a4d5c5f  _coerce_map_from_ > has_coerce_map_from in doctests

ee8272c  fixed conversion from multivariate power series rings; replaced PolynomialRing and PowerSeriesRing in doc by bracketnotation

fde1604  Merge branch 'asy/growthGroup' into asy/asymptoticTerm

66e4d4e  can_absorb now calls helper functions _can_absorb_

c7ef699  implemented the conversion of suitable monomials with coefficient to terms with coefficient

a5b0ba0  postponed the implementation of L terms after having a minimal working example

0c8099e  implemented a flag for can_absorb

3cbeac3  helper methods for asymptotic expressions added

676c3d8  fixed a bug with conversion of the variable without powers

0d7ce6b  adapted representation of exact terms to the representation of

comment:12 Changed 5 years ago by
 Commit changed from 0d7ce6b628ef3ae399cf00d874ccbfc4de97734e to 7f2c5842f61d78663fd3c61e303cfe864fc558a1
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
dadef25  _base_ring > _base_ring_ + property

65301c7  changed representation string of TermWithCoefficientMonoid and

710f54f  refactored comparison for TermWithCoefficient and GenericTerm

5a4b631  fixed some typos

d73ce3e  added docstring for create_object

38b8836  specified exceptions caught in _element_constructor_

172824a  improved doctests: avoided tuple assignments

aa68142  O term(s) et al > `O`terms

1712037  improved documentation: simplified variable names in doctests

7f2c584  links repaired and header modified

comment:13 Changed 5 years ago by
 Description modified (diff)
comment:14 Changed 5 years ago by
 Commit changed from 7f2c5842f61d78663fd3c61e303cfe864fc558a1 to e6101a9b4bacd120d1b5e171563b32076f059c03
comment:15 Changed 5 years ago by
 Commit changed from e6101a9b4bacd120d1b5e171563b32076f059c03 to 42b45b8572f652c1b9b8feb6efc5f575b8443aee
Branch pushed to git repo; I updated commit sha1. New commits:
42b45b8  fixed helper function can_absorb

comment:16 Changed 5 years ago by
 Commit changed from 42b45b8572f652c1b9b8feb6efc5f575b8443aee to 637d4cb0188f2df312f95eeaf3801779a57b0d40
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
907e82d  docstrings for _repr*_ methods

6c8b543  changed default representation to short representation

2903a9a  helper method for short representation implemented

c916514  implemented a helper method for the growth group factory

ae0fff3  factory for growth groups implemented

9c3a08e  Merge branch 'asy/growthGroupfactory' into asy/asymptoticTerm

2010268  fixed doctest in can_absorb + improved documentation

a5fd74d  introduction of short notation for growth groups + factory

6e9652b  comparison with mul_vararg

637d4cb  header modified

comment:17 Changed 5 years ago by
 Dependencies changed from #17600 to #17600, #18930
comment:18 Changed 5 years ago by
 Commit changed from 637d4cb0188f2df312f95eeaf3801779a57b0d40 to 371a53afb8ac0c8aa91e5d67c241fcca2826ee2f
Branch pushed to git repo; I updated commit sha1. New commits:
371a53a  representation: 1*x > x; 1*x > x etc.

comment:19 Changed 5 years ago by
 Commit changed from 371a53afb8ac0c8aa91e5d67c241fcca2826ee2f to 7eecfe2014598d97048fc3fd98e552baa31f38f1
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
655ec12  rename to repr_short_to_parent

e60a325  rewrite growth group factory

ea8ae66  reproption to suppress words "Growth Group"

b7f5c73  rename reproptionkeyword and minor change in output

c0ec9fd  minor change in output of repr

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

comment:20 Changed 5 years ago by
 Commit changed from 7eecfe2014598d97048fc3fd98e552baa31f38f1 to fcf9581cd4b9fb08a65fb53cb713efa5fc048fcf
Branch pushed to git repo; I updated commit sha1. New commits:
fcf9581  minor simplification for the term factory

comment:21 Changed 5 years ago by
 Commit changed from fcf9581cd4b9fb08a65fb53cb713efa5fc048fcf to 461653586dd4f5b03df53c317bb4cbe78d8c08ed
Branch pushed to git repo; I updated commit sha1. New commits:
164d21e  compare exponents directly instead with is_le_one

baa8f7c  implemented gens_monomial and adapted gen, gens, ngens

b477c62  merge branch 'asy/growthGroup' into asy/growthGroupfactory and resolve a minor conflict

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

d92d3ec  parsing of logoperands fixed

3749fa1  refactored handling of generators

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

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

comment:22 Changed 5 years ago by
 Commit changed from 461653586dd4f5b03df53c317bb4cbe78d8c08ed to 0b53b76fa63afb0b275e953984a4e99dc84d16ef
comment:23 Changed 5 years ago by
comment:24 Changed 5 years ago by
 Status changed from new to needs_review
comment:25 Changed 5 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:26 Changed 5 years ago by
 Commit changed from 0b53b76fa63afb0b275e953984a4e99dc84d16ef to 79be7d6f4584f596bbdcad03b419db88b3d6b782
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
e8662cd  collect asymptotic code in one directory

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

7fba1fe  Merge branch 'asy/growthGroupfactory' into asy/asymptoticTerm

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

comment:27 Changed 5 years ago by
 Commit changed from 79be7d6f4584f596bbdcad03b419db88b3d6b782 to 7b8c1a097e0ce5c23e7ad9cfd006138557b44a49
Branch pushed to git repo; I updated commit sha1. New commits:
7b8c1a0  fixed a conversion issue for terms with coefficient

comment:28 Changed 5 years ago by
 Branch changed from u/behackl/asy/asymptoticTerm to u/dkrenn/asy/asymptoticTerm
comment:29 Changed 5 years ago by
 Commit changed from 7b8c1a097e0ce5c23e7ad9cfd006138557b44a49 to 6da5ade0a4f8ece3054b2a2a6fdd095ffec71e76
Merge 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

comment:30 Changed 5 years ago by
 Component changed from symbolics to asymptotic expansions
comment:31 Changed 5 years ago by
 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
$ ./sage docbuild u file=src/sage/rings/asymptotic/term_monoid.py html ... Error building the documentation. ... Traceback (most recent call last): ... OSError: [html ] /home/sci/cheuberg/.sage/docbuild/term_monoid/source/term_monoid.py:docstring of term_monoid.OTermMonoid._coerce_map_from_:33: WARNING: Inline interpreted text or phrase reference startstring without endstring.
comment:32 Changed 5 years ago by
 Branch changed from u/dkrenn/asy/asymptoticTerm to u/behackl/asy/asymptoticTerm
 Commit changed from 6da5ade0a4f8ece3054b2a2a6fdd095ffec71e76 to cc55be7405533455d24c378e8d2deb93a6831495
 Status changed from needs_work to needs_review
Fixed the docbuildissue, made some small documentationrelated changes, and merged the latest version of #18930 into this branch. Back to needs_review
.
Last 10 new commits:
3f88a9a  duplicate doctest removed

9489bad  element_constructor: input clarification; doctests marked as indirect

053ee33  type(...) == ... > isinstance(...)

7b49489  clarification gens vs. gens_monomial

2bf6868  prevent strange NotImplementedError from PowerSeriesRing

4f99031  Merge branch 'asy/growthGroup' into asy/growthGroupfactory

7c3f6b8  Merge branch 'asy/growthGroupfactory' into asy/asymptoticTerm

6f251fd  fixed typo

dfb8d41  fixed formatting issue

cc55be7  fixed indentation of one block

comment:33 Changed 5 years ago by
 Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm
comment:34 Changed 5 years ago by
 Commit changed from cc55be7405533455d24c378e8d2deb93a6831495 to 347f080df240102799ded90067cbd01beaa386a4
 Dependencies changed from #17600, #18930 to #17600, #18930, #19237
 Status changed from needs_review to needs_work
I reviewed this ticket, added a few reviewer commits and have a few comments:
absorption
: OneSentenceDescription should describe what this function does. What happens if the elements are not comparable (documentation; probably only possible in a followup ticket)?can_absorb
: OneSentenceDescription, then NOTE section would be superfluous.GenericTerm.__init__
: Provide doctests for error conditionsGenericTerm.can_absorb
andGenericTerm._can_absorb_
: Why two methods?GenericTerm.absorb
: what happens ifcheck
is not set? Why would one want to call that?GenericTerm.absorb
, last 3 lines of code: isn't it quite confusing to overrideself
andother
in thelambda
expression?GenericTerm._absorb_
: the method is never called in the doctests, in particular, theNotImplementedError
does not show up.GenericTermMonoid.__init__
: see #17600, comment 40: handling of tuples as parametercategory
,__classcall__
for parametercategory
; same question for derived classes?GenericTermMonoid.__init__
: documentation says thatgrowth_group
has to be a "partially ordered group" with aGenericGrowthGroup
only listed as an example; code explicitly requires aGenericGrowthGroup
.GenericTermMonoid._element_constructor_
: why exampleT_QQ.coerce(term1)
instead ofT_QQ(term1)
?GenericTermMonoid._element_constructor_
: whytype(data) == self.element_class
and notisinstance(data, self.element_class)
? Similarly for other parents.OTermMonoid._coerce_map_from_
: documentation does not agree with code: according to the documentation,S
must be anOTermMonoid
or anExactTermMonoid
. However, the code does not enforce the former.TermWithCoefficient._le_
: The comparison of coefficients is not documented. Apart from that, do we really want thatx <= 2*I*x
when the coefficient ring is complex?TermWithCoefficientMonoid._init_
: check error conditionTermWithCoefficientMonoid.base_ring
: why is this a property instead of a function? Compare with ring of polynomials.TermWithCoefficientMonoid._coerce_map_from_
: documentation mentions "this exact term monoid", but this is aTermWithCoefficientMonoid
.ExactTerm._repr_
: I do not like the checkself.growth._raw_element_ == 0
,self.growth
is the identity element of that group, so we should check for that. I'd prefer
.is_zero()
over== 0
. TermMonoidFactory.create_key_and_extra_args
: test error conditions
New commits:
88b9294  Trac #19237: Fix ReSt errors in reference/rings

a7361b2  Trac #17715: Merge #19237 to ease review

148b0b8  Trac #17715: minor documentation issues

9f8a248  Trac #17715: remove duplicate line in doctest

d870c90  Trac #17715: Documentation: language

d4c2b0a  Trac #17715: Fix/insert links

a2dfd22  Trac #17715: ReSt error

f6882fe  Trac #17715: additional doctest for explanation

347f080  Trac #17715: emphasize that 'O' is capital letter and not digit

comment:35 followup: ↓ 36 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/asymptoticTerm to u/behackl/asy/asymptoticTerm
 Commit changed from 347f080df240102799ded90067cbd01beaa386a4 to 0bac3bb892aab1e2ae42a20b9f50458fa36acd13
 Status changed from needs_work to needs_review
Hello Clemens!
Replying to cheuberg:
I reviewed this ticket, added a few reviewer commits and have a few comments:
absorption
: OneSentenceDescription should describe what this function does. What happens if the elements are not comparable (documentation; probably only possible in a followup ticket)?
I adapted the short description and slightly adapted the code, such that a different ArithmeticError is raised. (This should not introduce a merge conflict, this code did not change up to (and including) the cleanup ticket #19083.)
can_absorb
: OneSentenceDescription, then NOTE section would be superfluous.
Done.
GenericTerm.__init__
: Provide doctests for error conditions
I did introduce some tests  however, only for those errors that are also raised on the cleanup ticket #19083 (... one less thing to think about when merging the changes into there). If you would prefer a full error coverage on this ticket as well, let me know.
GenericTerm.can_absorb
andGenericTerm._can_absorb_
: Why two methods?
As far as I can remember, we wanted can_absorb
to be a publicly accessible function, but in the documentation it should not apper too often. Thus, we wrote one public (welldocumented) function that calls _can_absorb_
, and implemented _can_absorb_
in the derived classes only.
In any case, I suppose we could change that, as we documented all the "technical" _can_absorb_
functions also quite well. What do you think would be cleaner?
GenericTerm.absorb
: what happens ifcheck
is not set? Why would one want to call that?
At some point we wanted an option to surpress this check because in the AsymptoticRing
, the MutablePoset
calls can_absorb
really very often, which makes it a bottleneck, up to some degree. In certain cases, for example when adding an O
term into a MutablePoset
, then the poset first needs to do some comparisons in order to place the O
term correctlyand then, in a second step, the O
term absorbs all predecessors (without additional comparison!), because O
terms can absorb anything with weaker growth.
This was the motivation to have some option that allows to skip the test. Actually doing this optimization ishoweverstill on our TODOlist.
GenericTerm.absorb
, last 3 lines of code: isn't it quite confusing to overrideself
andother
in thelambda
expression?
Yes, it really is. Changed to left
and right
.
GenericTerm._absorb_
: the method is never called in the doctests, in particular, theNotImplementedError
does not show up.
Added a doctest that directly calls GenericTerm._absorb_
.
GenericTermMonoid.__init__
: see #17600, comment 40: handling of tuples as parametercategory
,__classcall__
for parametercategory
; same question for derived classes?
Like with the GrowthGroup
, this is already fixed in #19083. Thus, I'd leave this as is.
GenericTermMonoid.__init__
: documentation says thatgrowth_group
has to be a "partially ordered group" with aGenericGrowthGroup
only listed as an example; code explicitly requires aGenericGrowthGroup
.
This has been partially changed in #19083. There, the growth group only has to be a parent  but we should probably also check, whether the category of the passed growth group is a subcategory of Posets()
. This would also fit to the suggested changes in #18223.
In any case, as this ticket enforces the growth group to be derived from GenericGrowthGroup
, the category is also a subcategory of Posets()
. Thus, I'd also vote for leaving this as is.
GenericTermMonoid._element_constructor_
: why exampleT_QQ.coerce(term1)
instead ofT_QQ(term1)
?
Changed.
GenericTermMonoid._element_constructor_
: whytype(data) == self.element_class
and notisinstance(data, self.element_class)
? Similarly for other parents.
Changed.
OTermMonoid._coerce_map_from_
: documentation does not agree with code: according to the documentation,S
must be anOTermMonoid
or anExactTermMonoid
. However, the code does not enforce the former.
Yes, it doeshowever, it's not really obvious. Calling
super(OTermMonoid, self)._coerce_map_from_(S)
enforces this, as we check isinstance(S, self.__class__)
there.
TermWithCoefficient._le_
: The comparison of coefficients is not documented. Apart from that, do we really want thatx <= 2*I*x
when the coefficient ring is complex?
This is problematic. For now, I've included a check for the imaginary partbut if the coefficient ring is not ordered, this still causes problems.
I suppose that we could discuss removing _le_
for these terms altogether, or make terms of equal growth always incomparable: terms of equal growth are not handled via comparison, but via absorption...
TermWithCoefficientMonoid._init_
: check error condition
Rewritten. Now checks whether base_ring
is in Rings()
.
TermWithCoefficientMonoid.base_ring
: why is this a property instead of a function? Compare with ring of polynomials.
I believe that this makes some of the code in #19083 that handles the pushoutstuff (... changing the base ring ...) easier. Also, I think that having this as a property is overall cleaner.
Let me know if you think that we should enforce consistency with the PolynomialRing
.
TermWithCoefficientMonoid._coerce_map_from_
: documentation mentions "this exact term monoid", but this is aTermWithCoefficientMonoid
.
Fixed.
ExactTerm._repr_
: I do not like the checkself.growth._raw_element_ == 0
,self.growth
is the identity element of that group, so we should check for that.
Fixed in #19083.
 I'd prefer
.is_zero()
over== 0
.
Changed everywhere in #19083.
TermMonoidFactory.create_key_and_extra_args
: test error conditions
Added some more tests.
I pushed my changes to this ticket; please crossreview them and let me know how you want to proceed regarding the open questions.
Thanks for the review!
Benjamin
Last 10 new commits:
3b0a678  improve absorb, can_absorb

5aa190e  test for checking parent of growth in __init__

ea89a53  lambda: self, other > left, right

d6de96c  test _absorb_

cf9f007  use call instead of .coerce(..)

6bfb92f  type(..) == ... > isinstance(...)

483f6b9  fix comparison of terms with complex coefficients

1920865  fix docstring of _coerce_map_from_ from term with coefficient monoid

1217348  improve handling of base_ring for term with coefficient monoid

0bac3bb  add more tests for TermMonoidFactory

comment:36 in reply to: ↑ 35 Changed 5 years ago by
 Status changed from needs_review to needs_info
Replying to behackl:
GenericTerm.can_absorb
andGenericTerm._can_absorb_
: Why two methods?As far as I can remember, we wanted
can_absorb
to be a publicly accessible function, but in the documentation it should not apper too often. Thus, we wrote one public (welldocumented) function that calls_can_absorb_
, and implemented_can_absorb_
in the derived classes only.In any case, I suppose we could change that, as we documented all the "technical"
_can_absorb_
functions also quite well. What do you think would be cleaner?
My impression when reviewing this ticket was that absorption is explained many times. Perhaps these explanations and examples could have been collected in one place (either in the module documentation or in the relevant methods in the base class). Then the documentation of all overriden classes could have included a link to the general explanation and only explain the particularities of the respective class. Having the explanation in the docstring of a method of the base class would have the advantage that users of method?
could also access it.
This module is of rather technical nature anyway and the end user will hopefully rarely look into it. Thus reducing the number of occurrences of can_absorb
in the reference manual does not concern me too much.
IMHO, having can_absorb
as a trivial wrapper around _can_absorb_
has a (very slight) performance penalty and makes future reading of the code somewhat harder.
GenericTerm.absorb
: what happens ifcheck
is not set? Why would one want to call that?At some point we wanted an option to surpress this check because in the
AsymptoticRing
, theMutablePoset
callscan_absorb
really very often, which makes it a bottleneck, up to some degree. In certain cases, for example when adding anO
term into aMutablePoset
, then the poset first needs to do some comparisons in order to place theO
term correctlyand then, in a second step, theO
term absorbs all predecessors (without additional comparison!), becauseO
terms can absorb anything with weaker growth.This was the motivation to have some option that allows to skip the test. Actually doing this optimization ishoweverstill on our TODOlist.
Could you add one sentence to the documentation? Something like "Setting check=False
is meant to be used in cases where the truth of can_absorb
has been checked in advance to avoid duplicate checking."
GenericTermMonoid.__init__
: documentation says thatgrowth_group
has to be a "partially ordered group" with aGenericGrowthGroup
only listed as an example; code explicitly requires aGenericGrowthGroup
.This has been partially changed in #19083. There, the growth group only has to be a parent  but we should probably also check, whether the category of the passed growth group is a subcategory of
Posets()
. This would also fit to the suggested changes in #18223.In any case, as this ticket enforces the growth group to be derived from
GenericGrowthGroup
, the category is also a subcategory ofPosets()
. Thus, I'd also vote for leaving this as is.
I think that if the current code expects the growth group to be a GenericGrowthGroup
, then the documentation should state that.
GenericTermMonoid._element_constructor_
: why exampleT_QQ.coerce(term1)
instead ofT_QQ(term1)
?Changed.
The attached comment should also be changed. Having a look again, I now partially understand why coerce
was called in the first place: it seems to explain why comparison in the line above could work. However, in the _element_constructor_
method, I expected to see an example of conversion.
Perhaps both could be included: first conversion, then comparison and the explanation that coercion did actually work.
TermWithCoefficient._le_
: The comparison of coefficients is not documented. Apart from that, do we really want thatx <= 2*I*x
when the coefficient ring is complex?This is problematic. For now, I've included a check for the imaginary partbut if the coefficient ring is not ordered, this still causes problems.
I suppose that we could discuss removing
_le_
for these terms altogether, or make terms of equal growth always incomparable: terms of equal growth are not handled via comparison, but via absorption...
I do not know yet what the usecase for comparison of elements of equal growth was supposed to be. For me, only comparing the growth would be sufficient. Mixing the order of the growth group and the order of the base ring seems to be some kind of overkill, if at all possible.
I am not sure, though, whether x <= 2*x
and 2*x <= x
should hold. Or what about mixing exact terms and O
terms.
Are distinct conventions for _le_
and can_absorb
necessary?
TermWithCoefficientMonoid.base_ring
: why is this a property instead of a function? Compare with ring of polynomials.I believe that this makes some of the code in #19083 that handles the pushoutstuff (... changing the base ring ...) easier.
Could someone elaborate on that?
Also, I think that having this as a property is overall cleaner.
Why?
Including this ticket, we have 74 classes with base_ring
,
$rgrep 'def base_ring'  wc 74 230 4186
and one of them (this ticket) has it as a property:
$ rgrep C1 'def base_ring' . grep property ./rings/asymptotic/term_monoid.py @property
Let me know if you think that we should enforce consistency with the
PolynomialRing
.
I'd like to see more convincing arguments before breaking consistency with 73 other sage modules.
I pushed my changes to this ticket; please crossreview them and let me know how you want to proceed regarding the open questions.
done.
I have one further question not discussed so far:
absorb
uses the coercion framework before calling_absorb_
with guaranteed equal parents.can_absorb
does not. Is there a reason for that? Does only the growth group play a role here, so that different parents do not really matter?
comment:37 Changed 5 years ago by
 Commit changed from 0bac3bb892aab1e2ae42a20b9f50458fa36acd13 to 67a73cabf434ab2d6642db0b9e5e8eeec9767feb
Branch pushed to git repo; I updated commit sha1. New commits:
0da8a7a  improved module documentation

3964eae  _can_absorb_ > can_absorb

820e310  base_ring is now a function, not a property

4afce6c  removed TermWithCoefficient._le_, improved documentation of __le__ and _le_

6d23773  clarification of growth_group in GenericTermMonoid.__init__

ad0754c  shifted documentation of absorption towards module description

0eaa472  remark regarding keyword check in GenericTerm.absorb

67a73ca  improved some doctests

comment:38 followup: ↓ 40 Changed 5 years ago by
 Status changed from needs_info to needs_review
Replying to cheuberg:
My impression when reviewing this ticket was that absorption is explained many times. Perhaps these explanations and examples could have been collected in one place (either in the module documentation or in the relevant methods in the base class). Then the documentation of all overriden classes could have included a link to the general explanation and only explain the particularities of the respective class. Having the explanation in the docstring of a method of the base class would have the advantage that users of
method?
could also access it.This module is of rather technical nature anyway and the end user will hopefully rarely look into it. Thus reducing the number of occurrences of
can_absorb
in the reference manual does not concern me too much.IMHO, having
can_absorb
as a trivial wrapper around_can_absorb_
has a (very slight) performance penalty and makes future reading of the code somewhat harder.
I think that you are right. I've collected the documentation for absorb
and can_absorb
and put it in a section of the module description. The respective methods now only have a short documentation (explaining their own behavior), and a reference to that section.
GenericTerm.absorb
: what happens ifcheck
is not set? Why would one want to call that?At some point we wanted an option to surpress this check because in the
AsymptoticRing
, theMutablePoset
callscan_absorb
really very often, which makes it a bottleneck, up to some degree. In certain cases, for example when adding anO
term into aMutablePoset
, then the poset first needs to do some comparisons in order to place theO
term correctlyand then, in a second step, theO
term absorbs all predecessors (without additional comparison!), becauseO
terms can absorb anything with weaker growth.This was the motivation to have some option that allows to skip the test. Actually doing this optimization ishoweverstill on our TODOlist.
Could you add one sentence to the documentation? Something like "Setting
check=False
is meant to be used in cases where the truth ofcan_absorb
has been checked in advance to avoid duplicate checking."
Done.
GenericTermMonoid.__init__
: documentation says thatgrowth_group
has to be a "partially ordered group" with aGenericGrowthGroup
only listed as an example; code explicitly requires aGenericGrowthGroup
.This has been partially changed in #19083. There, the growth group only has to be a parent  but we should probably also check, whether the category of the passed growth group is a subcategory of
Posets()
. This would also fit to the suggested changes in #18223.In any case, as this ticket enforces the growth group to be derived from
GenericGrowthGroup
, the category is also a subcategory ofPosets()
. Thus, I'd also vote for leaving this as is.I think that if the current code expects the growth group to be a
GenericGrowthGroup
, then the documentation should state that.
It does so now.
GenericTermMonoid._element_constructor_
: why exampleT_QQ.coerce(term1)
instead ofT_QQ(term1)
?Changed.
The attached comment should also be changed. Having a look again, I now partially understand why
coerce
was called in the first place: it seems to explain why comparison in the line above could work. However, in the_element_constructor_
method, I expected to see an example of conversion. Perhaps both could be included: first conversion, then comparison and the explanation that coercion did actually work.
I don't think that conversion is at work in this particular sectionin any case, I've rewritten these doctests slightly in order to better reflect what we want to demonstrate.
TermWithCoefficient._le_
: The comparison of coefficients is not documented. Apart from that, do we really want thatx <= 2*I*x
when the coefficient ring is complex?This is problematic. For now, I've included a check for the imaginary partbut if the coefficient ring is not ordered, this still causes problems.
I suppose that we could discuss removing
_le_
for these terms altogether, or make terms of equal growth always incomparable: terms of equal growth are not handled via comparison, but via absorption...I do not know yet what the usecase for comparison of elements of equal growth was supposed to be. For me, only comparing the growth would be sufficient. Mixing the order of the growth group and the order of the base ring seems to be some kind of overkill, if at all possible.
I am not sure, though, whether
x <= 2*x
and2*x <= x
should hold. Or what about mixing exact terms andO
terms.Are distinct conventions for
_le_
andcan_absorb
necessary?
In fact, we only need the comparison of the underlying growth. I've deleted TermWithCoefficient._le_
and rewritten the documentation of GenericTerm.__le__
and GenericTerm._le_
in order to reflect that.
As this isas you already saida rather technical class, I think that it can be justified if <=
only compares growth. However, if we follow this approach, then x <= 2*x
and 2*x <= x
would both yield True
, but x == 2*x
would be false (because as far as I can remember, we need ==
to actually check if the coefficients are the same too, somewhere in the AsymptoticRing
). Any thoughts?
TermWithCoefficientMonoid.base_ring
: why is this a property instead of a function? Compare with ring of polynomials.I believe that this makes some of the code in #19083 that handles the pushoutstuff (... changing the base ring ...) easier.
Could someone elaborate on that?
Also, I think that having this as a property is overall cleaner.
Why?
Including this ticket, we have 74 classes with
base_ring
,$rgrep 'def base_ring'  wc 74 230 4186and one of them (this ticket) has it as a property:
$ rgrep C1 'def base_ring' . grep property ./rings/asymptotic/term_monoid.py @propertyLet me know if you think that we should enforce consistency with the
PolynomialRing
.I'd like to see more convincing arguments before breaking consistency with 73 other sage modules.
Mea culpa, I was wrong. Later on, we renamed base_ring
to coefficient_ring
but as far as I've looked up, we never acutally set the property outside of initialization. So this could easily become a function (which is what I also changed here).
I pushed my changes to this ticket; please crossreview them and let me know how you want to proceed regarding the open questions.
done.
I have one further question not discussed so far:
absorb
uses the coercion framework before calling_absorb_
with guaranteed equal parents.can_absorb
does not. Is there a reason for that? Does only the growth group play a role here, so that different parents do not really matter?
Well, we currently only have three cases when t1.can_absorb(t2)
is called:
t1
is a term from an abstract base class. These cannot absorb anything, soFalse
is returned. No need to ask the coercion framework.t1
is anO
term. In this case,can_absorb
testst1 <= t2
, which in turn asks the coercion framework for help.t1
is an exact term. Here,t2
can be absorbed if and only ift2
is an exact term as well, and the growth needs to coincide as well. I don't think that the coercion framework should be involved in this case.
Benjamin
comment:39 Changed 5 years ago by
 Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm
comment:40 in reply to: ↑ 38 ; followup: ↓ 41 Changed 5 years ago by
 Commit changed from 67a73cabf434ab2d6642db0b9e5e8eeec9767feb to b22a24b09af01226e100bdb69847495e806e1c53
 Status changed from needs_review to needs_info
Replying to behackl:
In fact, we only need the comparison of the underlying growth. I've deleted
TermWithCoefficient._le_
and rewritten the documentation ofGenericTerm.__le__
andGenericTerm._le_
in order to reflect that.As this isas you already saida rather technical class, I think that it can be justified if
<=
only compares growth. However, if we follow this approach, thenx <= 2*x
and2*x <= x
would both yieldTrue
, butx == 2*x
would be false (because as far as I can remember, we need==
to actually check if the coefficients are the same too, somewhere in theAsymptoticRing
). Any thoughts?
First, I do not know what the next tickets want to see, whether <=
has to be antisymmetric or not.
On the other hand, elements of equal growth will always absorb each other and not be elements of the same asymptotic expansion, anyway?
Second, where is the implementation of equality of growth terms?
If in doubt, I would say that x
and 2x
are incomparable in order to save antisymmetry.
Apart from that, I reviewed your changes, added a few reviewer commits (please crossreview).
New commits:
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

comment:41 in reply to: ↑ 40 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/asymptoticTerm to u/behackl/asy/asymptoticTerm
 Commit changed from b22a24b09af01226e100bdb69847495e806e1c53 to abc6a16771d308e14b167110de8980de680ca53b
 Status changed from needs_info to needs_review
Replying to cheuberg:
Replying to behackl:
In fact, we only need the comparison of the underlying growth. I've deleted
TermWithCoefficient._le_
and rewritten the documentation ofGenericTerm.__le__
andGenericTerm._le_
in order to reflect that.As this isas you already saida rather technical class, I think that it can be justified if
<=
only compares growth. However, if we follow this approach, thenx <= 2*x
and2*x <= x
would both yieldTrue
, butx == 2*x
would be false (because as far as I can remember, we need==
to actually check if the coefficients are the same too, somewhere in theAsymptoticRing
). Any thoughts?First, I do not know what the next tickets want to see, whether
<=
has to be antisymmetric or not. On the other hand, elements of equal growth will always absorb each other and not be elements of the same asymptotic expansion, anyway?
I agree, once again. We should preserve that <=
is antisymmetric, and I propose the following:
 For terms without coefficient, we simply compare the growth with
<=
like we do now.  For terms with coefficient, we check if
term1.growth < term.growth
(still like above), and in case we haveterm1.growth == term2.growth
, we returnTrue
if and only if the terms are the same, i.e. if the coefficient coincides. Otherwise, the terms are incomparable.
I've added this, as well as a short note in the module description how terms are compared.
Second, where is the implementation of equality of growth terms?
If in doubt, I would say that
x
and2x
are incomparable in order to save antisymmetry.
Ah! These did not exist on this ticket  I have added them as well, as they logically belong here.
Apart from that, I reviewed your changes, added a few reviewer commits (please crossreview).
I reviewed your changes, and added the points from above (please crossreview again :)
).
Benjamin
Last 10 new commits:
ad0754c  shifted documentation of absorption towards module description

0eaa472  remark regarding keyword check in GenericTerm.absorb

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

comment:42 Changed 5 years ago by
 Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm
comment:43 Changed 5 years ago by
 Commit changed from abc6a16771d308e14b167110de8980de680ca53b to aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c
 Status changed from needs_review to positive_review
comment:44 Changed 5 years ago by
 Branch changed from u/cheuberg/asy/asymptoticTerm to aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
added the copyright header.
fixed author date in copyright header.
fixed coercion error: coercion happens now only when bases coerce into
initial commit: structure fixed, coercion implemented
fixed some minor documentation issues
implemented absorption for OTerm and ExactTerm, and multiplication for LTermGeneric
coefficient 0 is not allowed
_le_ for TermWithCoefficient
can_absorb always returns a boolean
improved documentation