Opened 5 years ago

Closed 4 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) Commit: aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c
Dependencies: #17600, #18930, #19237 Stopgaps:

Description (last modified by behackl)

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 5 years ago by ncohen

  • Cc ncohen vdelecroix tmonteil added

comment:2 Changed 5 years ago by behackl

  • Branch set to u/behackl/asy/asymptoticTerm
  • Commit set to cd4c640179f27a8516a119e11415f8116b452635

comment:3 Changed 4 years ago by git

  • Commit changed from cd4c640179f27a8516a119e11415f8116b452635 to 7ef7cb402e0d99c6e59346d7412b25993d41d745

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

016db34added the copyright header.
feadcaefixed author date in copyright header.
92b1720fixed coercion error: coercion happens now only when bases coerce into
a4e5018initial commit: structure fixed, coercion implemented
2a92578fixed some minor documentation issues
49db4b8implemented absorption for OTerm and ExactTerm, and multiplication for LTermGeneric
7d96970coefficient 0 is not allowed
eacb0e9_le_ for TermWithCoefficient
0d8b99acan_absorb always returns a boolean
7ef7cb4improved documentation

comment:4 Changed 4 years ago by git

  • Commit changed from 7ef7cb402e0d99c6e59346d7412b25993d41d745 to eb4c8af525e41e334dc8241ec9daf2ace3e3c1f6

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

0a603f3import have_same_parent from sage.structure.element instead of .sage_object
1eef695merge fix of import deprecation (have_same_parent) for asy/growthElement into asy/asymptoticTerm
eb4c8afimport have_same_parent from sage.structure.element

comment:5 Changed 4 years ago by git

  • Commit changed from eb4c8af525e41e334dc8241ec9daf2ace3e3c1f6 to 042e9c1b85a2dd1b0a5805699697baa0cf369744

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

4e80522repr: checking for integers with isinstance introduces problems with
4207fcea base is valid, if it inherits from Parent
e48afc9minor documentation improvements
73017abconversion from multivariate polynomial rings and multivariate power
167dec3merge the clean and cross-reviewed version of asy/growthGroup into asy/asymptoticTerm
ae273d8fixed doctests due to changes to asy/growthGroup
ea07028growth group has to be specified; choice no longer defaults to GenericGrowthGroup.
8a206a3replaced most double quotes by single quotes (consistency with asy/growthGroup)
1ee90eaimproved and simplified documentation (consistency with asy/growthGroup)
042e9c1coefficients have to be specified explicitly; no default values.

comment:6 Changed 4 years ago by git

  • Commit changed from 042e9c1b85a2dd1b0a5805699697baa0cf369744 to a589d8d4e3dbfbc25e453f7f33529ca599df3ef8

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

2dfe905added a factory for asymptotic terms
234945cadapted import statements (consistency with asy/growthGroup)
5f513a7module description added
cc6a431_mul_ calls the parent to construct a new element
414a2c6simplified documentation of _repr_
95f98c8various improvements of the documentation.
ce7a2a3reworked the element constructor and added doctests for growth group conversion
a589d8dgeneration of L terms using the factory documented

comment:7 Changed 4 years ago by git

  • Commit changed from a589d8d4e3dbfbc25e453f7f33529ca599df3ef8 to 0c8099e644102fcae9407b6f7200f80ffd07aa0e

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

a2840b3fixed can_absorb for generic L terms
a4d5c5f_coerce_map_from_ --> has_coerce_map_from in doctests
ee8272cfixed conversion from multivariate power series rings; replaced PolynomialRing and PowerSeriesRing in doc by bracket-notation
fde1604Merge branch 'asy/growthGroup' into asy/asymptoticTerm
66e4d4ecan_absorb now calls helper functions _can_absorb_
c7ef699implemented the conversion of suitable monomials with coefficient to terms with coefficient
a5b0ba0postponed the implementation of L terms after having a minimal working example
0c8099eimplemented a flag for can_absorb

comment:8 Changed 4 years ago by git

  • Commit changed from 0c8099e644102fcae9407b6f7200f80ffd07aa0e to 0d7ce6b628ef3ae399cf00d874ccbfc4de97734e

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

3cbeac3helper methods for asymptotic expressions added
676c3d8fixed a bug with conversion of the variable without powers
0d7ce6badapted representation of exact terms to the representation of

comment:9 Changed 4 years ago by dkrenn

  • Branch changed from u/behackl/asy/asymptoticTerm to u/dkrenn/asy/asymptoticTerm

comment:10 Changed 4 years ago by dkrenn

  • Authors changed from Benjamin Hackl to Benjamin Hackl, Daniel Krenn
  • Commit changed from 0d7ce6b628ef3ae399cf00d874ccbfc4de97734e to 373dda9bc08ca928dda27998035d0860e0cb556c
  • Reviewers set to Daniel Krenn

Last 10 new commits:

28dc2a8moved _can_absorb_ in code directly below can_absorb
3546ed4docstring enhancements in GenericTerm
4f53a8bimprove docstrings of term monoid
5128036remove default None from constructor of generic term monoid
16c407esimplify code of _coerce_map_from_
ae361b5remove else branch and move block to the left (_element_constructor_) to increase readability
f6799c5improve docstrings
f189e1csome minor code rewritings
253556fadd an additional doctest
373dda9fixed broken doctests

comment:11 Changed 4 years ago by behackl

  • 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
ee8272cfixed conversion from multivariate power series rings; replaced PolynomialRing and PowerSeriesRing in doc by bracket-notation
fde1604Merge branch 'asy/growthGroup' into asy/asymptoticTerm
66e4d4ecan_absorb now calls helper functions _can_absorb_
c7ef699implemented the conversion of suitable monomials with coefficient to terms with coefficient
a5b0ba0postponed the implementation of L terms after having a minimal working example
0c8099eimplemented a flag for can_absorb
3cbeac3helper methods for asymptotic expressions added
676c3d8fixed a bug with conversion of the variable without powers
0d7ce6badapted representation of exact terms to the representation of

comment:12 Changed 4 years ago by git

  • 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
65301c7changed representation string of TermWithCoefficientMonoid and
710f54frefactored comparison for TermWithCoefficient and GenericTerm
5a4b631fixed some typos
d73ce3eadded docstring for create_object
38b8836specified exceptions caught in _element_constructor_
172824aimproved doctests: avoided tuple assignments
aa68142O term(s) et al --> `O`-terms
1712037improved documentation: simplified variable names in doctests
7f2c584links repaired and header modified

comment:13 Changed 4 years ago by behackl

  • Description modified (diff)

comment:14 Changed 4 years ago by git

  • Commit changed from 7f2c5842f61d78663fd3c61e303cfe864fc558a1 to e6101a9b4bacd120d1b5e171563b32076f059c03

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

5538893added @experimental to parents
9a89bcaMerge branch 'asy/growthGroup' into asy/asymptoticTerm
e6101a9added @experimental to the term monoids

comment:15 Changed 4 years ago by git

  • Commit changed from e6101a9b4bacd120d1b5e171563b32076f059c03 to 42b45b8572f652c1b9b8feb6efc5f575b8443aee

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

42b45b8fixed helper function can_absorb

comment:16 Changed 4 years ago by git

  • Commit changed from 42b45b8572f652c1b9b8feb6efc5f575b8443aee to 637d4cb0188f2df312f95eeaf3801779a57b0d40

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

907e82ddocstrings for _repr*_ methods
6c8b543changed default representation to short representation
2903a9ahelper method for short representation implemented
c916514implemented a helper method for the growth group factory
ae0fff3factory for growth groups implemented
9c3a08eMerge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
2010268fixed doctest in can_absorb + improved documentation
a5fd74dintroduction of short notation for growth groups + factory
6e9652bcomparison with mul_vararg
637d4cbheader modified

comment:17 Changed 4 years ago by behackl

  • Dependencies changed from #17600 to #17600, #18930

comment:18 Changed 4 years ago by git

  • Commit changed from 637d4cb0188f2df312f95eeaf3801779a57b0d40 to 371a53afb8ac0c8aa91e5d67c241fcca2826ee2f

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

371a53arepresentation: 1*x --> x; -1*x --> -x etc.

comment:19 Changed 4 years ago by git

  • Commit changed from 371a53afb8ac0c8aa91e5d67c241fcca2826ee2f to 7eecfe2014598d97048fc3fd98e552baa31f38f1

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

655ec12rename to repr_short_to_parent
e60a325rewrite growth group factory
ea8ae66repr-option to suppress words "Growth Group"
b7f5c73rename repr-option-keyword and minor change in output
c0ec9fdminor change in output of repr
f141775typos in module description fixed
62d824fMerge branch 'asy/growthGroup' into asy/growthGroup-factory
116ab14Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
164e39cexperimental warning: refer to #17601
7eecfe2improved representation strings

comment:20 Changed 4 years ago by git

  • Commit changed from 7eecfe2014598d97048fc3fd98e552baa31f38f1 to fcf9581cd4b9fb08a65fb53cb713efa5fc048fcf

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

fcf9581minor simplification for the term factory

comment:21 Changed 4 years ago by git

  • Commit changed from fcf9581cd4b9fb08a65fb53cb713efa5fc048fcf to 461653586dd4f5b03df53c317bb4cbe78d8c08ed

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

164d21ecompare exponents directly instead with is_le_one
baa8f7cimplemented gens_monomial and adapted gen, gens, ngens
b477c62merge branch 'asy/growthGroup' into asy/growthGroup-factory and resolve a minor conflict
c98eaeeMerge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
d92d3ecparsing of log-operands fixed
3749fa1refactored handling of generators
ba16c0fMerge branch 'asy/growthGroup' into asy/growthGroup-factory
4616535Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm

comment:22 Changed 4 years ago by git

  • Commit changed from 461653586dd4f5b03df53c317bb4cbe78d8c08ed to 0b53b76fa63afb0b275e953984a4e99dc84d16ef

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

c6d8584error with the element constructor fixed, doctest added
3564d23Merge branch 'asy/growthGroup' into asy/growthGroup-factory
0b53b76Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm

comment:23 Changed 4 years ago by dkrenn

  • Authors changed from Benjamin Hackl, Daniel Krenn to Benjamin Hackl

comment:24 Changed 4 years ago by behackl

  • Status changed from new to needs_review

comment:25 Changed 4 years ago by dkrenn

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

  • Commit changed from 0b53b76fa63afb0b275e953984a4e99dc84d16ef to 79be7d6f4584f596bbdcad03b419db88b3d6b782

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

e8662cdcollect asymptotic code in one directory
c5f0dacMerge branch 'asy/growthGroup' into asy/growthGroup-factory
7fba1feMerge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
7774ff2fixed doctests
878ef2afixed documentation build
5fd9662Merge branch 'asy/growthGroup' into asy/growthGroup-factory
f20c42efixing doctests
38e73c8Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
ae6a9bbfixed doctests
79be7d6documentation builds again

comment:27 Changed 4 years ago by git

  • Commit changed from 79be7d6f4584f596bbdcad03b419db88b3d6b782 to 7b8c1a097e0ce5c23e7ad9cfd006138557b44a49

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

7b8c1a0fixed a conversion issue for terms with coefficient

comment:28 Changed 4 years ago by dkrenn

  • Branch changed from u/behackl/asy/asymptoticTerm to u/dkrenn/asy/asymptoticTerm

comment:29 Changed 4 years ago by dkrenn

  • Commit changed from 7b8c1a097e0ce5c23e7ad9cfd006138557b44a49 to 6da5ade0a4f8ece3054b2a2a6fdd095ffec71e76

Merge 6.9.beta5


New commits:

1c81c12language oddities fixed
032d8b8Merge branch 'asy/growthGroup' into asy/growthGroup-factory
3a05be7Merge tag '6.9.beta5' into t/17600/asy/growthGroup
58f931dadd asymptotic_expansions index
9d6f2daMerge branch 't/17600/asy/growthGroup' into t/18930/asy/growthGroup-factory
6da5adeMerge branch 't/18930/asy/growthGroup-factory' into t/17715/asy/asymptoticTerm

comment:30 Changed 4 years ago by dkrenn

  • Component changed from symbolics to asymptotic expansions

comment:31 Changed 4 years ago by cheuberg

  • 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 4 years ago by behackl

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

3f88a9aduplicate doctest removed
9489badelement_constructor: input clarification; doctests marked as indirect
053ee33type(...) == ... --> isinstance(...)
7b49489clarification gens vs. gens_monomial
2bf6868prevent strange NotImplementedError from PowerSeriesRing
4f99031Merge branch 'asy/growthGroup' into asy/growthGroup-factory
7c3f6b8Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
6f251fdfixed typo
dfb8d41fixed formatting issue
cc55be7fixed indentation of one block

comment:33 Changed 4 years ago by cheuberg

  • Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm

comment:34 Changed 4 years ago by cheuberg

  • 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 conditions
  • GenericTerm.can_absorb and GenericTerm._can_absorb_: Why two methods?
  • GenericTerm.absorb: what happens if check is not set? Why would one want to call that?
  • GenericTerm.absorb, last 3 lines of code: isn't it quite confusing to override self and other in the lambda expression?
  • GenericTerm._absorb_: the method is never called in the doctests, in particular, the NotImplementedError does not show up.
  • GenericTermMonoid.__init__: see #17600, comment 40: handling of tuples as parameter category, __classcall__ for parameter category; same question for derived classes?
  • GenericTermMonoid.__init__: documentation says that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.
  • GenericTermMonoid._element_constructor_: why example T_QQ.coerce(term1) instead of T_QQ(term1)?
  • GenericTermMonoid._element_constructor_: why type(data) == self.element_class and not isinstance(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 an OTermMonoid or an ExactTermMonoid. However, the code does not enforce the former.
  • TermWithCoefficient._le_: The comparison of coefficients is not documented. Apart from that, do we really want that x <= 2*I*x when the coefficient ring is complex?
  • TermWithCoefficientMonoid._init_: check error condition
  • TermWithCoefficientMonoid.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 a TermWithCoefficientMonoid.
  • ExactTerm._repr_: I do not like the check self.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:

88b9294Trac #19237: Fix ReSt errors in reference/rings
a7361b2Trac #17715: Merge #19237 to ease review
148b0b8Trac #17715: minor documentation issues
9f8a248Trac #17715: remove duplicate line in doctest
d870c90Trac #17715: Documentation: language
d4c2b0aTrac #17715: Fix/insert links
a2dfd22Trac #17715: ReSt error
f6882feTrac #17715: additional doctest for explanation
347f080Trac #17715: emphasize that 'O' is capital letter and not digit

comment:35 follow-up: Changed 4 years ago by behackl

  • 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 and GenericTerm._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 if check 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 override self and other in the lambda expression?

Yes, it really is. Changed to left and right.

  • GenericTerm._absorb_: the method is never called in the doctests, in particular, the NotImplementedError does not show up.

Added a doctest that directly calls GenericTerm._absorb_.

  • GenericTermMonoid.__init__: see #17600, comment 40: handling of tuples as parameter category, __classcall__ for parameter category; 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 that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.

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 example T_QQ.coerce(term1) instead of T_QQ(term1)?

Changed.

  • GenericTermMonoid._element_constructor_: why type(data) == self.element_class and not isinstance(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 an OTermMonoid or an ExactTermMonoid. 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 that x <= 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 a TermWithCoefficientMonoid.

Fixed.

  • ExactTerm._repr_: I do not like the check self.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:

3b0a678improve absorb, can_absorb
5aa190etest for checking parent of growth in __init__
ea89a53lambda: self, other --> left, right
d6de96ctest _absorb_
cf9f007use call instead of .coerce(..)
6bfb92ftype(..) == ... --> isinstance(...)
483f6b9fix comparison of terms with complex coefficients
1920865fix docstring of _coerce_map_from_ from term with coefficient monoid
1217348improve handling of base_ring for term with coefficient monoid
0bac3bbadd more tests for TermMonoidFactory

comment:36 in reply to: ↑ 35 Changed 4 years ago by cheuberg

  • Status changed from needs_review to needs_info

Replying to behackl:

  • GenericTerm.can_absorb and GenericTerm._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 if check 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.

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 that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.

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.

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 example T_QQ.coerce(term1) instead of T_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 that x <= 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 4 years ago by git

  • Commit changed from 0bac3bb892aab1e2ae42a20b9f50458fa36acd13 to 67a73cabf434ab2d6642db0b9e5e8eeec9767feb

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

0da8a7aimproved module documentation
3964eae_can_absorb_ --> can_absorb
820e310base_ring is now a function, not a property
4afce6cremoved TermWithCoefficient._le_, improved documentation of __le__ and _le_
6d23773clarification of growth_group in GenericTermMonoid.__init__
ad0754cshifted documentation of absorption towards module description
0eaa472remark regarding keyword check in GenericTerm.absorb
67a73caimproved some doctests

comment:38 follow-up: Changed 4 years ago by behackl

  • 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 if check 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.

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

Done.

  • GenericTermMonoid.__init__: documentation says that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.

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.

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 example T_QQ.coerce(term1) instead of T_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 that x <= 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?

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

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, so False is returned. No need to ask the coercion framework.
  • t1 is an O-term. In this case, can_absorb tests t1 <= t2, which in turn asks the coercion framework for help.
  • t1 is an exact term. Here, t2 can be absorbed if and only if t2 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

Last edited 4 years ago by behackl (previous) (diff)

comment:39 Changed 4 years ago by cheuberg

  • Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm

comment:40 in reply to: ↑ 38 ; follow-up: Changed 4 years ago by cheuberg

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

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:

ce7e2a3Trac #17715: avoid the use of repr in doctest
7b29b28Trac #17715: do not include "the" in internal link texts
b22a24bTrac #17715: Fix ReSt error

comment:41 in reply to: ↑ 40 Changed 4 years ago by behackl

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

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 have term1.growth == term2.growth, we return True 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 and 2x 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:

ad0754cshifted documentation of absorption towards module description
0eaa472remark regarding keyword check in GenericTerm.absorb
67a73caimproved some doctests
fe906careintroduce _le_ for TermWithCoefficient
5cb54aeequality comparison for terms
14e3e63improve documentation: information on comparison
ce7e2a3Trac #17715: avoid the use of repr in doctest
7b29b28Trac #17715: do not include "the" in internal link texts
b22a24bTrac #17715: Fix ReSt error
abc6a16Merge branch 'u/cheuberg/asy/asymptoticTerm' of git://trac.sagemath.org/sage into asy/asymptoticTerm

comment:42 Changed 4 years ago by cheuberg

  • Branch changed from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm

comment:43 Changed 4 years ago by cheuberg

  • Commit changed from abc6a16771d308e14b167110de8980de680ca53b to aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c
  • Status changed from needs_review to positive_review

I added one more trivial language-related commit. Everything is fine for me now. Doctests pass, documentation builds.

Again, the module will only become useful only once at least #17716 is merged.


New commits:

aea0ae8Trac #17715: Minor language adjustments

comment:44 Changed 4 years ago by vbraun

  • Branch changed from u/cheuberg/asy/asymptoticTerm to aea0ae8c5be57bb171f9c0c2abbbf85c5520a35c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.