Opened 5 years ago

Last modified 3 years ago

#17601 new enhancement

Meta-Ticket: Asymptotic Expressions in Sage — at Version 8

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 Stopgaps:

Description (last modified by behackl)

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.

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.

Change History (8)

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

#10519 might be of interest.

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

Replying to tscrim:

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