Opened 8 years ago
Closed 7 years ago
#17715 closed enhancement (fixed)
AsymptoticTerm
Reported by: | behackl | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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, GitHub, GitLab) | Commit: | aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c |
Dependencies: | #17600, #18930, #19237 | Stopgaps: |
Description (last modified by )
Asymptotic terms are expressions like O(n2), 7 * n * 2n, or 42 * n * log(n). They build upon the asymptotic growth elements from #17600, which are elements like n2, n*2n 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 * x3, 7 * x-2/5, or 42 * x1/3 * log(x).
Asymptotic terms may be multiplied and absorbed; addition will be handled by AsymptoticExpression.
See meta-ticket #17601 for the planned structure.
Change History (44)
comment:1 Changed 8 years ago by
- Cc ncohen vdelecroix tmonteil added
comment:2 Changed 8 years ago by
- Branch set to u/behackl/asy/asymptoticTerm
- Commit set to cd4c640179f27a8516a119e11415f8116b452635
comment:3 Changed 7 years ago by
- Commit changed from cd4c640179f27a8516a119e11415f8116b452635 to 7ef7cb402e0d99c6e59346d7412b25993d41d745
comment:4 Changed 7 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 7 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 cross-reviewed 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 7 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 7 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 bracket-notation
|
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 7 years ago by
- Commit changed from 0c8099e644102fcae9407b6f7200f80ffd07aa0e to 0d7ce6b628ef3ae399cf00d874ccbfc4de97734e
comment:9 Changed 7 years ago by
- Branch changed from u/behackl/asy/asymptoticTerm to u/dkrenn/asy/asymptoticTerm
comment:10 Changed 7 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 7 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 bracket-notation
|
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 7 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 7 years ago by
- Description modified (diff)
comment:14 Changed 7 years ago by
- Commit changed from 7f2c5842f61d78663fd3c61e303cfe864fc558a1 to e6101a9b4bacd120d1b5e171563b32076f059c03
comment:15 Changed 7 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 7 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/growthGroup-factory' 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 7 years ago by
- Dependencies changed from #17600 to #17600, #18930
comment:18 Changed 7 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 7 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 | repr-option to suppress words "Growth Group"
|
b7f5c73 | rename repr-option-keyword 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/growthGroup-factory
|
116ab14 | Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
|
164e39c | experimental warning: refer to #17601
|
7eecfe2 | improved representation strings
|
comment:20 Changed 7 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 7 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/growthGroup-factory and resolve a minor conflict
|
c98eaee | Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
|
d92d3ec | parsing of log-operands fixed
|
3749fa1 | refactored handling of generators
|
ba16c0f | Merge branch 'asy/growthGroup' into asy/growthGroup-factory
|
4616535 | Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
|
comment:22 Changed 7 years ago by
- Commit changed from 461653586dd4f5b03df53c317bb4cbe78d8c08ed to 0b53b76fa63afb0b275e953984a4e99dc84d16ef
comment:23 Changed 7 years ago by
comment:24 Changed 7 years ago by
- Status changed from new to needs_review
comment:25 Changed 7 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 7 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/growthGroup-factory
|
7fba1fe | Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
|
7774ff2 | fixed doctests
|
878ef2a | fixed documentation build
|
5fd9662 | Merge branch 'asy/growthGroup' into asy/growthGroup-factory
|
f20c42e | fixing doctests
|
38e73c8 | Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
|
ae6a9bb | fixed doctests
|
79be7d6 | documentation builds again
|
comment:27 Changed 7 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 7 years ago by
- Branch changed from u/behackl/asy/asymptoticTerm to u/dkrenn/asy/asymptoticTerm
comment:29 Changed 7 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/growthGroup-factory
|
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/growthGroup-factory
|
6da5ade | Merge branch 't/18930/asy/growthGroup-factory' into t/17715/asy/asymptoticTerm
|
comment:30 Changed 7 years ago by
- Component changed from symbolics to asymptotic expansions
comment:31 Changed 7 years ago by
- Milestone changed from sage-6.5 to sage-6.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 start-string without end-string.
comment:32 Changed 7 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 docbuild-issue, made some small documentation-related 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/growthGroup-factory
|
7c3f6b8 | Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
|
6f251fd | fixed typo
|
dfb8d41 | fixed formatting issue
|
cc55be7 | fixed indentation of one block
|
comment:33 Changed 7 years ago by
- Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm
comment:34 Changed 7 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
: One-Sentence-Description should describe what this function does. What happens if the elements are not comparable (documentation; probably only possible in a follow-up ticket)?can_absorb
: One-Sentence-Description, 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 follow-up: ↓ 36 Changed 7 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
: One-Sentence-Description should describe what this function does. What happens if the elements are not comparable (documentation; probably only possible in a follow-up 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
: One-Sentence-Description, 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 (well-documented) 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 correctly---and 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 is--however--still on our TODO-list.
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 does---however, 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 part---but 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 pushout-stuff (... 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 cross-review 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 7 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 (well-documented) 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 correctly---and 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 is--however--still on our TODO-list.
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 part---but 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 pushout-stuff (... 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 cross-review 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 7 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 follow-up: ↓ 40 Changed 7 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 correctly---and 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 is--however--still on our TODO-list.
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 section---in 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 part---but 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 is--as you already said--a 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 pushout-stuff (... 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 cross-review 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 7 years ago by
- Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm
comment:40 in reply to: ↑ 38 ; follow-up: ↓ 41 Changed 7 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 is--as you already said--a 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 cross-review).
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 7 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 is--as you already said--a 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 cross-review).
I reviewed your changes, and added the points from above (please cross-review 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 7 years ago by
- Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm
comment:43 Changed 7 years ago by
- Commit changed from abc6a16771d308e14b167110de8980de680ca53b to aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c
- Status changed from needs_review to positive_review
comment:44 Changed 7 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