#17601: Meta-Ticket: Asymptotic Expressions in Sage
-------------------------------------------------+-------------------------
Reporter: behackl | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.6
Component: symbolics | Resolution:
Keywords: asymptotics, gsoc15 | Merged in:
Authors: Benjamin Hackl, Clemens | Reviewers:
Heuberger, Daniel Krenn | Work issues:
Report Upstream: N/A | Commit:
Branch: | Stopgaps:
Dependencies: #17600, #17693, #17715, |
#17716, #18182, #18222, #18223, #18586, |
#18587, #18930, #19017, #19028 |
-------------------------------------------------+-------------------------
Changes (by behackl):
* dependencies:
#17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586,
#18587, #18930
=>
#17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586,
#18587, #18930, #19017, #19028
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.
>
> 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^2^ 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.
>
> -------
>
> **Roadmap**:
>
> * 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.
>
> * 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.
> * Improve the performance of computations in the !AsymptoticRing.
>
> * 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^1/2^ 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)
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.
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^2^ 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.
-------
**Roadmap**:
* 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.
* 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.
* Implement comparison for asymptotic expressions.
* Improve the performance of computations in the !AsymptoticRing.
* 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^1/2^ 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)
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17601#comment:21>
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.
