Opened 5 years ago

Last modified 3 years ago

#17601 new enhancement

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

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, #19073, #19079, #19083, #19094 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 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. 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()
    • #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 ...)
  • Additional Dependencies:
    • #18222: provide <=, <, >=, > for poset elements by the category (depends on #10130)

Change History (30)

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)

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

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