#17601: Meta-Ticket: Asymptotic Expansions in SageMath
-------------------------------------+-------------------------------------
Reporter: behackl | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.6
Component: symbolics | Resolution:
Keywords: asymptotics, | Merged in:
gsoc15 | Reviewers:
Authors: Benjamin Hackl, | Work issues:
Clemens Heuberger, Daniel Krenn | Commit:
Report Upstream: N/A | 70abf65739587016ed71a953585ff56af33e325b
Branch: | Stopgaps:
u/dkrenn/asy/prototype |
Dependencies: #17600, #17693, |
#17715, #17716, #18182, #18222, |
#18223, #18586, #18587, #18930, |
#19017, #19028, #19047, #19048, |
#19068, #19073, #19079, #19083, |
#19094, #19110 |
-------------------------------------+-------------------------------------
Changes (by dkrenn):
* commit: => 70abf65739587016ed71a953585ff56af33e325b
* branch: => u/dkrenn/asy/prototype
Old description:
> We intend to implement asymptotic expressions in Sage. We would like to
> do computations with simple expressions such as
>
> n^2^ + n^3/2^ + O(n^1/2^),
>
> but also with expressions such as
>
> 2^n^ * n + O(n*log(n))
>
> or even multivariate expressions 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 expressions. Eventually,
> specified O-constants shall also be supported.
>
> See #17716 for more examples.
> -------
>
> **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 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.
>
> * 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
>
> * Extending the functionality of the !AsymptoticRing and
> !AsymptoticExpression
> * #19068: Implement Division for asymptotic Expressions.
> * #19094: Implement higher-order operations like `exp` and `log` for
> asymptotic expressions.
> * #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
> * #19079: !ConstructionFunctor: remove `__str__`
> * #19083: !AsymptoticRing: cleanup, some improvements, documentation.
>
> * 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
> * 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`.
> * #18222: provide <=, <, >=, > for poset elements by the category
> (depends on #10130)
> * #19110: QQ(0)^-1 raises SIGFPE (which is caught)
New description:
We intend to implement asymptotic expressions in Sage. We would like to do
computations with simple expressions such as
n^2^ + n^3/2^ + O(n^1/2^),
but also with expressions such as
2^n^ * n + O(n*log(n))
or even multivariate expressions 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 expressions. Eventually,
specified O-constants shall also be supported.
-------
See #17716 and #19083 for more examples. A working prototype can be found
in branch u/dkrenn/asy/prototype (based on 6.9.beta5).
-------
**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 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.
* 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
* Extending the functionality of the !AsymptoticRing and
!AsymptoticExpression
* #19068: Implement Division for asymptotic Expressions.
* #19094: Implement higher-order operations like `exp` and `log` for
asymptotic expressions.
* #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
* #19079: !ConstructionFunctor: remove `__str__`
* #19083: !AsymptoticRing: cleanup, some improvements, documentation.
* 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
* 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`.
* #18222: provide <=, <, >=, > for poset elements by the category
(depends on #10130)
* #19110: QQ(0)^-1 raises SIGFPE (which is caught)
--
Comment:
Last 10 new commits:
||[http://git.sagemath.org/sage.git/commit/?id=47894c883674c7954e1d735a8fce602a6be3b0fa
47894c8]||{{{Merge branch 't/19094/asy/ring-exp-log' into
t/19083/asy/prototype}}}||
||[http://git.sagemath.org/sage.git/commit/?id=8894fce6d9a060a36b204255cd369938dab7ffdf
8894fce]||{{{Merge branch 't/17716/asy/asymptoticExpression' into
t/19068/asy/inversion}}}||
||[http://git.sagemath.org/sage.git/commit/?id=106eacd29856f115fe58e903d556cb4f65939773
106eacd]||{{{Merge branch 't/19068/asy/inversion' into
t/19083/asy/prototype}}}||
||[http://git.sagemath.org/sage.git/commit/?id=1108cfc6af6cf8049e3d818270bc321c7f16ec4b
1108cfc]||{{{Merge branch 't/17716/asy/asymptoticExpression' into
t/19048/asy/an_element}}}||
||[http://git.sagemath.org/sage.git/commit/?id=3c2fa0ca0749ddae121692e1556e6adef684e0f7
3c2fa0c]||{{{Merge branch 't/19048/asy/an_element' into
t/19083/asy/prototype}}}||
||[http://git.sagemath.org/sage.git/commit/?id=1812a5e458ec074907d0b43405415697c3ea1faa
1812a5e]||{{{rename doc-index-file}}}||
||[http://git.sagemath.org/sage.git/commit/?id=0720b14855eebe533acae7e82df47c1e0023ff52
0720b14]||{{{fix doctests: update since TestSuite now checks for
cardinality}}}||
||[http://git.sagemath.org/sage.git/commit/?id=14f9a9a4e74b0826ced00de326e0b043bfb7b146
14f9a9a]||{{{Merge branch 't/19094/asy/ring-exp-log' into
t/19083/asy/prototype}}}||
||[http://git.sagemath.org/sage.git/commit/?id=9aba4b6a3fae816bc02ec69161fb994a29755ee0
9aba4b6]||{{{make entry in reference/index}}}||
||[http://git.sagemath.org/sage.git/commit/?id=70abf65739587016ed71a953585ff56af33e325b
70abf65]||{{{include misc}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/17601#comment:35>
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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
