Opened 5 years ago

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

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, #19068, #19073, #19079, #19083, #19094

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 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.

• Implementing a minimal working example
• #17600 (AsymptoticGrowthElement): elements which handle the asymptotic growth. Such an element holds, e.g. n2 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 the AsymptoticRing and AsymptoticExpression
• #19017: Easy access to the `O`-constructor in `big_oh.py`.
• #19068: Implement Division for asymptotic Expressions.
• #19094: 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()`
• #19047: `QQ.some_elements()`
• #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__`
• #19083: AsymptoticRing: cleanup, some improvements, documentation.
• 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 ...)
• #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)

### 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:5 Changed 5 years ago by ncohen

• Cc ncohen added

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

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

### comment:7 Changed 5 years ago by vdelecroix

• Cc vdelecroix added

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

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

### comment:9 Changed 5 years ago by malb

• Cc malb added

### comment:10 Changed 5 years ago by mmezzarobba

• Cc mmezzarobba added

### 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

• Cc rws added
• 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:15 Changed 5 years ago by kalvotom

• Cc kalvotom added

### 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 4 years ago by behackl

• Description modified (diff)
• Keywords gsoc15 added

### comment:19 Changed 4 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 4 years ago by behackl

• Description modified (diff)

### comment:21 Changed 4 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 4 years ago by dkrenn

• Description modified (diff)

### comment:23 Changed 4 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)

### comment:24 Changed 4 years ago by dkrenn

• Description modified (diff)

### comment:25 Changed 4 years ago by behackl

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

### comment:26 Changed 4 years ago by dkrenn

• Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073
• Description modified (diff)

### comment:27 Changed 4 years ago by dkrenn

• Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079
• Description modified (diff)

### comment:28 Changed 4 years ago by dkrenn

• Description modified (diff)

### comment:29 Changed 4 years ago by dkrenn

• Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083
• Description modified (diff)

### comment:30 Changed 4 years ago by behackl

• Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094
• Description modified (diff)
Note: See TracTickets for help on using tickets.