AsymptoticTerm

[behackl]

Asymptotic terms are expressions like O(n²), 7 * n * 2ⁿ, or 42 * n * log(n). They build upon the asymptotic growth elements from #17600, which are elements like n², n*2ⁿ 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³, 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 meta-ticket #17601 for the planned structure.

Depends on #17600
Depends on #18930
Depends on #19237

CC: @dkrenn @cheuberg @nathanncohen @videlec @sagetrac-tmonteil

Component: asymptotic expansions

Keywords: gsoc15

Author: Benjamin Hackl

Branch/Commit: aea0ae8

Reviewer: Daniel Krenn, Clemens Heuberger

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

[behackl]

Commit: cd4c640

[behackl]

Branch: u/behackl/asy/asymptoticTerm

[sagetrac-git]

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

016db34	added the copyright header.
feadcae	fixed author date in copyright header.
92b1720	fixed coercion error: coercion happens now only when bases coerce into
a4e5018	initial commit: structure fixed, coercion implemented
2a92578	fixed some minor documentation issues
49db4b8	implemented absorption for OTerm and ExactTerm, and multiplication for LTermGeneric
7d96970	coefficient 0 is not allowed
eacb0e9	_le_ for TermWithCoefficient
0d8b99a	can_absorb always returns a boolean
7ef7cb4	improved documentation

[sagetrac-git]

Changed commit from cd4c640 to 7ef7cb4

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 7ef7cb4 to eb4c8af

[sagetrac-git]

Changed commit from eb4c8af to 042e9c1

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 042e9c1 to a589d8d

[sagetrac-git]

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

[sagetrac-git]

Changed commit from a589d8d to 0c8099e

[sagetrac-git]

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

[sagetrac-git]

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

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

[sagetrac-git]

Changed commit from 0c8099e to 0d7ce6b

[dkrenn]

Changed branch from u/behackl/asy/asymptoticTerm to u/dkrenn/asy/asymptoticTerm

[dkrenn]

Changed commit from 0d7ce6b to 373dda9

[dkrenn]

Reviewer: Daniel Krenn

[dkrenn]

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

[dkrenn]

Changed author from Benjamin Hackl to Benjamin Hackl, Daniel Krenn

[behackl]

Changed branch from u/dkrenn/asy/asymptoticTerm to u/behackl/asy/asymptoticTerm

[behackl]

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

[behackl]

Dependencies: #17600

[behackl]

Changed keywords from none to gsoc15

[behackl]

Changed commit from 373dda9 to 0d7ce6b

[sagetrac-git]

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

[cheuberg]

comment:36

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?

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 0bac3bb to 67a73ca

[behackl]

comment:38

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

[cheuberg]

Changed branch from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm

[cheuberg]

comment:40

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:

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

[cheuberg]

Changed commit from 67a73ca to b22a24b

[behackl]

comment:41

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:

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

[behackl]

Changed commit from b22a24b to abc6a16

[behackl]

Changed branch from u/cheuberg/asy/asymptoticTerm to u/behackl/asy/asymptoticTerm

[cheuberg]

Changed branch from u/behackl/asy/asymptoticTerm to u/cheuberg/asy/asymptoticTerm

[cheuberg]

Changed commit from abc6a16 to aea0ae8

[cheuberg]

comment:43

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:

aea0ae8

Trac #17715: Minor language adjustments

[vbraun]

Changed branch from u/cheuberg/asy/asymptoticTerm to aea0ae8