id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
17601 Meta ticket: Asymptotic Expansions in SageMath behackl "We intend to implement asymptotic expansions in !SageMath. We would like to do computations with simple expansions such as
n^2^ + n^3/2^ + O(n^1/2^),
but also with expansions such as
2^n^ * n + O(n*log(n))
or even multivariate expansions 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 expansions. Eventually, specified O-constants shall also be supported.
-------
See #17716 and #19083 for more examples and the documentation files there for a more detailed description. A working prototype can be found in branch `u/dkrenn/asy/prototype`.
-------
**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 expansions. 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 expansions.
* #17716 (!AsymptoticRing and !AsymptoticExpansion): sum of asymptotic terms.
* Extending the functionality of growth groups
* #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expansions)
* #18223: cartesian products with orders
* #18586: passing on parameters and extra_category for cartesian products
* #19028: More growth group implementations: exponential growth groups.
* Extending the functionality of the !AsymptoticRing and !AsymptoticExpansion
* #19048: `AsymptoticRing.an_element()`
* #19047: `QQ.some_elements()`
* #19319: iterator over pairs on diagonals a la Cantor pairing
* #19068: Implement Division for asymptotic expansions.
* #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__`
* #19094: Implement higher-order operations like `exp` and `log` for asymptotic expansions.
* #19083: !AsymptoticRing: cleanup, some improvements, documentation.
* #19400: move code to sage.asymptotic
* Bugs and minor improvements
* #19399: let category of growth group be determined by input
* #19411: hidden but caught infinite loop in action of cartesian products of growth groups
* #19412: log of an asymptotic expansion ignores coefficient ring
* 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 expansions.
* 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 ...)
* #19300: Run benchmarks on `MutablePoset.remove` to decide between two algorithms.
* #19305: substitution of asymptotic expansions
* #19306: common generators for asymptotic expansions
* #19259: subrings of the symbolic ring
* #19316 compute asymptotic expansion to some rational directly
* Additional dependencies
* #19017: Easy access to the `O`-constructor in `big_oh.py`.
* #19110: QQ(0)^-1^ raises SIGFPE (which is caught)
* Other related Tickets:
* #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
* #19088 multi-line doctests fail when using angle notation (preparser)
* #19269: add category Posets to ZZ and QQ
" enhancement new major sage-6.9 asymptotic expansions asymptotics, gsoc15 dkrenn cheuberg ncohen vdelecroix malb mmezzarobba rws kalvotom Benjamin Hackl, Daniel Krenn N/A u/dkrenn/asy/prototype a39204c67440a804066b1877937cccdca7593e92 #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412