Opened 5 years ago
Last modified 3 years ago
#17601 new enhancement
Meta-Ticket: Asymptotic Expressions in Sage — at Initial Version
Reported by: | behackl | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.4 |
Component: | asymptotic expansions | Keywords: | asymptotics, gsoc15 |
Cc: | dkrenn, cheuberg, ncohen, vdelecroix, malb, mmezzarobba, rws, kalvotom | Merged in: | |
Authors: | Benjamin Hackl, Clemens Heuberger, Daniel Krenn | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
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.
In #17600, we start with AsymptoticGrowthElement.