Opened 5 years ago

Closed 4 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) Commit: 2bf68685c1f2c09a258b592d537f34cd9c77b2d3
Dependencies: Stopgaps:

Description (last modified by cheuberg)

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

  • Description modified (diff)

comment:2 Changed 5 years ago by ncohen

  • Cc ncohen added

comment:3 Changed 5 years ago by behackl

  • Branch set to u/behackl/asy/growthGroup

comment:4 Changed 5 years ago by git

  • Commit set to 485502bcb5121cfd54cced29f71944a759db2793

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

485502badded the copyright header.

comment:5 Changed 5 years ago by git

  • Commit changed from 485502bcb5121cfd54cced29f71944a759db2793 to 278c1f740b54c3336e4624367332438a9dd9b1ba

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

492679efixed author date in copyright header.
278c1f7fixed coercion error: coercion happens now only when bases coerce into

comment:6 follow-up: Changed 5 years ago by vdelecroix

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

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

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

  • Commit changed from 92b17209dac29a02e4f5bc8c566a0f7d32012bfd to 0a603f3c0b5d7ac2cc604a53610db43f342d7371

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

0a603f3import have_same_parent from sage.structure.element instead of .sage_object

comment:10 Changed 4 years ago by dkrenn

  • Authors changed from Benjamin Hackl to Benjamin Hackl, Daniel Krenn
  • 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:

8b06fa6cleanup in _convert_
b746c83delete unnecessary populate coercion list
7b1bef5rewrite class descriptions
608d524revise gen & Co methods
4be8d0dsome new doctests, minor docstring rewritings, small other modifications
d08e4d2write docstring-header of module
160a2d3add description of exponent-property
c2a5bebmove _div_ to GenericGrowthElement
dd1f1deoperations of elements: some small modifications and rewritings
9fe8bb6docstrings in elements

comment:11 Changed 4 years ago by behackl

  • Branch changed from u/dkrenn/asy/growthGroup to u/behackl/asy/growthGroup
  • Commit changed from 9fe8bb6c54649aa2dc0f24f1346290114ad78390 to 6e69d50d2d61a4bf2ac3a95a92f77390b403a93a

comment:12 Changed 4 years ago by git

  • Commit changed from 6e69d50d2d61a4bf2ac3a95a92f77390b403a93a to 4e805224e9576f526f68a4658906327c2251590c

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

4e80522repr: checking for integers with isinstance introduces problems with

comment:13 Changed 4 years ago by git

  • Commit changed from 4e805224e9576f526f68a4658906327c2251590c to 73017ab4d43b822203c676581035c10113b92345

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

4207fcea base is valid, if it inherits from Parent
e48afc9minor documentation improvements
73017abconversion from multivariate polynomial rings and multivariate power

comment:14 Changed 4 years ago by git

  • Commit changed from 73017ab4d43b822203c676581035c10113b92345 to ee8272c49552f0b42132d37e179c0a4fe01294eb

Branch pushed to git repo; I updated commit sha1. 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

comment:15 Changed 4 years ago by git

  • Commit changed from ee8272c49552f0b42132d37e179c0a4fe01294eb to 5538893a685e8b02e36b0b31a56d70cabd438307

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

5538893added @experimental to parents

comment:16 Changed 4 years ago by git

  • Commit changed from 5538893a685e8b02e36b0b31a56d70cabd438307 to 2903a9a24a7b683e67c11f0944bc46be4c81db2b

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

627884cintroduce _repr_short_ for nicer representation
907e82ddocstrings for _repr*_ methods
6c8b543changed default representation to short representation
2903a9ahelper method for short representation implemented

comment:17 Changed 4 years ago by dkrenn

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

comment:18 Changed 4 years ago by git

  • Commit changed from 2903a9a24a7b683e67c11f0944bc46be4c81db2b to 30cde4d9d51de53532843744c5ff43d5e438a5a1

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

30cde4dextend docstring of parent_to_string

comment:19 Changed 4 years ago by git

  • Commit changed from 30cde4d9d51de53532843744c5ff43d5e438a5a1 to 45a37b8273e481ef158e098d7b856949c392cdf5

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

ed03ca1rename to parent_to_repr_short
45a37b8rewrite docstring

comment:20 Changed 4 years ago by git

  • Commit changed from 45a37b8273e481ef158e098d7b856949c392cdf5 to c0ec9fda59c661076a99937378dde627bb82180f

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

ea8ae66repr-option to suppress words "Growth Group"
b7f5c73rename repr-option-keyword and minor change in output
c0ec9fdminor change in output of repr

comment:21 Changed 4 years ago by behackl

  • Branch changed from u/dkrenn/asy/growthGroup to u/behackl/asy/growthGroup
  • Commit changed from c0ec9fda59c661076a99937378dde627bb82180f to f141775e9cdb013947907d58d39765877f3ff2e4

Last 10 new commits:

29d7479TESTS-->EXAMPLES
9ae448cchange repr-string of groups
a985397change experimental feature trac number to meta ticket 17601
30cde4dextend docstring of parent_to_string
ed03ca1rename to parent_to_repr_short
45a37b8rewrite docstring
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

comment:22 Changed 4 years ago by git

  • Commit changed from f141775e9cdb013947907d58d39765877f3ff2e4 to 3749fa1d680a9a83b92bc7e08200dc69187b7434

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
3749fa1refactored handling of generators

comment:23 Changed 4 years ago by git

  • Commit changed from 3749fa1d680a9a83b92bc7e08200dc69187b7434 to c6d85848c8690b1b4d1409c0ade4bebbd7954797

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

c6d8584error with the element constructor fixed, doctest added

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 rws

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: Changed 4 years ago by 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 ...

Just because we'd like to avoid directly referring to True.

comment:28 in reply to: ↑ 27 ; follow-up: Changed 4 years ago by rws

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: Changed 4 years ago by dkrenn

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

Replying to dkrenn:

Is there a grammatical reason that "Return if..." should be avoided?

Not at all. I accept your explanation.

comment:31 Changed 4 years ago by git

  • Commit changed from c6d85848c8690b1b4d1409c0ade4bebbd7954797 to 1c81c124efdbe3b378273dbf8c33088e39561b52

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

db9ee43improved __pow__
2f3d740improved _element_constructor_
e8662cdcollect asymptotic code in one directory
7774ff2fixed doctests
878ef2afixed documentation build
1c81c12language oddities fixed

comment:32 Changed 4 years ago by dkrenn

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

comment:33 Changed 4 years ago by dkrenn

  • Commit changed from 1c81c124efdbe3b378273dbf8c33088e39561b52 to 58f931d03aa7a98cf713be8002d3c438fa8a9576

Merged in 6.9.beta5


New commits:

3a05be7Merge tag '6.9.beta5' into t/17600/asy/growthGroup
58f931dadd asymptotic_expansions index

comment:34 Changed 4 years ago by dkrenn

  • Component changed from symbolics to asymptotic expansions

comment:35 Changed 4 years ago by cheuberg

  • Description modified (diff)
  • Milestone changed from sage-6.5 to sage-6.9

comment:36 Changed 4 years ago by cheuberg

  • Branch changed from u/dkrenn/asy/growthGroup to u/cheuberg/asy/growthGroup

comment:37 Changed 4 years ago by git

  • Commit changed from 58f931d03aa7a98cf713be8002d3c438fa8a9576 to ac5541719eb6ec9605b7e221ffc64d8fc83781e1

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

ef5591fTrac #17600: Minor language adjustments
ac55417Trac #17600: Break long line

comment:38 Changed 4 years ago by cheuberg

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 in Parent ("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 with
    sage: 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 4 years ago by git

  • Commit changed from ac5541719eb6ec9605b7e221ffc64d8fc83781e1 to 1ab1334c30e2f2c71c222d789f1e3b4430a17696

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

83a3905Trac #17600: Fix ReSt error
f827b2cTrac #17600: one-sentence descriptions: command instead of description
c4dca20Trac #17600: Punctuation
1ab1334Trac #17600: fix incorrect link

comment:40 Changed 4 years ago by cheuberg

  • Status changed from needs_review to needs_work

Here is the remainder of my comments.

  • GenericGrowthGroup._element_constructor_: make clear that either data or raw_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 using type(data) == self.element_class in the second line and isinstance(data, self.element_class) in the fourth line of the code?
  • GenericGrowthGroup.gens_monomial: it is not clear what the difference between gens and gens_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 two ValueErrors
  • 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 in G(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" from gens to gens_monomial as "except if the growth group is logarithmic"
  • parent_to_repr_short: Rewrite INPUT section to standard format

comment:41 Changed 4 years ago by behackl

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

f827b2cTrac #17600: one-sentence descriptions: command instead of description
c4dca20Trac #17600: Punctuation
1ab1334Trac #17600: fix incorrect link
1c7a521corrected INPUT-section of parent_to_repr_short
6dee8b7abstract implementation --> basic implementation
3f88a9aduplicate doctest removed
9489badelement_constructor: input clarification; doctests marked as indirect
053ee33type(...) == ... --> isinstance(...)
7b49489clarification gens vs. gens_monomial
2bf6868prevent strange NotImplementedError from PowerSeriesRing

comment:42 Changed 4 years ago by behackl

  • 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 in Parent ("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 either data or raw_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 using type(data) == self.element_class in the second line and isinstance(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 between gens and gens_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 two ValueErrors

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 in G(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" from gens to gens_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 4 years ago by cheuberg

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

  • Branch changed from u/behackl/asy/growthGroup to 2bf68685c1f2c09a258b592d537f34cd9c77b2d3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.