Opened 5 years ago

# Meta-Ticket: Asymptotic Expressions in Sage — at Version 23

Reported by: Owned by: behackl major sage-7.4 asymptotic expansions asymptotics, gsoc15 dkrenn, cheuberg, ncohen, vdelecroix, malb, mmezzarobba, rws, kalvotom Benjamin Hackl, Clemens Heuberger, Daniel Krenn N/A #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048

We intend to implement asymptotic expressions in Sage. We would like to do computations with simple expressions such as

n2 + n3/2 + O(n1/2),

but also with expressions such as

2n * n + O(n*log(n))

or even multivariate expressions such as

3*k/n + O(k2 / n2) 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. n2 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.

• 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 (AsymptoticRing and 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.
• #19048: `AsymptoticRing.an_element()`
• 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| <= n1/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 ...)
• #18182: pushout construction and finding common parents for/including cartesian products
• #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)
• #19047: `QQ.some_elements()`

### comment:1 Changed 5 years ago by behackl

• Dependencies set to 17600

### comment:2 Changed 5 years ago by behackl

• Dependencies changed from 17600 to #17600

### comment:3 follow-up: ↓ 4 Changed 5 years ago by tscrim

#10519 might be of interest.

### comment:4 in reply to: ↑ 3 Changed 5 years ago by dkrenn

#10519 might be of interest.

Thanks---I'm involved in both tickets ;)

At the moment both are independent, but when the asymptotic expressions are created, one can use them in the calculations (or at least as a possible output format) in #10519.

### comment:6 Changed 5 years ago by dkrenn

• Dependencies changed from #17600 to #17600, #17693
• Description modified (diff)

### comment:8 Changed 5 years ago by behackl

• Dependencies changed from #17600, #17693 to #17600, #17693, #17715, #17716
• Description modified (diff)

### comment:11 Changed 5 years ago by fredrik.johansson

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 rws

• Milestone changed from sage-6.5 to sage-6.6

### comment:13 follow-up: ↓ 14 Changed 5 years ago by vdelecroix

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 cheuberg

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:16 Changed 5 years ago by dkrenn

• 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 dkrenn

• 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 behackl

• Description modified (diff)

### comment:19 Changed 5 years ago by behackl

• 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 behackl

• Description modified (diff)

### comment:21 Changed 5 years ago by behackl

• 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 dkrenn

• Description modified (diff)

### comment:23 Changed 5 years ago by dkrenn

• 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)
Note: See TracTickets for help on using tickets.