behackl commented 9 years ago

We intend to implement asymptotic expansions in SageMath. We would like to do computations with simple expansions such as

n² + n^3/2 + O(n^1/2),

but also with expansions such as

2ⁿ n + O(nlog(n))

or even multivariate expansions such as

3*k/n + O(k² / n²) with |k| <= n^(1/2).

Of course, O(n) - O(n) = O(n) must hold and we want to perform various arithmetic operations with these asymptotic expansions. Eventually, specified O-constants shall also be supported.

See the documentation files for a more examples and a detailed description. A working prototype is include in SageMath 6.10 and a version containing all features can be found in branch public/asy/trunk.

Roadmap:

Implementing a minimal working example
- 17600 (AsymptoticGrowthElement): elements which handle the asymptotic growth. Such an element holds, e.g. n² or k/n or n*log(n). This can compare, multiply etc., but has no coefficient; the order of magnitude is managed here. Concretely for this ticket: MonomialGrowthElement, implementation for powers.
- 18930: Factory for user-friendly generation of growth groups
- 17715 (AsymptoticTerm): a summand for asymptotic expansions. They contain the growth and additional information on the type of the summand. For starters, there will be big-Oh terms (e.g. O(n) and exact terms (e.g. 3*n^2).
- 17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expansions.
- 17716 (AsymptoticRing and AsymptoticExpansion): sum of asymptotic terms.
Extending the functionality of growth groups
- 18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expansions)
  - 18223: cartesian products with orders
  - 18586: passing on parameters and extra_category for cartesian products
- 19028: More growth group implementations: exponential growth groups.
Extending the functionality of the AsymptoticRing and AsymptoticExpansion
- 19048: AsymptoticRing.an_element()
  - 19047: QQ.some_elements()
  - 19319: iterator over pairs on diagonals a la Cantor pairing
- 19068: Implement Division for asymptotic expansions.
- 19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups
  - 18182: pushout construction and finding common parents for/including cartesian products
  - 19079: ConstructionFunctor: remove __str__
- 19083: AsymptoticRing: exp, log, cleanup, some improvements, documentation.
  - contains #19094: Implement higher-order operations like exp and log for asymptotic expansions
- 19400: move documentation to sage.asymptotic
Additional dependencies
- 19017: Easy access to the O-constructor in big_oh.py.
- 19110: QQ(0)^-1 raises SIGFPE (which is caught)
We have a working prototype (made of the tickets above).
Arithmetic, categories and coercion (bugs and improvements)
- 19399: let category of growth group be determined by input
- 19316: compute asymptotic expansion to some rational directly
- 19411: hidden but caught infinite loop in action of cartesian products of growth groups
- 19412: log of an asymptotic expansion ignores coefficient ring
- 19420: make log of growth elements to the base of some powers of elements possible
- 19423: AsymptoticExpansion: combine shared code of invert, log, exp
- 19577: performance improvement of mutable poset used for univariate asymptotic expansions
- 20000: sqrt of AsymptoticExpansion
- 20043: multiplication with zero fails
- 20044: calculate asymptotic expansions to some asymptotic expansions exponents directly
- 21665: AsymptoticRing.substitute fails with exponents in QQbar
- 22396: AsymptoticRing default_prec lost with coercion
- 22414: check for subs of AsymptoticExpansion
Conversion (bugs and improvements)
- 19421: let asymptotic terms accept multivariate polynomials
- 19426: AsymptoticRing: convert Orders of symbolic ring
  - 19425: Order in symbolic ring: error calling operator
- 19429: extend conversion from SR to growth groups: allow inverses
- 19431: convert asymptotic expansion to the symbolic ring
  - 19436: fixup of #19431
  - 19437: SR.symbol: correct parent in inherting classes of SymbolicRing
- 19921: handle zero coefficients when converting asymptotic rings
- 19945: Asymptotic Ring: cannot construct (1/2)^n
- 19946: Asymptotic Ring: cannot construct 2ⁿ when coefficient ring is SR
  - 19961: mention rpow of asymptotic ring in module doc/examples more prominently
  - 19965: parent of exponent getting too large in exponentiation in asymptotic ring
- 19947: conversion SR to asymptotic ring
Other bugs and minor improvements
- 19300: Run benchmarks on MutablePoset.remove to decide between two algorithms.
- 19424: enable TestSuite for AsymptoticRing
- 19504: better implementation of AsymptoticExpansion.__hash__
- 19576: parentheses around coefficients of asymptotic expansions
- 19580: use locals() in growth group factory
- 19981: implementation of is_exact for asymptotic expansions
- 19987: LaTeX-representation of asymptotic expansions
- 19999: infinite recursion creating certain asymptotic expansion
- 20045: move wrongly imported series_precision in AsymptoticRing
- 22140: remove "import sage" from sage.rings.asymptotic.*
- 22340: coefficient of an AsymptoticExpansion
- 22395: ordering of (O-)terms: absolute values, real parts, etc.
- 22944: remove experimental warning of asymptotic ring
Generators for asymptotic expansions
- 19306: common generators for asymptotic expansions
  - 19259: subrings of the symbolic ring
- 19510: generator for binomial(kn, n)
  - 19521: wrong inverse action when using ConstructionFunctor.coercion_reversed
- 19898: generator for expansion of harmonic number
Singularity analysis
- 19532: generators related to singularity analysis
- 19969: enhancement of SA-generators: log-type singularities
  - 19993: Arb: parse symbolic expressions
- 19944: singularity analysis
- 20020: singularity analysis (log-type) without renormalization
- 20040: singularity analysis method for log-type singularities
- 20049: singularity in formula in docstring of SingularityAnalysis-generator
- 20056: rename AsymptoticRing.singularity_analysis to coefficients_of_generating_function
- 20051: speed up singularity analysis (log-type) without renormalization
- 20052: allow symbolic expressions
- 20053: allow singular expansions as input
- 20054: intelligent choice of precision
- 20055: non-integral exponents beta also outside of generators
- 21659: coefficients_of_generating_function: hardcoded exponents in QQ
- 22360: raise proper !OZero-exception (instead of AttributeError)
More features
- 19305: substitution of asymptotic expansions
- 19528: map_coefficients for asymptotic expansions
- 19931: exact_part for asymptotic expansions
- 19540: factorial
- 19957: list plot comparing values
Further plans
- for growth groups
  - implement dependencies like |k| <= n^1/2 for different growth group variables.
  - 20050: growth groups with asymptotic at a non-infinity point
    - MultivariatePuiseuxSeriesRing
- other
  - Deal with comparison for asymptotic expansions.
  - Check and improve the performance of computations in the AsymptoticRing.
    - 20065: Asymptotic Expansions: adaptive precision
  - Implementation of more types of asymptotic terms (little-oh terms, omega-terms, variations of big-Oh terms ...)
Other related tickets:
- 10519: analytic combinatorics: new code for computing asymptotics for multivariate generating functions
  - 19989: asymptotics for multivariate generating functions: zero division error on last coordinate
- 18092: evaluating symbolic expressions
- 18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
- 19088: multi-line doctests fail when using angle notation (preparser)
- 19269: add category Posets to ZZ and QQ

Depends on #17600 Depends on #17693 Depends on #17715 Depends on #17716 Depends on #18182 Depends on #18222 Depends on #18223 Depends on #18586 Depends on #18587 Depends on #18930 Depends on #19017 Depends on #19028 Depends on #19047 Depends on #19048 Depends on #19068 Depends on #19073 Depends on #19079 Depends on #19083 Depends on #19088 Depends on #19094 Depends on #19110 Depends on #19259 Depends on #19269 Depends on #19300 Depends on #19305 Depends on #19306 Depends on #19316 Depends on #19319 Depends on #19399 Depends on #19400 Depends on #19411 Depends on #19412 Depends on #19420 Depends on #19421 Depends on #19423 Depends on #19424 Depends on #19425 Depends on #19426 Depends on #19429 Depends on #19431 Depends on #19436 Depends on #19437 Depends on #19504 Depends on #19510 Depends on #19521 Depends on #19528 Depends on #19532 Depends on #19540 Depends on #19576 Depends on #19577 Depends on #19580 Depends on #19898 Depends on #19921 Depends on #19931 Depends on #19944 Depends on #19945 Depends on #19946 Depends on #19957 Depends on #19961 Depends on #19965 Depends on #19969 Depends on #19981 Depends on #19987 Depends on #19999 Depends on #20000 Depends on #20020 Depends on #20040 Depends on #20043 Depends on #20044 Depends on #20045 Depends on #20049 Depends on #20050 Depends on #20051 Depends on #20052 Depends on #20053 Depends on #20054 Depends on #20055 Depends on #20056 Depends on #20065 Depends on #21659 Depends on #21665 Depends on #22140 Depends on #22340 Depends on #22360 Depends on #22395 Depends on #22396 Depends on #22414 Depends on #22944

CC: @dkrenn @cheuberg @nathanncohen @videlec @malb @mezzarobba @rwst @kalvotom

Component: asymptotic expansions

Keywords: gsoc15

Author: Benjamin Hackl, Daniel Krenn, Clemens Heuberger

Branch/Commit: public/asy/trunk @ db96be9

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

behackl commented 9 years ago

Dependencies: 17600

behackl commented 9 years ago

Changed dependencies from 17600 to #17600

tscrim commented 9 years ago

comment:3

10519 might be of interest.

dkrenn commented 9 years ago

comment:4

Replying to @tscrim:

10519 might be of interest.

Thanks---I'm involved in both tickets ;)

At the moment both are independent, but when the asymptotic expressions are created, one can use them in the calculations (or at least as a possible output format) in #10519.

dkrenn commented 9 years ago

Changed dependencies from #17600 to #17600, #17693

dkrenn commented 9 years ago

Description changed:

--- 
+++ 
@@ -36,4 +36,4 @@

 AsymptoticExpression, however, can be general enough to deal with all cases; here, the sum, the product, the exponential function, etc. are implemented in a generic setting.

-In #17600, we start with AsymptoticGrowthElement.
+In #17600, we start with AsymptoticGrowthElement. #17693 implements a data structure (MutablePoset) for an asymptotic expression

behackl commented 9 years ago

Description changed:

--- 
+++ 
@@ -36,4 +36,8 @@

 AsymptoticExpression, however, can be general enough to deal with all cases; here, the sum, the product, the exponential function, etc. are implemented in a generic setting.

-In #17600, we start with AsymptoticGrowthElement. #17693 implements a data structure (MutablePoset) for an asymptotic expression
+Related Tickets:
+    #17600 (AsmyptoticGrowthElement): elements which handle the asymptotic growth.
+    #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, growth + additional information (OTerm, ExactTerm, ...).
+    #17716 (AsymptoticExpression): sum of multiple asymptotic terms.
+    #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.

behackl commented 9 years ago

Changed dependencies from #17600, #17693 to #17600, #17693, #17715, #17716

fredrik-johansson commented 9 years ago

comment:11

Are "asymptotic expressions" equivalent to "transseries" (http://arxiv.org/abs/0801.4877, http://www.texmacs.org/joris/ln/ln-abs.html)? Or are they more general, less general, or partially overlapping in scope?

videlec commented 9 years ago

comment:13

Hi,

Whatever you propose, I would say that the most important thing to do is to consider the integration into Sage. In other words:

how it will be used from Sage
how it does interact with the Symbolic ring, polynomials, fraction fields, power series and any objects where asymptotic makes sens I do not see any of this in the ticket description. And it is definitely important to think of it before starting the implementation.

I only see a list of classes, parents and elements whose goal is basically to mimic the symbolic ring by adding some big Oh. I do not see the point of creating so much classes to handle asymptotic terms. Please, motivate and explain your choices.

Vincent

cheuberg commented 9 years ago

comment:14

Replying to @videlec:

I only see a list of classes, parents and elements whose goal is basically to mimic the symbolic ring by adding some big Oh.

I rather think of it as a version of the PowerSeriesRing with additional features (non-integer exponents, several (not completely independent) variables).

dkrenn commented 9 years ago

Changed dependencies from #17600, #17693, #17715, #17716 to #17600, #17693, #17715, #17716, #18182, #18222, #18223

dkrenn commented 9 years ago

Description changed:

--- 
+++ 
@@ -41,3 +41,9 @@
     #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, growth + additional information (OTerm, ExactTerm, ...).
     #17716 (AsymptoticExpression): sum of multiple asymptotic terms.
     #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
+
+Other Dependencies:
+    #18182: pushout construction and finding common parents for/including cartesian products
+    #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
+    #18223: new categories for cartesian products with orders
+

dkrenn commented 9 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587

dkrenn commented 9 years ago

Description changed:

--- 
+++ 
@@ -41,9 +41,11 @@
     #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, growth + additional information (OTerm, ExactTerm, ...).
     #17716 (AsymptoticExpression): sum of multiple asymptotic terms.
     #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
+    #18587: cartesian products of growth groups

 Other Dependencies:
     #18182: pushout construction and finding common parents for/including cartesian products
     #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
-    #18223: new categories for cartesian products with orders
+    #18223: cartesian products with orders
+    #18586: passing on parameters and extra_category

behackl commented 9 years ago

Description changed:

--- 
+++ 
@@ -15,19 +15,17 @@
 Eventually, specified O-constants shall also be supported.

 The current plan is to implement the following classes (plus derivatives for more concrete situations). For simplicity, the corresponding parents are not listed here.
-    
- AsymptoticGrowthElement::
-  hold `_one_` term, e.g. n<sup>2</sup> or k/n or n*log(n). This can compare, multiply etc.,
-  but has **no** coefficient. Here, only the order of magnitude shall be managed.

- AsymptoticTerm::
+
+ AsymptoticGrowthElement:: hold `_one_` term, e.g. n<sup>2</sup> or k/n or n*log(n). This can compare, multiply etc., but has **no** coefficient. Here, only the order of magnitude shall be managed.
+
+ AsymptoticTerm:: 

   holds one AsymptoticGrowthElement, plus information on the coefficient or that it is an O-term etc.

- AsymptoticExpression::
+ AsymptoticExpression:: 

   represents the sum of several AsymptoticTerms.
-

 The idea is to override AsymptoticGrowthElement to obtain specific behaviour (as mentioned in our wishlist) because it seems unlikely to be able to handle everything in one class.
 For starters, there will be an GrowthGroupPowerElement.
@@ -36,16 +34,36 @@

 AsymptoticExpression, however, can be general enough to deal with all cases; here, the sum, the product, the exponential function, etc. are implemented in a generic setting.

-Related Tickets:
-    #17600 (AsmyptoticGrowthElement): elements which handle the asymptotic growth.
-    #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, growth + additional information (OTerm, ExactTerm, ...).
-    #17716 (AsymptoticExpression): sum of multiple asymptotic terms.
-    #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
-    #18587: cartesian products of growth groups
+---

-Other Dependencies:
-    #18182: pushout construction and finding common parents for/including cartesian products
-    #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
-    #18223: cartesian products with orders
-    #18586: passing on parameters and extra_category
+**Roadmap**:

+
+* Implementing a minimal working example
+    * #17600 (AsymptoticGrowthElement): elements which handle the asymptotic growth. Concretely: MonomialGrowthElement, implementation for powers.
+    * #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, they contain the growth and additional information on the type of the term. For starters, there will be big-Oh terms and exact terms.
+    * #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
+    * #17716 (AsymptoticExpression): sum of asymptotic terms.
+
+* Extending the functionality of AsymptoticExpression
+    * Implement Division for asymptotic Expressions
+    * Implement higher-order operations like `exp` and `log` for asymptotic expressions.
+    * Improve the user interface: extend the conversion from the symbolic ring such that more than just monomials can be converted.
+    * Implement comparison for asymptotic expressions.
+
+* Extending the functionality of growth groups
+    * More growth group implementations: logarithmic and exponential growth groups.
+    * #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expressions)
+        * #18223: cartesian products with orders
+        * #18586: passing on parameters and extra_category for cartesian products
+        * implement dependencies like |k| <= n<sup>1/2</sup> for different growth group variables.
+
+* Further plans
+    * growth groups with asymptotic at a non-infinity point
+    * Implementation of more types of asymptotic terms (little-oh terms, omega-terms, variations of big-Oh terms ...)
+
+
+* Additional Dependencies:
+    * #18182: pushout construction and finding common parents for/including cartesian products
+    * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
+

behackl commented 9 years ago

Changed keywords from none to gsoc15

behackl commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930

behackl commented 8 years ago

Description changed:

--- 
+++ 
@@ -52,6 +52,7 @@
     * Implement comparison for asymptotic expressions.

 * Extending the functionality of growth groups
+    * #18930: Factory for user-friendly generation of growth groups
     * More growth group implementations: logarithmic and exponential growth groups.
     * #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expressions)
         * #18223: cartesian products with orders

behackl commented 8 years ago

Description changed:

--- 
+++ 
@@ -41,6 +41,7 @@

 * Implementing a minimal working example
     * #17600 (AsymptoticGrowthElement): elements which handle the asymptotic growth. Concretely: MonomialGrowthElement, implementation for powers.
+    * #18930: Factory for user-friendly generation of growth groups
     * #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, they contain the growth and additional information on the type of the term. For starters, there will be big-Oh terms and exact terms.
     * #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
     * #17716 (AsymptoticExpression): sum of asymptotic terms.
@@ -50,9 +51,9 @@
     * Implement higher-order operations like `exp` and `log` for asymptotic expressions.
     * Improve the user interface: extend the conversion from the symbolic ring such that more than just monomials can be converted.
     * Implement comparison for asymptotic expressions.
+    * Improve the performance of computations in the AsymptoticRing.

 * Extending the functionality of growth groups
-    * #18930: Factory for user-friendly generation of growth groups
     * More growth group implementations: logarithmic and exponential growth groups.
     * #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expressions)
         * #18223: cartesian products with orders

behackl commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028

behackl commented 8 years ago

Description changed:

--- 
+++ 
@@ -47,6 +47,7 @@
     * #17716 (AsymptoticExpression): sum of asymptotic terms.

 * Extending the functionality of AsymptoticExpression
+    * #19017: Easy access to the `O`-constructor in `big_oh.py`.
     * Implement Division for asymptotic Expressions
     * Implement higher-order operations like `exp` and `log` for asymptotic expressions.
     * Improve the user interface: extend the conversion from the symbolic ring such that more than just monomials can be converted.
@@ -54,7 +55,7 @@
     * Improve the performance of computations in the AsymptoticRing.

 * Extending the functionality of growth groups
-    * More growth group implementations: logarithmic and exponential growth groups.
+    * #19028: More growth group implementations: exponential growth groups.
     * #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expressions)
         * #18223: cartesian products with orders
         * #18586: passing on parameters and extra_category for cartesian products

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -44,7 +44,7 @@
     * #18930: Factory for user-friendly generation of growth groups
     * #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, they contain the growth and additional information on the type of the term. For starters, there will be big-Oh terms and exact terms.
     * #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
-    * #17716 (AsymptoticExpression): sum of asymptotic terms.
+    * #17716 (AsymptoticRing and AsymptoticExpression): sum of asymptotic terms.

 * Extending the functionality of AsymptoticExpression
     * #19017: Easy access to the `O`-constructor in `big_oh.py`.

dkrenn commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -53,6 +53,7 @@
     * Improve the user interface: extend the conversion from the symbolic ring such that more than just monomials can be converted.
     * Implement comparison for asymptotic expressions.
     * Improve the performance of computations in the AsymptoticRing.
+    * #19048: `AsymptoticRing.an_element()`

 * Extending the functionality of growth groups
     * #19028: More growth group implementations: exponential growth groups.
@@ -69,4 +70,5 @@
 * Additional Dependencies:
     * #18182: pushout construction and finding common parents for/including cartesian products
     * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
+    * #19047: `QQ.some_elements()`

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -10,29 +10,9 @@

 3*k/n + O(k<sup>2</sup> / n<sup>2</sup>) with |k| <= n<sup>(1/2)</sup>.

-Of course, O(n) - O(n) = O(n) must hold.
+Of course, O(n) - O(n) = O(n) must hold and we want to perform various arithmetic operations with these asymptotic expressions. Eventually, specified O-constants shall also be supported.

-Eventually, specified O-constants shall also be supported.
-
-The current plan is to implement the following classes (plus derivatives for more concrete situations). For simplicity, the corresponding parents are not listed here.
-
-
- AsymptoticGrowthElement:: hold `_one_` term, e.g. n<sup>2</sup> or k/n or n*log(n). This can compare, multiply etc., but has **no** coefficient. Here, only the order of magnitude shall be managed.
-
- AsymptoticTerm:: 
-
-  holds one AsymptoticGrowthElement, plus information on the coefficient or that it is an O-term etc.
-
- AsymptoticExpression:: 
-
-  represents the sum of several AsymptoticTerms.
-
-The idea is to override AsymptoticGrowthElement to obtain specific behaviour (as mentioned in our wishlist) because it seems unlikely to be able to handle everything in one class.
-For starters, there will be an GrowthGroupPowerElement.
-
-AsymptoticTerm is expected to be more general; it might be necessary to override it for the case of specified O-constants.
-
-AsymptoticExpression, however, can be general enough to deal with all cases; here, the sum, the product, the exponential function, etc. are implemented in a generic setting.
+See #17716 for more examples.

 ---

@@ -40,9 +20,9 @@

 * Implementing a minimal working example
-    * #17600 (AsymptoticGrowthElement): elements which handle the asymptotic growth. Concretely: MonomialGrowthElement, implementation for powers.
+    * #17600 (AsymptoticGrowthElement): elements which handle the asymptotic growth. Such an element holds, e.g. n<sup>2</sup> or k/n or n*log(n). This can compare, multiply etc., but has **no** coefficient; the order of magnitude is managed here. Concretely for this ticket: MonomialGrowthElement, implementation for powers.
     * #18930: Factory for user-friendly generation of growth groups
-    * #17715 (AsymptoticTerm): "building blocks" for asymptotic expressions, they contain the growth and additional information on the type of the term. For starters, there will be big-Oh terms and exact terms.
+    * #17715 (AsymptoticTerm): a summand for asymptotic expressions. They contain the growth and additional information on the type of the summand. For starters, there will be big-Oh terms (e.g. `O(n)` and exact terms (e.g. `3*n^2`). 
     * #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
     * #17716 (AsymptoticRing and AsymptoticExpression): sum of asymptotic terms.

@@ -54,6 +34,7 @@
     * Implement comparison for asymptotic expressions.
     * Improve the performance of computations in the AsymptoticRing.
     * #19048: `AsymptoticRing.an_element()`
+        * #19047: `QQ.some_elements()`

 * Extending the functionality of growth groups
     * #19028: More growth group implementations: exponential growth groups.
@@ -70,5 +51,4 @@
 * Additional Dependencies:
     * #18182: pushout construction and finding common parents for/including cartesian products
     * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
-    * #19047: `QQ.some_elements()`

behackl commented 8 years ago

Description changed:

--- 
+++ 
@@ -28,7 +28,7 @@

 * Extending the functionality of AsymptoticExpression
     * #19017: Easy access to the `O`-constructor in `big_oh.py`.
-    * Implement Division for asymptotic Expressions
+    * #19068: Implement Division for asymptotic Expressions.
     * Implement higher-order operations like `exp` and `log` for asymptotic expressions.
     * Improve the user interface: extend the conversion from the symbolic ring such that more than just monomials can be converted.
     * Implement comparison for asymptotic expressions.

behackl commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -26,7 +26,7 @@
     * #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
     * #17716 (AsymptoticRing and AsymptoticExpression): sum of asymptotic terms.

-* Extending the functionality of AsymptoticExpression
+* Extending the functionality of the AsymptoticRing and AsymptoticExpression
     * #19017: Easy access to the `O`-constructor in `big_oh.py`.
     * #19068: Implement Division for asymptotic Expressions.
     * Implement higher-order operations like `exp` and `log` for asymptotic expressions.
@@ -35,6 +35,8 @@
     * Improve the performance of computations in the AsymptoticRing.
     * #19048: `AsymptoticRing.an_element()`
         * #19047: `QQ.some_elements()`
+    * #19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups
+        * #18182: pushout construction and finding common parents for/including cartesian products

 * Extending the functionality of growth groups
     * #19028: More growth group implementations: exponential growth groups.
@@ -49,6 +51,5 @@

 * Additional Dependencies:
-    * #18182: pushout construction and finding common parents for/including cartesian products
     * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)

dkrenn commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073

dkrenn commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -52,4 +52,5 @@

 * Additional Dependencies:
     * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
+    * #19079: ConstructionFunctor: remove `__str__`

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -37,6 +37,7 @@
         * #19047: `QQ.some_elements()`
     * #19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups
         * #18182: pushout construction and finding common parents for/including cartesian products
+        * #19079: ConstructionFunctor: remove `__str__`

 * Extending the functionality of growth groups
     * #19028: More growth group implementations: exponential growth groups.
@@ -52,5 +53,4 @@

 * Additional Dependencies:
     * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
-    * #19079: ConstructionFunctor: remove `__str__`

dkrenn commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -38,6 +38,7 @@
     * #19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups
         * #18182: pushout construction and finding common parents for/including cartesian products
         * #19079: ConstructionFunctor: remove `__str__`
+    * #19083: AsymptoticRing: cleanup, some improvements, documentation.

 * Extending the functionality of growth groups
     * #19028: More growth group implementations: exponential growth groups.

behackl commented 8 years ago

Description changed:

--- 
+++ 
@@ -29,7 +29,7 @@
 * Extending the functionality of the AsymptoticRing and AsymptoticExpression
     * #19017: Easy access to the `O`-constructor in `big_oh.py`.
     * #19068: Implement Division for asymptotic Expressions.
-    * Implement higher-order operations like `exp` and `log` for asymptotic expressions.
+    * #19094: Implement higher-order operations like `exp` and `log` for asymptotic expressions.
     * Improve the user interface: extend the conversion from the symbolic ring such that more than just monomials can be converted.
     * Implement comparison for asymptotic expressions.
     * Improve the performance of computations in the AsymptoticRing.

behackl commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -54,4 +54,5 @@

 * Additional Dependencies:
     * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
+    * #19110: QQ(0)^-1 raises SIGFPE (which is caught)

dkrenn commented 8 years ago

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094, #19110

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -26,13 +26,16 @@
     * #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expression.
     * #17716 (AsymptoticRing and AsymptoticExpression): sum of asymptotic terms.

+* Extending the functionality of growth groups
+    * #19028: More growth group implementations: exponential growth groups.
+    * #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expressions)
+        * #18223: cartesian products with orders
+        * #18586: passing on parameters and extra_category for cartesian products
+        * implement dependencies like |k| <= n<sup>1/2</sup> for different growth group variables.
+
 * Extending the functionality of the AsymptoticRing and AsymptoticExpression
-    * #19017: Easy access to the `O`-constructor in `big_oh.py`.
     * #19068: Implement Division for asymptotic Expressions.
     * #19094: Implement higher-order operations like `exp` and `log` for asymptotic expressions.
-    * Improve the user interface: extend the conversion from the symbolic ring such that more than just monomials can be converted.
-    * Implement comparison for asymptotic expressions.
-    * Improve the performance of computations in the AsymptoticRing.
     * #19048: `AsymptoticRing.an_element()`
         * #19047: `QQ.some_elements()`
     * #19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups
@@ -40,19 +43,14 @@
         * #19079: ConstructionFunctor: remove `__str__`
     * #19083: AsymptoticRing: cleanup, some improvements, documentation.

-* Extending the functionality of growth groups
-    * #19028: More growth group implementations: exponential growth groups.
-    * #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expressions)
-        * #18223: cartesian products with orders
-        * #18586: passing on parameters and extra_category for cartesian products
-        * implement dependencies like |k| <= n<sup>1/2</sup> for different growth group variables.
-
 * Further plans
     * growth groups with asymptotic at a non-infinity point
+    * Deal with comparison for asymptotic expressions.
+    * Check and improve the performance of computations in the AsymptoticRing.
     * Implementation of more types of asymptotic terms (little-oh terms, omega-terms, variations of big-Oh terms ...)

-
 * Additional Dependencies:
+    * #19017: Easy access to the `O`-constructor in `big_oh.py`.
     * #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
     * #19110: QQ(0)^-1 raises SIGFPE (which is caught)

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -31,7 +31,6 @@
     * #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expressions)
         * #18223: cartesian products with orders
         * #18586: passing on parameters and extra_category for cartesian products
-        * implement dependencies like |k| <= n<sup>1/2</sup> for different growth group variables.

 * Extending the functionality of the AsymptoticRing and AsymptoticExpression
     * #19068: Implement Division for asymptotic Expressions.
@@ -44,10 +43,13 @@
     * #19083: AsymptoticRing: cleanup, some improvements, documentation.

 * Further plans
-    * growth groups with asymptotic at a non-infinity point
-    * Deal with comparison for asymptotic expressions.
-    * Check and improve the performance of computations in the AsymptoticRing.
-    * Implementation of more types of asymptotic terms (little-oh terms, omega-terms, variations of big-Oh terms ...)
+    * for growth groups
+        * implement dependencies like |k| <= n<sup>1/2</sup> for different growth group variables.
+        * growth groups with asymptotic at a non-infinity point
+    * other
+        * Deal with comparison for asymptotic expressions.
+        * Check and improve the performance of computations in the AsymptoticRing.
+        * Implementation of more types of asymptotic terms (little-oh terms, omega-terms, variations of big-Oh terms ...)

 * Additional Dependencies:
     * #19017: Easy access to the `O`-constructor in `big_oh.py`.

dkrenn commented 8 years ago

Branch: u/dkrenn/asy/prototype

dkrenn commented 8 years ago

Commit: 70abf65

dkrenn commented 8 years ago

Last 10 new commits:

`47894c8`	`Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype`
`8894fce`	`Merge branch 't/17716/asy/asymptoticExpression' into t/19068/asy/inversion`
`106eacd`	`Merge branch 't/19068/asy/inversion' into t/19083/asy/prototype`
`1108cfc`	`Merge branch 't/17716/asy/asymptoticExpression' into t/19048/asy/an_element`
`3c2fa0c`	`Merge branch 't/19048/asy/an_element' into t/19083/asy/prototype`
`1812a5e`	`rename doc-index-file`
`0720b14`	`fix doctests: update since TestSuite now checks for cardinality`
`14f9a9a`	`Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype`
`9aba4b6`	`make entry in reference/index`
`70abf65`	`include misc`

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -12,7 +12,9 @@

 Of course, O(n) - O(n) = O(n) must hold and we want to perform various arithmetic operations with these asymptotic expressions. Eventually, specified O-constants shall also be supported.

-See #17716 for more examples.
+---
+
+See #17716 and #19083 for more examples. A working prototype can be found in branch u/dkrenn/asy/prototype (based on 6.9.beta5).

 ---

dkrenn commented 8 years ago

Description changed:

--- 
+++ 
@@ -14,7 +14,7 @@

 ---

-See #17716 and #19083 for more examples. A working prototype can be found in branch u/dkrenn/asy/prototype (based on 6.9.beta5).
+See #17716 and #19083 for more examples and the documentation files there for a more detailed description. A working prototype can be found in branch u/dkrenn/asy/prototype (based on 6.9.beta5).

 ---

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 70abf65 to 2e4a415

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

2e4a415 rename title

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 2e4a415 to b0e228b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`cd17673`	`Merge tag '6.9.beta6' into t/18182/18182-on-6.8`
`3eefe25`	`correct typo in AUTHORS`
`5fe52e4`	`fix doctests since name of cartesian product functor has changed`
`60b9375`	`revert changes in base_ring of category_object and adapt doctests`
`8d6de43`	`Merge remote-tracking branch 'trac/u/dkrenn/18182/pushout' into t/19073/asy/groups-coercion`
`d50cc55`	`Merge branch 't/19073/asy/groups-coercion' into t/19094/asy/ring-exp-log`
`44fbccc`	`Merge remote-tracking branch 'origin/u/dkrenn/asy/ring-exp-log' into t/19094/asy/ring-exp-log`
`09032ee`	`Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype`
`b0e228b`	`Merge remote-tracking branch 'origin/u/dkrenn/asy/prototype' into t/19083/asy/prototype`

sagemath / sage

Meta ticket: Asymptotic Expansions in SageMath #17601

18930: Factory for user-friendly generation of growth groups

17715 (AsymptoticTerm): a summand for asymptotic expansions. They contain the growth and additional information on the type of the summand. For starters, there will be big-Oh terms (e.g. O(n) and exact terms (e.g. 3*n^2).

17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expansions.

17716 (AsymptoticRing and AsymptoticExpansion): sum of asymptotic terms.

18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expansions)

18223: cartesian products with orders

18586: passing on parameters and extra_category for cartesian products

19028: More growth group implementations: exponential growth groups.

19048: AsymptoticRing.an_element()

19047: QQ.some_elements()

19319: iterator over pairs on diagonals a la Cantor pairing

19068: Implement Division for asymptotic expansions.

19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups

18182: pushout construction and finding common parents for/including cartesian products

19079: ConstructionFunctor: remove __str__

19083: AsymptoticRing: exp, log, cleanup, some improvements, documentation.

19400: move documentation to sage.asymptotic

19017: Easy access to the O-constructor in big_oh.py.

19110: QQ(0)-1 raises SIGFPE (which is caught)

19399: let category of growth group be determined by input

19316: compute asymptotic expansion to some rational directly

19411: hidden but caught infinite loop in action of cartesian products of growth groups

19412: log of an asymptotic expansion ignores coefficient ring

19420: make log of growth elements to the base of some powers of elements possible

19423: AsymptoticExpansion: combine shared code of invert, log, exp

19577: performance improvement of mutable poset used for univariate asymptotic expansions

20000: sqrt of AsymptoticExpansion

20043: multiplication with zero fails

20044: calculate asymptotic expansions to some asymptotic expansions exponents directly

21665: AsymptoticRing.substitute fails with exponents in QQbar

22396: AsymptoticRing default_prec lost with coercion

22414: check for subs of AsymptoticExpansion

19421: let asymptotic terms accept multivariate polynomials

19426: AsymptoticRing: convert Orders of symbolic ring

19425: Order in symbolic ring: error calling operator

19429: extend conversion from SR to growth groups: allow inverses

19431: convert asymptotic expansion to the symbolic ring

19436: fixup of #19431

19437: SR.symbol: correct parent in inherting classes of SymbolicRing

19921: handle zero coefficients when converting asymptotic rings

19945: Asymptotic Ring: cannot construct (1/2)^n

19946: Asymptotic Ring: cannot construct 2n when coefficient ring is SR

19961: mention rpow of asymptotic ring in module doc/examples more prominently

19965: parent of exponent getting too large in exponentiation in asymptotic ring

19947: conversion SR to asymptotic ring

19300: Run benchmarks on MutablePoset.remove to decide between two algorithms.

19424: enable TestSuite for AsymptoticRing

19504: better implementation of AsymptoticExpansion.__hash__

19576: parentheses around coefficients of asymptotic expansions

19580: use locals() in growth group factory

19981: implementation of is_exact for asymptotic expansions

19987: LaTeX-representation of asymptotic expansions

19999: infinite recursion creating certain asymptotic expansion

20045: move wrongly imported series_precision in AsymptoticRing

22140: remove "import sage" from sage.rings.asymptotic.*

22340: coefficient of an AsymptoticExpansion

22395: ordering of (O-)terms: absolute values, real parts, etc.

22944: remove experimental warning of asymptotic ring

19306: common generators for asymptotic expansions

19259: subrings of the symbolic ring

19510: generator for binomial(kn, n)

19521: wrong inverse action when using ConstructionFunctor.coercion_reversed

19898: generator for expansion of harmonic number

19532: generators related to singularity analysis

19969: enhancement of SA-generators: log-type singularities

19993: Arb: parse symbolic expressions

19944: singularity analysis

20020: singularity analysis (log-type) without renormalization

20040: singularity analysis method for log-type singularities

20049: singularity in formula in docstring of SingularityAnalysis-generator

20056: rename AsymptoticRing.singularity_analysis to coefficients_of_generating_function

20051: speed up singularity analysis (log-type) without renormalization

20052: allow symbolic expressions

20053: allow singular expansions as input

20054: intelligent choice of precision

20055: non-integral exponents beta also outside of generators

21659: coefficients_of_generating_function: hardcoded exponents in QQ

22360: raise proper !OZero-exception (instead of AttributeError)

17715 (AsymptoticTerm): a summand for asymptotic expansions. They contain the growth and additional information on the type of the summand. For starters, there will be big-Oh terms (e.g. `O(n)` and exact terms (e.g. `3*n^2`).

19048: `AsymptoticRing.an_element()`

19047: `QQ.some_elements()`

19079: ConstructionFunctor: remove `str`

19083: AsymptoticRing: `exp`, `log`, cleanup, some improvements, documentation.

19017: Easy access to the `O`-constructor in `big_oh.py`.

19110: QQ(0)^-1 raises SIGFPE (which is caught)

21665: `AsymptoticRing.substitute` fails with exponents in QQbar

19946: Asymptotic Ring: cannot construct 2ⁿ when coefficient ring is SR

19300: Run benchmarks on `MutablePoset.remove` to decide between two algorithms.

19504: better implementation of `AsymptoticExpansion.hash`

19580: use `locals()` in growth group factory

19981: implementation of `is_exact` for asymptotic expansions

19521: wrong inverse action when using `ConstructionFunctor.coercion_reversed`

20056: rename `AsymptoticRing.singularity_analysis` to `coefficients_of_generating_function`

21659: `coefficients_of_generating_function`: hardcoded exponents in `QQ`

19528: `map_coefficients` for asymptotic expansions