#17601: Meta ticket: Asymptotic Expansions in SageMath
-------------------------------------+-------------------------------------
Reporter: behackl | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-7.1
Component: asymptotic | Resolution:
expansions | Merged in:
Keywords: asymptotics, | Reviewers:
gsoc15 | Work issues:
Authors: Benjamin Hackl, | Commit:
Daniel Krenn, Clemens Heuberger | 6351542e32ba8befee9ba8f7a655571ac3072824
Report Upstream: N/A | Stopgaps:
Branch: public/asy/trunk |
Dependencies: #17600, #17693, |
#17715, #17716, #18182, #18222, |
#18223, #18586, #18587, #18930, |
#19017, #19028, #19047, #19048, |
#19068, #19073, #19079, #19083, |
#19088, #19094, #19110, #19259, |
#19269, #19300, #19305, #19306, |
#19316, #19319, #19399, #19400, |
#19411, #19412, #19420, #19421, |
#19423, #19424, #19425, #19426, |
#19429, #19431, #19436, #19437, |
#19504, #19510, #19521, #19528, |
#19532, #19540, #19576, #19577, |
#19580, #19898, #19921, #19931, |
#19944, #19945, #19946, #19957, |
#19961, #19965, #19969, #19981 |
-------------------------------------+-------------------------------------
Changes (by behackl):
* dependencies:
#17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586,
#18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073,
#19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300,
#19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412,
#19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431,
#19436, #19437, #19504, #19510, #19521, #19528, #19532, #19540,
#19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945,
#19946, #19957, #19961, #19965, #19969
=>
#17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586,
#18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073,
#19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300,
#19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412,
#19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431,
#19436, #19437, #19504, #19510, #19521, #19528, #19532, #19540,
#19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945,
#19946, #19957, #19961, #19965, #19969, #19981
Old description:
> We intend to implement asymptotic expansions in !SageMath. We would like
> to do computations with simple expansions such as
>
> n^2^ + n^3/2^ + O(n^1/2^),
>
> but also with expansions such as
>
> 2^n^ * n + O(n*log(n))
>
> or even multivariate expansions such as
>
> 3*k/n + O(k^2^ / n^2^) 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
> [http://doc.sagemath.org/html/en/reference/asymptotic/sage/rings/asymptotic/asymptotic_ring.html
> 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^2^ 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
>
> * Bugs and minor improvements
> * #19399: let category of growth group be determined by input
> * #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
> * #19421: let asymptotic terms accept multivariate polynomials
> * #19423: !AsymptoticExpansion: combine shared code of invert, log,
> exp
> * #19424: enable !TestSuite for !AsymptoticRing
> * #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
> * #19504: better implementation of `AsymptoticExpansion.__hash__`
> * #19576: parentheses around coefficients of asymptotic expansions
> * #19577: performance improvement of mutable poset used for
> univariate asymptotic expansions
> * #19580: use `locals()` in growth group factory
> * #19921: handle zero coefficients when converting asymptotic rings
> * #19931: exact_part for asymptotic expansions
> * #19945: Asymptotic Ring: cannot construct (1/2)^n
> * #19946: Asymptotic Ring: cannot construct 2^n^ 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
>
> * 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
> * #19532: generators related to singularity analysis
> * #19969: enhancement of SA-generators: log-type singularities
>
> * More features
> * #19305: substitution of asymptotic expansions
> * #19528: `map_coefficients` for asymptotic expansions
> * #19540: factorial
> * #19944: singularity analysis
> * #19957: list plot comparing values
>
> * Further plans
> * for growth groups
> * implement dependencies like |k| <= n^1/2^ for different growth
> group variables.
> * 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.
> * Implementation of more types of asymptotic terms (little-oh
> terms, omega-terms, variations of big-Oh terms ...)
> * #19300: Run benchmarks on `MutablePoset.remove` to decide
> between two algorithms.
> * #19316 compute asymptotic expansion to some rational directly
>
> * Additional dependencies
> * #19017: Easy access to the `O`-constructor in `big_oh.py`.
> * #19110: QQ(0)^-1^ raises SIGFPE (which is caught)
>
> * Other related Tickets:
> * #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
New description:
We intend to implement asymptotic expansions in !SageMath. We would like
to do computations with simple expansions such as
n^2^ + n^3/2^ + O(n^1/2^),
but also with expansions such as
2^n^ * n + O(n*log(n))
or even multivariate expansions such as
3*k/n + O(k^2^ / n^2^) 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
[http://doc.sagemath.org/html/en/reference/asymptotic/sage/rings/asymptotic/asymptotic_ring.html
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^2^ 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
* Bugs and minor improvements
* #19399: let category of growth group be determined by input
* #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
* #19421: let asymptotic terms accept multivariate polynomials
* #19423: !AsymptoticExpansion: combine shared code of invert, log,
exp
* #19424: enable !TestSuite for !AsymptoticRing
* #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
* #19504: better implementation of `AsymptoticExpansion.__hash__`
* #19576: parentheses around coefficients of asymptotic expansions
* #19577: performance improvement of mutable poset used for univariate
asymptotic expansions
* #19580: use `locals()` in growth group factory
* #19921: handle zero coefficients when converting asymptotic rings
* #19931: exact_part for asymptotic expansions
* #19945: Asymptotic Ring: cannot construct (1/2)^n
* #19946: Asymptotic Ring: cannot construct 2^n^ 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
* #19981: minor improvements (`is_exact`, `_latex_`, ...)
* 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
* #19532: generators related to singularity analysis
* #19969: enhancement of SA-generators: log-type singularities
* More features
* #19305: substitution of asymptotic expansions
* #19528: `map_coefficients` for asymptotic expansions
* #19540: factorial
* #19944: singularity analysis
* #19957: list plot comparing values
* Further plans
* for growth groups
* implement dependencies like |k| <= n^1/2^ for different growth
group variables.
* 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.
* Implementation of more types of asymptotic terms (little-oh
terms, omega-terms, variations of big-Oh terms ...)
* #19300: Run benchmarks on `MutablePoset.remove` to decide
between two algorithms.
* #19316 compute asymptotic expansion to some rational directly
* Additional dependencies
* #19017: Easy access to the `O`-constructor in `big_oh.py`.
* #19110: QQ(0)^-1^ raises SIGFPE (which is caught)
* Other related Tickets:
* #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
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17601#comment:134>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
