Opened 5 years ago
Last modified 3 years ago
#17601 new enhancement
Meta-Ticket: Asymptotic Expressions in Sage — at Version 25
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, #18930, #19017, #19028, #19047, #19048, #19068 | 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 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 AsymptoticExpression
- #19017: Easy access to the
O
-constructor inbig_oh.py
. - #19068: Implement Division for asymptotic Expressions.
- Implement higher-order operations like
exp
andlog
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.
- #19048:
AsymptoticRing.an_element()
- #19047:
QQ.some_elements()
- #19047:
- #19017: Easy access to the
- Extending the functionality of growth groups
- 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 ...)
Change History (25)
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)
comment:18 Changed 5 years ago by
- Description modified (diff)
- Keywords gsoc15 added
comment:19 Changed 5 years ago by
- Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930
- Description modified (diff)
comment:20 Changed 5 years ago by
- Description modified (diff)
comment:21 Changed 5 years ago by
- Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028
- Description modified (diff)
comment:22 Changed 5 years ago by
- Description modified (diff)
comment:23 Changed 5 years ago by
- Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048
- Description modified (diff)
comment:24 Changed 5 years ago by
- Description modified (diff)
comment:25 Changed 5 years ago by
- Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068
- Description modified (diff)
#10519 might be of interest.