Opened 8 years ago
Closed 7 years ago
#17600 closed enhancement (fixed)
AsymptoticGrowthElement
Reported by: | behackl | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.9 |
Component: | asymptotic expansions | Keywords: | asymptotics, gsoc2015 |
Cc: | cheuberg, dkrenn, ncohen, vdelecroix | Merged in: | |
Authors: | Benjamin Hackl, Daniel Krenn | Reviewers: | Daniel Krenn, Clemens Heuberger |
Report Upstream: | N/A | Work issues: | |
Branch: | 2bf6868 (Commits, GitHub, GitLab) | Commit: | 2bf68685c1f2c09a258b592d537f34cd9c77b2d3 |
Dependencies: | Stopgaps: |
Description (last modified by )
Hold one order of magnitude for asymptotic terms and expressions. Such a term could be, e.g. n2 or k/n or n*log(n).
AsymptoticGrowthElements can be compared, multiplied, etc., but have no coefficient. Here, only the order of magnitude shall be managed.
See #17601 for the planned structure.
Change History (44)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
- Cc ncohen added
comment:3 Changed 8 years ago by
- Branch set to u/behackl/asy/growthGroup
comment:4 Changed 8 years ago by
- Commit set to 485502bcb5121cfd54cced29f71944a759db2793
comment:5 Changed 8 years ago by
- Commit changed from 485502bcb5121cfd54cced29f71944a759db2793 to 278c1f740b54c3336e4624367332438a9dd9b1ba
comment:6 follow-up: ↓ 7 Changed 7 years ago by
- Cc vdelecroix added
Hello,
The "planned structure" at #17601 does not motivates any choice. In particular, the branch attached to this ticket makes me sceptical since it implements a completely broken version of a multiplicative group isomorphic to RR
(which is also slower and less usable than the original one).
Why is it a group and not a ring? Why should there be, if any, a dedicated parent to an asymptotic term? Do you really intend to implement a parent for each kind of asymptotic you have in mind?
What I see in the branch is only code that is working for itself which is not very interesting and not very useful. You can not start building a cathedral without any serious roadmap.
Vincent
comment:7 in reply to: ↑ 6 Changed 7 years ago by
Replying to vdelecroix:
Why is it a group and not a ring?
The AsymptoticGrowthGroup
is only planned to handle the multiplicative structure. Instead of the simplest example here, think about asymptotics involving powers of n
and log(n)
for n -> infinity
. Then this group will be isomorphic to a cartesian product of RR
with itself with lexicographic order. In another example, where |h|<= n^(3/4)
and n->infinity
, this group will again be a cartesian product of RR
with itself, but the partial order of the lexicographic order will be refined by the additional rule, but not yet be a linear order because some of these terms cannot be compared.
Handling of coefficients, addition of two terms and absorption of O terms are rather independent of the growth group as outlined here. Thus they are planned to be handeled by the AsymptoticTerm
(#17715).
High level operations such as addition and multiplication of expressions are still more general and will be part of the (yet unimplemented) AsymptoticExpression
(#17716).
Why should there be, if any, a dedicated parent to an asymptotic term?
There is a natural coercion from an AsymptoticGrowthGroup
in n
to the AsymptoticGrowthGroup
in n
and log(n)
, for instance. Thus I think it makes sense to use the coercion framework. This requires to have parents.
What I see in the branch is only code that is working for itself which is not very interesting and not very useful.
Therefore, all these tickets are still in status new
and not needs_review
, because the AsymptoticExpression
is still missing.
You can not start building a cathedral without any serious roadmap.
There is a roadmap and the very brief version is in the meta ticket #17601. The long version are notes made during long oral discussions.
Your comments here and on the meta ticket #17601 make it clear that the abbreviated version is not sufficiently clear. Probably the long version of the road map will also be of interest later on and could live in the documentation of the asymptotic expression.
comment:8 Changed 7 years ago by
- Branch changed from u/behackl/asy/growthGroup to u/behackl/asy/growthElement
- Commit changed from 278c1f740b54c3336e4624367332438a9dd9b1ba to 92b17209dac29a02e4f5bc8c566a0f7d32012bfd
Rebased to Sage 6.7.
comment:9 Changed 7 years ago by
- Commit changed from 92b17209dac29a02e4f5bc8c566a0f7d32012bfd to 0a603f3c0b5d7ac2cc604a53610db43f342d7371
Branch pushed to git repo; I updated commit sha1. New commits:
0a603f3 | import have_same_parent from sage.structure.element instead of .sage_object
|
comment:10 Changed 7 years ago by
- Branch changed from u/behackl/asy/growthElement to u/dkrenn/asy/growthGroup
- Commit changed from 0a603f3c0b5d7ac2cc604a53610db43f342d7371 to 9fe8bb6c54649aa2dc0f24f1346290114ad78390
- Keywords gsoc2015 added
- Reviewers set to Daniel Krenn
Last 10 new commits:
8b06fa6 | cleanup in _convert_
|
b746c83 | delete unnecessary populate coercion list
|
7b1bef5 | rewrite class descriptions
|
608d524 | revise gen & Co methods
|
4be8d0d | some new doctests, minor docstring rewritings, small other modifications
|
d08e4d2 | write docstring-header of module
|
160a2d3 | add description of exponent-property
|
c2a5beb | move _div_ to GenericGrowthElement
|
dd1f1de | operations of elements: some small modifications and rewritings
|
9fe8bb6 | docstrings in elements
|
comment:11 Changed 7 years ago by
- Branch changed from u/dkrenn/asy/growthGroup to u/behackl/asy/growthGroup
- Commit changed from 9fe8bb6c54649aa2dc0f24f1346290114ad78390 to 6e69d50d2d61a4bf2ac3a95a92f77390b403a93a
comment:12 Changed 7 years ago by
- Commit changed from 6e69d50d2d61a4bf2ac3a95a92f77390b403a93a to 4e805224e9576f526f68a4658906327c2251590c
Branch pushed to git repo; I updated commit sha1. New commits:
4e80522 | repr: checking for integers with isinstance introduces problems with
|
comment:13 Changed 7 years ago by
- Commit changed from 4e805224e9576f526f68a4658906327c2251590c to 73017ab4d43b822203c676581035c10113b92345
comment:14 Changed 7 years ago by
- Commit changed from 73017ab4d43b822203c676581035c10113b92345 to ee8272c49552f0b42132d37e179c0a4fe01294eb
comment:15 Changed 7 years ago by
- Commit changed from ee8272c49552f0b42132d37e179c0a4fe01294eb to 5538893a685e8b02e36b0b31a56d70cabd438307
Branch pushed to git repo; I updated commit sha1. New commits:
5538893 | added @experimental to parents
|
comment:16 Changed 7 years ago by
- Commit changed from 5538893a685e8b02e36b0b31a56d70cabd438307 to 2903a9a24a7b683e67c11f0944bc46be4c81db2b
comment:17 Changed 7 years ago by
- Branch changed from u/behackl/asy/growthGroup to u/dkrenn/asy/growthGroup
comment:18 Changed 7 years ago by
- Commit changed from 2903a9a24a7b683e67c11f0944bc46be4c81db2b to 30cde4d9d51de53532843744c5ff43d5e438a5a1
Branch pushed to git repo; I updated commit sha1. New commits:
30cde4d | extend docstring of parent_to_string
|
comment:19 Changed 7 years ago by
- Commit changed from 30cde4d9d51de53532843744c5ff43d5e438a5a1 to 45a37b8273e481ef158e098d7b856949c392cdf5
comment:20 Changed 7 years ago by
- Commit changed from 45a37b8273e481ef158e098d7b856949c392cdf5 to c0ec9fda59c661076a99937378dde627bb82180f
comment:21 Changed 7 years ago by
- Branch changed from u/dkrenn/asy/growthGroup to u/behackl/asy/growthGroup
- Commit changed from c0ec9fda59c661076a99937378dde627bb82180f to f141775e9cdb013947907d58d39765877f3ff2e4
Last 10 new commits:
29d7479 | TESTS-->EXAMPLES
|
9ae448c | change repr-string of groups
|
a985397 | change experimental feature trac number to meta ticket 17601
|
30cde4d | extend docstring of parent_to_string
|
ed03ca1 | rename to parent_to_repr_short
|
45a37b8 | rewrite docstring
|
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
|
comment:22 Changed 7 years ago by
- Commit changed from f141775e9cdb013947907d58d39765877f3ff2e4 to 3749fa1d680a9a83b92bc7e08200dc69187b7434
comment:23 Changed 7 years ago by
- Commit changed from 3749fa1d680a9a83b92bc7e08200dc69187b7434 to c6d85848c8690b1b4d1409c0ade4bebbd7954797
Branch pushed to git repo; I updated commit sha1. New commits:
c6d8584 | error with the element constructor fixed, doctest added
|
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
I found a few language oddities.
functions and their behavior as the functions, and their behavior as the It, its functionality or its interface Either its functionality or its interface Helper method, which generates Helper method which generates Growth elements form a group by multiplication and (some of) the Growth elements form a group by multiplication, and (some of) the that this element, as well as ``other`` are of the same type. that this element is of the same type as ``other``. This can anything that is valid to be on the right hand side of ``*`` with an elements of the parent's base This can be anything that is a valid right hand side of ``*`` with elements of the parent's base. (found twice) The result of this exponentiation a :class:`MonomialGrowthElement`. The result of this exponentiation, a :class:`MonomialGrowthElement`. Return if this growth element is equal to ``other``. Return True if this growth element is equal to ``other``. Return if this :class:`GenericGrowthElement` is equal to ``other``. Return True if this :class:`GenericGrowthElement` is equal to ``other``. ...and similar cases... Converts given object to this growth group. Converts a given object to this growth group. Converts given ``data`` to something... Converts ``data`` to something... class and should be overridden in inherited class. class, and should be overridden in inherited classes. Takes this growth element to the given ``power``. Raises this growth element to the given ``power``.
comment:27 follow-up: ↓ 28 Changed 7 years ago by
Hi Ralf! Thanks for your remarks; I'm currently fixing these oddities and will push the changes soon. One question: instead of
Return ``True`` if ...
what do you think about:
Return whether ...
Just because we'd like to avoid directly referring to True
.
comment:28 in reply to: ↑ 27 ; follow-up: ↓ 29 Changed 7 years ago by
Replying to behackl:
Hi Ralf! Thanks for your remarks; I'm currently fixing these oddities and will push the changes soon. One question: instead of
Return ``True`` if ...what do you think about:
Return whether ...
Well if is a synonym for whether so nothing changed.
Just because we'd like to avoid directly referring to
True
.
I have no idea why you would want that. Can you please clarify?
comment:29 in reply to: ↑ 28 ; follow-up: ↓ 30 Changed 7 years ago by
Replying to rws:
Return ``True`` if ...what do you think about:
Return whether ...Well if is a synonym for whether so nothing changed.
Just because we'd like to avoid directly referring to
True
.I have no idea why you would want that. Can you please clarify?
The one-liner description should be short; additionally we have an output block saying that the method returns a boolean. Since there also an ongoing discussion in #19041 about such things, I would leave it for now as it is...
Is there a grammatical reason that "Return if..." should be avoided?
comment:30 in reply to: ↑ 29 Changed 7 years ago by
Replying to dkrenn:
Is there a grammatical reason that "Return if..." should be avoided?
Not at all. I accept your explanation.
comment:31 Changed 7 years ago by
- Commit changed from c6d85848c8690b1b4d1409c0ade4bebbd7954797 to 1c81c124efdbe3b378273dbf8c33088e39561b52
comment:32 Changed 7 years ago by
- Branch changed from u/behackl/asy/growthGroup to u/dkrenn/asy/growthGroup
comment:33 Changed 7 years ago by
- Commit changed from 1c81c124efdbe3b378273dbf8c33088e39561b52 to 58f931d03aa7a98cf713be8002d3c438fa8a9576
comment:34 Changed 7 years ago by
- Component changed from symbolics to asymptotic expansions
comment:35 Changed 7 years ago by
- Description modified (diff)
- Milestone changed from sage-6.5 to sage-6.9
comment:36 Changed 7 years ago by
- Branch changed from u/dkrenn/asy/growthGroup to u/cheuberg/asy/growthGroup
comment:37 Changed 7 years ago by
- Commit changed from 58f931d03aa7a98cf713be8002d3c438fa8a9576 to ac5541719eb6ec9605b7e221ffc64d8fc83781e1
comment:38 Changed 7 years ago by
I started reviewing this ticket and added three reviewer commits, one of which is not shown in trac.
Comments so far:
- I think that the following behaviour does not conform to the use of the parameter
category
inParent
("If category is a list or tuple, a JoinCategory is created out of them."):sage: import sage.rings.asymptotic.growth_group as agg sage: agg.GenericGrowthGroup(ZZ, category=(Posets(), Groups())) Traceback (most recent call last): ... ValueError: (Category of posets, Category of groups) is not a subcategory of Join of Category of groups and Category of posets
Compare this withsage: Parent(category=(Posets(), Groups())).category() Join of Category of groups and Category of posets
GenericGrowthElement
- class documentation: "abstract implementation" sounds contradictory.GenericGrowthElement.__init__
: first and second tests seem to do the same thing.
comment:39 Changed 7 years ago by
- Commit changed from ac5541719eb6ec9605b7e221ffc64d8fc83781e1 to 1ab1334c30e2f2c71c222d789f1e3b4430a17696
comment:40 Changed 7 years ago by
- Status changed from needs_review to needs_work
Here is the remainder of my comments.
GenericGrowthGroup._element_constructor_
: make clear that eitherdata
orraw_element
has to be given; in the latter case,data
has to be 0.GenericGrowthGroup._element_constructor_
: shouldn't the tests be marked as indirect doctests?GenericGrowthGroup._element_constructor_
: is there a particular reason for usingtype(data) == self.element_class
in the second line andisinstance(data, self.element_class)
in the fourth line of the code?GenericGrowthGroup.gens_monomial
: it is not clear what the difference betweengens
andgens_monomial
should be.MonomialGrowthGroup.__classcall__
: The category parameter is not checked, but I can live with that:sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup sage: G1 = MonomialGrowthGroup(ZZ, 'x') sage: G2 = MonomialGrowthGroup(ZZ, 'x', category=Posets() & Groups()) sage: G1 is G2 False sage: G1.category() == G2.category() True
MonomialGrowthGroup.__init__
: Please include doctests for the twoValueErrors
MonomialGrowthGroup._convert_
: I think that the error message on variable in a multivariate power series is not instructive in the following example, I'd prefer to see "Cannot convert 2" as inG(2)
below.sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup sage: G = MonomialGrowthGroup(ZZ, 'x') sage: R.<x, y> = PowerSeriesRing(ZZ, ['x', 'y']) sage: R(2).variables() () sage: G(R(2)) Traceback (most recent call last): ... NotImplementedError: variable not defined for multivariate power series; use 'variables' instead. sage: G(2) Traceback (most recent call last): ... ValueError: Cannot convert 2.
MonomialGrowthGroup.gens_monomial
: Is this method needed? See the example:sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup sage: MonomialGrowthGroup(ZZ, 'log(x)').gens_monomial() () sage: MonomialGrowthGroup(ZZ, 'exp(x)').gens_monomial() (exp(x),)
MonomialGrowthGroup.gens
: cf.gens_monomial
: I'd move "even if the growth group is logarithmic" fromgens
togens_monomial
as "except if the growth group is logarithmic"parent_to_repr_short
: Rewrite INPUT section to standard format
comment:41 Changed 7 years ago by
- Branch changed from u/cheuberg/asy/growthGroup to u/behackl/asy/growthGroup
- Commit changed from 1ab1334c30e2f2c71c222d789f1e3b4430a17696 to 2bf68685c1f2c09a258b592d537f34cd9c77b2d3
- Reviewers changed from Daniel Krenn to Daniel Krenn, Clemens Heuberger
Last 10 new commits:
f827b2c | Trac #17600: one-sentence descriptions: command instead of description
|
c4dca20 | Trac #17600: Punctuation
|
1ab1334 | Trac #17600: fix incorrect link
|
1c7a521 | corrected INPUT-section of parent_to_repr_short
|
6dee8b7 | abstract implementation --> basic implementation
|
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
|
comment:42 Changed 7 years ago by
- Status changed from needs_work to needs_review
Replying to cheuberg:
- I think that the following behaviour does not conform to the use of the parameter
category
inParent
("If category is a list or tuple, a JoinCategory is created out of them."):sage: import sage.rings.asymptotic.growth_group as agg sage: agg.GenericGrowthGroup(ZZ, category=(Posets(), Groups())) Traceback (most recent call last): ... ValueError: (Category of posets, Category of groups) is not a subcategory of Join of Category of groups and Category of posets
This is because our code checks, whether at least one argument in the tuple is a subcategory of Join of Category of groups and Category of posets
. Of course, this could be relaxed such that we check if there is at least one argument that is a subcategory of Category of groups
, and at least one that is a subcategory of Category of posets
.
However, we already took care of that in the cleanup ticket #19083. Thus, I'd leave this as it is here.
GenericGrowthElement
- class documentation: "abstract implementation" sounds contradictory.
Rephrased to "basic implementation".
GenericGrowthElement.__init__
: first and second tests seem to do the same thing.
Duplicate removed.
GenericGrowthGroup._element_constructor_
: make clear that eitherdata
orraw_element
has to be given; in the latter case,data
has to be 0.
Done.
GenericGrowthGroup._element_constructor_
: shouldn't the tests be marked as indirect doctests?
Done.
GenericGrowthGroup._element_constructor_
: is there a particular reason for usingtype(data) == self.element_class
in the second line andisinstance(data, self.element_class)
in the fourth line of the code?
Not as far as I can remember. I have rewritten this particular part of the element constructor.
GenericGrowthGroup.gens_monomial
: it is not clear what the difference betweengens
andgens_monomial
should be.
I've tried to clarify by extending the documentation.
MonomialGrowthGroup.__classcall__
: The category parameter is not checked, but I can live with that:
Fixed on the cleanup-ticket.
MonomialGrowthGroup.__init__
: Please include doctests for the twoValueErrors
We put the code handling variables in a separate class on the cleanup ticket. Thus, I think that this is not really necessary.
MonomialGrowthGroup._convert_
: I think that the error message on variable in a multivariate power series is not instructive in the following example, I'd prefer to see "Cannot convert 2" as inG(2)
below.sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup sage: G = MonomialGrowthGroup(ZZ, 'x') sage: R.<x, y> = PowerSeriesRing(ZZ, ['x', 'y']) sage: R(2).variables() () sage: G(R(2)) Traceback (most recent call last): ... NotImplementedError: variable not defined for multivariate power series; use 'variables' instead. sage: G(2) Traceback (most recent call last): ... ValueError: Cannot convert 2.
Fixed.
MonomialGrowthGroup.gens_monomial
: Is this method needed? See the example:sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup sage: MonomialGrowthGroup(ZZ, 'log(x)').gens_monomial() () sage: MonomialGrowthGroup(ZZ, 'exp(x)').gens_monomial() (exp(x),)
I've added an additional note to explain what this method should exactly do. Note that while it can only recognize log(...)
on this ticket, we have extended the functionality of it (to actually do what it should) on ticket #18587.
MonomialGrowthGroup.gens
: cf.gens_monomial
: I'd move "even if the growth group is logarithmic" fromgens
togens_monomial
as "except if the growth group is logarithmic"
Removed the half-sentence. The additional note for gens_monomial
should make the difference clear.
parent_to_repr_short
: Rewrite INPUT section to standard format
Done.
Thank you for your review---this is now ready for a short cross-review.
comment:43 Changed 7 years ago by
- Status changed from needs_review to positive_review
Reviewed your changes.
Doctests pass, documentation builds, code is ok.
Obviously, inclusion of this ticket alone into SageMath is not useful. However, once everything mentioned in the meta ticket #17601 is merged, this should be very useful. It will take some more time to finish and then review all those tickets.
Despite all that, a first step has to be made, so I set this to positive_review.
comment:44 Changed 7 years ago by
- Branch changed from u/behackl/asy/growthGroup to 2bf68685c1f2c09a258b592d537f34cd9c77b2d3
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
added the copyright header.