Opened 6 years ago

Last modified 4 years ago

#17601 new enhancement

Meta ticket: Asymptotic Expansions in SageMath — at Version 49

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, Daniel Krenn Reviewers:
Report Upstream: N/A Work issues:
Branch: u/dkrenn/asy/prototype (Commits) Commit: 1109ce002874d776617102f2ccc295b410e4a3b6
Dependencies: #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094, #19110, #19259, #19269, #19300, #19305, #19306 Stopgaps:

Description (last modified by dkrenn)

We intend to implement asymptotic expansions in SageMath. We would like to do computations with simple expansions such as

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

but also with expansions such as

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

or even multivariate expansions 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 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. 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 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()
    • #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.
  • Further plans
    • for growth groups
      • implement dependencies like |k| <= n1/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
  • 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)
    • #19269: add category Posets to ZZ and QQ

Change History (49)

comment:1 Changed 6 years ago by behackl

  • Dependencies set to 17600

comment:2 Changed 6 years ago by behackl

  • Dependencies changed from 17600 to #17600

comment:3 follow-up: Changed 6 years ago by tscrim

#10519 might be of interest.

comment:4 in reply to: ↑ 3 Changed 6 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 6 years ago by ncohen

  • Cc ncohen added

comment:6 Changed 6 years ago by dkrenn

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

comment:7 Changed 6 years ago by vdelecroix

  • Cc vdelecroix added

comment:8 Changed 6 years ago by behackl

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

comment:9 Changed 6 years ago by malb

  • Cc malb added

comment:10 Changed 6 years ago by mmezzarobba

  • Cc mmezzarobba added

comment:11 Changed 6 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 6 years ago by rws

  • Cc rws added
  • Milestone changed from sage-6.5 to sage-6.6

comment:13 follow-up: Changed 6 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 6 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 6 years ago by kalvotom

  • Cc kalvotom added

comment:16 Changed 6 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 6 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)
  • Keywords gsoc15 added

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)

comment:24 Changed 5 years ago by dkrenn

  • Description modified (diff)

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

  • Description modified (diff)

comment:29 Changed 5 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 5 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)

comment:31 Changed 5 years ago by dkrenn

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

comment:32 Changed 5 years ago by dkrenn

  • Summary changed from Meta-Ticket: Asymptotic Expressions in Sage to Meta-Ticket: Asymptotic Expansions in SageMath

comment:33 Changed 5 years ago by dkrenn

  • Description modified (diff)

comment:34 Changed 5 years ago by dkrenn

  • Description modified (diff)

comment:35 Changed 5 years ago by dkrenn

  • Branch set to u/dkrenn/asy/prototype
  • Commit set to 70abf65739587016ed71a953585ff56af33e325b
  • Description modified (diff)

Last 10 new commits:

​47894c8Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype
​8894fceMerge branch 't/17716/asy/asymptoticExpression' into t/19068/asy/inversion
​106eacdMerge branch 't/19068/asy/inversion' into t/19083/asy/prototype
​1108cfcMerge branch 't/17716/asy/asymptoticExpression' into t/19048/asy/an_element
​3c2fa0cMerge branch 't/19048/asy/an_element' into t/19083/asy/prototype
​1812a5erename doc-index-file
​0720b14fix doctests: update since TestSuite now checks for cardinality
​14f9a9aMerge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype
​9aba4b6make entry in reference/index
​70abf65include misc

comment:36 Changed 5 years ago by dkrenn

  • Description modified (diff)

comment:37 Changed 5 years ago by dkrenn

  • Component changed from symbolics to asymptotic expansions

comment:38 Changed 5 years ago by git

  • Commit changed from 70abf65739587016ed71a953585ff56af33e325b to 2e4a415d7859d3968f612932b36c98318e1823d2

Branch pushed to git repo; I updated commit sha1. New commits:

​2e4a415rename title

comment:39 Changed 5 years ago by git

  • Commit changed from 2e4a415d7859d3968f612932b36c98318e1823d2 to b0e228b4870e49cfdc9594c5f85173bb889f6722

Branch pushed to git repo; I updated commit sha1. New commits:

​cd17673Merge tag '6.9.beta6' into t/18182/18182-on-6.8
​3eefe25correct typo in AUTHORS
​5fe52e4fix doctests since name of cartesian product functor has changed
​60b9375revert changes in base_ring of category_object and adapt doctests
​8d6de43Merge remote-tracking branch 'trac/u/dkrenn/18182/pushout' into t/19073/asy/groups-coercion
​d50cc55Merge branch 't/19073/asy/groups-coercion' into t/19094/asy/ring-exp-log
​44fbcccMerge remote-tracking branch 'origin/u/dkrenn/asy/ring-exp-log' into t/19094/asy/ring-exp-log
​09032eeMerge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype
​b0e228bMerge remote-tracking branch 'origin/u/dkrenn/asy/prototype' into t/19083/asy/prototype

comment:40 Changed 5 years ago by git

  • Commit changed from b0e228b4870e49cfdc9594c5f85173bb889f6722 to 1109ce002874d776617102f2ccc295b410e4a3b6

Branch pushed to git repo; I updated commit sha1. New commits:

​c16587cfix bug (tower has only one entry which is None)
​1109ce0Merge branch 'u/dkrenn/18182/pushout' of trac.sagemath.org:sage into t/19083/asy/prototype

comment:41 Changed 5 years ago by cheuberg

  • Authors changed from Benjamin Hackl, Clemens Heuberger, Daniel Krenn to Benjamin Hackl, Daniel Krenn
  • Milestone changed from sage-6.6 to sage-6.9

comment:42 Changed 5 years ago by dkrenn

  • Description modified (diff)
  • Summary changed from Meta-Ticket: Asymptotic Expansions in SageMath to Metaticket: Asymptotic Expansions in SageMath

comment:43 Changed 5 years ago by dkrenn

  • Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094, #19110 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094, #19110, #19259, #19269

comment:44 Changed 5 years ago by dkrenn

  • Description modified (diff)

comment:45 Changed 5 years ago by dkrenn

  • Description modified (diff)

comment:46 Changed 5 years ago by slelievre

  • Description modified (diff)

comment:47 Changed 5 years ago by cheuberg

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

comment:48 Changed 5 years ago by dkrenn

  • Dependencies changed from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094, #19110, #19259, #19269, #19300 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19094, #19110, #19259, #19269, #19300, #19305, #19306
  • Description modified (diff)
  • Summary changed from Metaticket: Asymptotic Expansions in SageMath to Meta ticket: Asymptotic Expansions in SageMath

comment:49 Changed 5 years ago by dkrenn

  • Description modified (diff)
Note: See TracTickets for help on using tickets.