Opened 5 years ago
Last modified 3 years ago
#17601 new enhancement
Meta-Ticket: Asymptotic Expressions in Sage — at Version 17
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: | #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587 | Stopgaps: |
Description (last modified by )
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.
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
Change History (17)
comment:1 Changed 5 years ago by
- Dependencies set to 17600
comment:2 Changed 5 years ago by
- Dependencies changed from 17600 to #17600
comment:3 follow-up: ↓ 4 Changed 5 years ago by
comment:4 in reply to: ↑ 3 Changed 5 years ago by
comment:5 Changed 5 years ago by
- Cc ncohen added
comment:6 Changed 5 years ago by
- Dependencies changed from #17600 to #17600, #17693
- Description modified (diff)
comment:7 Changed 5 years ago by
- Cc vdelecroix added
comment:8 Changed 5 years ago by
- Dependencies changed from #17600, #17693 to #17600, #17693, #17715, #17716
- Description modified (diff)
comment:9 Changed 5 years ago by
- Cc malb added
comment:10 Changed 5 years ago by
- Cc mmezzarobba added
comment:11 Changed 5 years ago by
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?
comment:12 Changed 5 years ago by
- Cc rws added
- Milestone changed from sage-6.5 to sage-6.6
comment:13 follow-up: ↓ 14 Changed 5 years ago by
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
comment:14 in reply to: ↑ 13 Changed 5 years ago by
Replying to vdelecroix:
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).
comment:15 Changed 5 years ago by
- Cc kalvotom added
comment:16 Changed 5 years ago by
- Dependencies changed from #17600, #17693, #17715, #17716 to #17600, #17693, #17715, #17716, #18182, #18222, #18223
- Description modified (diff)
comment:17 Changed 5 years ago by
- Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587
- Description modified (diff)
#10519 might be of interest.