Opened 5 years ago

Last modified 3 years ago

#17601 new enhancement

Meta ticket: Asymptotic Expansions in SageMath — at Version 89

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: a848139a35e95bfd67d9964fa7412743942de4a4
Dependencies: #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510, #19521, #19532 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()
      • #19047: QQ.some_elements()
      • #19319: iterator over pairs on diagonals a la Cantor pairing
    • #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__
    • #19083: AsymptoticRing: exp, log, cleanup, some improvements, documentation.
      • contains #19094: Implement higher-order operations like exp and log for asymptotic expansions
    • #19400: move documentation to sage.asymptotic
  • Bugs and minor improvements
    • #19399: let category of growth group be determined by input
    • #19411: hidden but caught infinite loop in action of cartesian products of growth groups
    • #19412: log of an asymptotic expansion ignores coefficient ring
    • #19420: make log of growth elements to the base of some powers of elements possible
    • #19421: let asymptotic terms accept multivariate polynomials
    • #19423: AsymptoticExpansion: combine shared code of invert, log, exp
    • #19424: enable TestSuite for AsymptoticRing
    • #19426: AsymptoticRing: convert Orders of symbolic ring
      • #19425: Order in symbolic ring: error calling operator
    • #19429: extend conversion from SR to growth groups: allow inverses
    • #19431: convert asymptotic expansion to the symbolic ring
      • #19436: fixup of #19431
      • #19437: SR.symbol: correct parent in inherting classes of SymbolicRing
    • #19504: better implementation of AsymptoticExpansion.__hash__
  • Generators for asymptotic expansions
    • #19306: common generators for asymptotic expansions
      • #19259: subrings of the symbolic ring
    • #19510: generator for binomial(kn, n)
      • #19521: wrong inverse action when using ConstructionFunctor.coercion_reversed
    • #19532: generators related to singularity analysis
  • 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
      • #19316 compute asymptotic expansion to some rational directly
  • 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)
    • #19088: multi-line doctests fail when using angle notation (preparser)
    • #19269: add category Posets to ZZ and QQ

Change History (89)

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 ; follow-up: 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)

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

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

comment:33 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:34 Changed 4 years ago by dkrenn

  • Description modified (diff)

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

  • Description modified (diff)

comment:37 Changed 4 years ago by dkrenn

  • Component changed from symbolics to asymptotic expansions

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

  • Description modified (diff)

comment:45 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:46 Changed 4 years ago by slelievre

  • Description modified (diff)

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

  • Description modified (diff)

comment:50 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, #19083, #19094, #19110, #19259, #19269, #19300, #19305, #19306 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, #19316
  • Description modified (diff)

comment:51 Changed 4 years ago by git

  • Commit changed from 1109ce002874d776617102f2ccc295b410e4a3b6 to 3ca2e9179d3bf8ad5a72df9b9b7a69cf25a0adb0

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​6d3e4f4Trac #18587: nicer output of one link target
​66759bbRevert "remove unreachable ValueError (comment 2)"
​0642564doctest added
​7f209eaimproved error message (equal or disjoint var.)
​c49740aMerge branch 'u/behackl/asy/growth-group-cartesian' of trac.sagemath.org:sage into t/19094/asy/ring-exp-log
​4fe08b7rewrite a doctest to make it work (and mark original test as 'not tested')
​4acd110Merge branch 'u/dkrenn/asy/ring-exp-log' of trac.sagemath.org:sage into t/19083/asy/prototype
​45d0c03post-merge: fix imports
​f62f7cfpost-merge: fix doctests
​3ca2e91fix broken links

comment:52 Changed 4 years ago by git

  • Commit changed from 3ca2e9179d3bf8ad5a72df9b9b7a69cf25a0adb0 to 7f4272375d6de89bbe7fe5457c11d9165d4622ff

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

​03f3621fix duplicated docstring-parts
​7f42723update AUTHORS (new style)

comment:53 Changed 4 years ago by git

  • Commit changed from 7f4272375d6de89bbe7fe5457c11d9165d4622ff to ff90d7351b6d8c96c7ee077dcc6d0fd7e7cf98df

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​65ce848Merge branch 'asy/growth-group-cartesian' into asy/growthGroup-exponential and resolve merge conflicts
​bd93e37fix doctests
​7ec7e7dfix indentation of one block
​e56459a: --> ::
​0d469cdMerge branch 'u/behackl/asy/growthGroup-exponential' of trac.sagemath.org:sage into t/19073/asy/groups-coercion
​e86db32Merge branch 'u/dkrenn/asy/asymptoticExpression' of trac.sagemath.org:sage into t/19073/asy/groups-coercion
​36e16a3fix doctests after merge
​dd82094fix duplicated docstring-parts
​ae300adMerge branch 't/19073/asy/groups-coercion' into t/19094/asy/ring-exp-log
​ff90d73Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype

comment:54 Changed 4 years ago by git

  • Commit changed from ff90d7351b6d8c96c7ee077dcc6d0fd7e7cf98df to c4cd7ed152db8651e0af80951dfe45ed598e4399

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​e8460b9improve docstring
​9e41be5doctest with infinite iterator inputs
​97cb59cadd seealso blocks
​17229c6extend AUTHROS
​e33703bMerge branch 'u/dkrenn/product_cantor_pairing' of trac.sagemath.org:sage into t/19048/asy/an_element
​a529d4cMerge branch 'u/dkrenn/asy/an_element' of trac.sagemath.org:sage into t/19094/asy/ring-exp-log
​ba99790use new product_cantor_pairing and delete old product_diagonal
​4a9d3d2Merge branch 'u/dkrenn/asy/an_element' of trac.sagemath.org:sage into t/19094/asy/ring-exp-log
​8204cfaremove old product_diagonal (superseded by #19319)
​c4cd7edMerge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype

comment:55 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, #19083, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316 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, #19316, #19319
  • Description modified (diff)

Last 10 new commits:

​e8460b9improve docstring
​9e41be5doctest with infinite iterator inputs
​97cb59cadd seealso blocks
​17229c6extend AUTHROS
​e33703bMerge branch 'u/dkrenn/product_cantor_pairing' of trac.sagemath.org:sage into t/19048/asy/an_element
​a529d4cMerge branch 'u/dkrenn/asy/an_element' of trac.sagemath.org:sage into t/19094/asy/ring-exp-log
​ba99790use new product_cantor_pairing and delete old product_diagonal
​4a9d3d2Merge branch 'u/dkrenn/asy/an_element' of trac.sagemath.org:sage into t/19094/asy/ring-exp-log
​8204cfaremove old product_diagonal (superseded by #19319)
​c4cd7edMerge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype

comment:56 Changed 4 years ago by git

  • Commit changed from c4cd7ed152db8651e0af80951dfe45ed598e4399 to 14941885df88ebdb20555268f193367e741fddb3

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

​88f0013adapt Trac #19073, comment 20, 1: add missing INPUT/OUTPUT block of combine_exceptions
​6659ceeadapt Trac #19073, comment 20, 4: missing INPUT/OUTPUT block of merge_overlapping and extend description
​2008f6badapt Trac #19073, comment 20, 4: cache keys
​1494188adapt Trac #19073, comment 20, 7: remove Poset category from AsymptoticRing

comment:57 Changed 4 years ago by git

  • Commit changed from 14941885df88ebdb20555268f193367e741fddb3 to 60b93ab17ef80750fbd053c2219d9bd84fe22bc9

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​4a52a84Trac 19319: fix doctests
​3c5af3bTrac #19319: fix typo
​c20bfe5Trac #19319: a.next() -> next(a) (Python3 compliance)
​1fee722Trac #19319: added a few blanks
​96c0366Trac 19319: return tuples + repeat argument
​ceb1db5Trac #19048: Merge #19319
​3fd53d6Trac #19048: rename product_cantor_pairing to cantor_product (see #19319)
​617c593Trac #19048: Fix doctests (order in cantor_product changed)
​9213baaMerge branch 'u/cheuberg/asy/an_element' of trac.sagemath.org:sage into t/19094/asy/ring-exp-log
​60b93abMerge branch 'u/dkrenn/asy/ring-exp-log' of trac.sagemath.org:sage into t/19083/asy/prototype

comment:58 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, #19083, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319
  • Description modified (diff)

comment:59 Changed 4 years ago by git

  • Commit changed from 60b93ab17ef80750fbd053c2219d9bd84fe22bc9 to 2cba56bd14842af761cd4eb7eb1fb56a50424724

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

​a33daf9changes part 1 after comments of cheuberg
​2cba56brewrite informal description of growth elements and explain description strings

comment:60 Changed 4 years ago by git

  • Commit changed from 2cba56bd14842af761cd4eb7eb1fb56a50424724 to a39204c67440a804066b1877937cccdca7593e92

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

​2a80346Trac #19073: simplify signatures of helper functions in merge_overlapping
​1583ffcTrac #19073: Reword and add doctest for _pushout_
​8a32f1fcorrect PEP8-spacings in doctest
​05862f4Merge branch 't/19073/asy/groups-coercion' into t/19094/asy/ring-exp-log
​b160261forgotten changes of last merge
​d0c0f15Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype
​a39204cchanges part 2 (of 2) after comments of cheuberg

comment:61 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399
  • Description modified (diff)

comment:62 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400
  • Description modified (diff)

comment:63 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412
  • Description modified (diff)

comment:64 Changed 4 years ago by git

  • Commit changed from a39204c67440a804066b1877937cccdca7593e92 to e8ad893715b0dfc8a3907a05382b0c1cba57b818

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​0ca6efdTrac #19094/#19083 comment 60, 11: correct wrong log and give log in errors a base
​71802daTrac #19094/#19083 comment 60, 8: rename to _create_element_in_extension_
​e2285e7Trac #19094/#19083 comment 60, 8: rewrite description of _create_element_in_extension_
​4cb775fTrac #19094/#19083 comment 60, 12: add doctest in _rpow_element to test parameter base
​51f796cTrac #19094/#19083 comment 60, 12: document _rpow_element 2^x
​2f110dbTrac #19094/#19083 comment 60, 13: simplify ExponentialGrowthElement._repr_
​4c49d02Trac #19094/#19083 comment 60, 14: rewrite keyword arguments documentation of GrowthGroupFactory
​d2cc73aadd forgotten "EXAMPLES::" line
​498dbadTrac #19094/#19083 comment 60, 15: add a doctest to GenericProduct._create_element_via_parent_
​e8ad893Trac #19094/#19083 comment 60, 16: delte misplaced statement in docstring

comment:65 Changed 4 years ago by cheuberg

  • Description modified (diff)

comment:66 Changed 4 years ago by git

  • Commit changed from e8ad893715b0dfc8a3907a05382b0c1cba57b818 to b66497d7e1dfe12d486b0c50bef65547f28ed44f

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​c5dadf7Trac #19083: More interesting doctest by including a coefficient
​e2a0c6eTrac #19083: minor language issues
​ac9d4bcTrac #19083: ReSt errors
​b6ac6c1Trac #19083: abbreviate link
​b85176aTrac #19083: break long lines
​6b45b79Trac #19083: mark one doctest as indirect
​0481cdaTrac #19083: simplify doctest
​5867787Trac #19083: o(1) instead of O(1) for use of taylor series
​2c60570Trac #19083: additional doctest and explanation
​b66497dMerge remote-tracking branch 'origin/u/cheuberg/asy/prototype' into t/19083/asy/prototype

comment:67 Changed 4 years ago by git

  • Commit changed from b66497d7e1dfe12d486b0c50bef65547f28ed44f to 3fdb4dcee28c67dd076a6552580c8ab15811924a

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​cacd890Trac #19094/#19083 comment 64, 28: test error in OTermMonoid._create_element_
​5219671Trac #19094/#19083 comment 64, 29: fix broken link
​d4a447fTrac #19094/#19083 comment 64, 29: TermWithCoefficient._calculate_pow_: test ArithemticError
​086b62dTrac #19094/#19083 comment 64, 30: TermMonoidFactory: note block to refer to instance TermMonoid
​7647952write docstrings for the factory instances
​7e4e823Trac #19094/#19083 comment 64, 30: more doctests in TermMonoidFactory
​8f57fa1Trac #19083: Insert external link
​6c00163Trac #19083: minor language issues
​51f699dTrac #19083: fix dead link by explicitly naming GenericGrowthElement
​3fdb4dcMerge branch 'u/cheuberg/asy/prototype' of trac.sagemath.org:sage into t/19083/asy/prototype

comment:68 Changed 4 years ago by git

  • Commit changed from 3fdb4dcee28c67dd076a6552580c8ab15811924a to d582c1345a788d5b8eba1b5d6e0734378f4559c4

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

​728ccf9Trac #19094/#19083 comment 66, 30: document parameter convert
​a7f7fafTrac #19094/#19083 comment 66, 31: test parameter convert
​7a27e68Trac #19094/#19083 comment 66, 31: Doctest error
​ad645aaTrac #19094/#19083 comment 66, 32: change simplification check to "not exact term"
​d582c13Trac #19094/#19083 comment 66, 29: rename coefficient to new_coefficent (_calculate_pow_)

comment:69 Changed 4 years ago by git

  • Commit changed from d582c1345a788d5b8eba1b5d6e0734378f4559c4 to 44b52d61e4c1e3229ee8f3ae7c2c375a67bbc247

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​7ca2b7fTrac #19094/#19083 comment 66, 33: test errors in __invert__
​12e8e52Trac #19094/#19083 comment 66, 34: not tested in __pow__: refer to #19316
​0845655Trac #19094/#19083 comment 66, 34: __pow__ add error tests
​3fe96bfsort maximal elements in error string
​5ca69eaTrac #19094/#19083 comment 66, 35: doctest errors of log
​cb55faaTrac #19094/#19083 comment 66, 35: improve speed of log
​d925157Trac #19094/#19083 comment 66, 36: rpow: decrease indention of ALGORITHM block
​57eb7ccTrac #19083: Mention "GrowthGroup" in docstring of "GrowthGroupFactory"
​0042756Trac #19083: added doctest (comment 64.23)
​44b52d6Merge branch 'u/cheuberg/asy/prototype' of trac.sagemath.org:sage into t/19083/asy/prototype

comment:70 Changed 4 years ago by git

  • Commit changed from 44b52d61e4c1e3229ee8f3ae7c2c375a67bbc247 to 80068372f79a2e804be5c864b51bac9a1c75498a

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

​2522bd0Trac #19094/#19083 comment 66, 36: add error test
​8cbacdfTrac #19094/#19083 comment 66, 37: refer to #19424 in not tested doctest
​ec10395Trac #19094/#19083 comment 66, 39: extend description of old_parent (in
​36a48e4Trac #19094/#19083 comment 66, 39: _create_element_in_extension_ rewrite doctests and rename parameter to old_term_parent
​38a597bTrac #19094/#19083 comment 66, 40: remove outdated NOTE block
​b927671Trac #19094/#19083 comment 66, 40: complete doctests of AsymptoticRing._element_constructor_
​7624627Trac #19094/#19083 comment 66, 40: refer to trac tickets at O-Term from SR todo
​1ceba10Trac #19094/#19083 comment 66, 40: test conversion from multivariate polynomial ring
​8006837Trac #19094/#19083 comment 66, 40: simplify test for empty data

comment:71 Changed 4 years ago by git

  • Commit changed from 80068372f79a2e804be5c864b51bac9a1c75498a to a848139a35e95bfd67d9964fa7412743942de4a4

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

​4e5af11Trac #19094/#19083 comment 66, 36: delete ALGORITHM block
​cb083d4Trac #19094/#19083 comment 66, 41: delete _create_exact_summands_ since not needed
​cf228bbTrac #19094/#19083 comment 66, 42: make creating of exact summand with growth but without coefficient impossible
​a848139Trac #19094/#19083 comment 66, 42: create_summands: add doctests for interesting `data`

comment:72 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:73 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:74 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426

comment:75 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429
  • Description modified (diff)

comment:76 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431
  • Description modified (diff)

comment:77 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:78 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436

comment:79 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437
  • Description modified (diff)

comment:80 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:81 Changed 4 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, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504
  • Description modified (diff)
  • Milestone changed from sage-6.9 to sage-6.10

comment:82 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:83 in reply to: ↑ 14 Changed 4 years ago by nbruin

Replying to cheuberg:

I rather think of it as a version of the PowerSeriesRing with additional features (non-integer exponents, several (not completely independent) variables).

Yes, and you could get a lot of leverage out of making that link more prominent. In fact, the appropriate concept would be "Puiseux series", which are Laurent series (with negative exponents allowed) in fractional powers of your variables.

For asymptotic expansions you have x+O(x(1/2)) = O(x(1/2)), which is consistent with Puiseux series in t=1/x.

The usual implementation for Puiseux series is as

[d,N,a[N],a[N+1],a[N+2],...,finite number of terms]

meaning

sum_{i=N..} a_i* x(i/d)

For arithmetic you just first bring series in common denominator "d" and then do power series arithmetic.

For multivariate series, the appropriate behaviour is caught by "local term orders". SingularLib might offer some useful things already.

Note that a series in n and log(n) can be treated as a bivariate series, with an appropriate term order on the variables signifying "n" and "log(n)", for asymptotic series probably again modelling these with X=1/n and Y= 1/log(n).

So I think this ticket can be realized by implementing "multivariate puiseux series", which would be useful in a lot of settings. It would be better if (the underlying ring) would also be called "multivariate puiseux series ring" because that would improve discoverability.

Searching the literature for these terms will probably also make it easier to find relevant algorithms.

Last edited 4 years ago by vdelecroix (previous) (diff)

comment:84 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510
  • Description modified (diff)

comment:85 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:86 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510, #19521

comment:87 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510, #19521 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510, #19521, #19528
  • Description modified (diff)

comment:88 Changed 4 years ago by dkrenn

  • Description modified (diff)

comment:89 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, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510, #19521, #19528 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028, #19047, #19048, #19068, #19073, #19079, #19083, #19088, #19094, #19110, #19259, #19269, #19300, #19305, #19306, #19316, #19319, #19399, #19400, #19411, #19412, #19420, #19421, #19423, #19424, #19425, #19426, #19429, #19431, #19436, #19437, #19504, #19510, #19521, #19532
  • Description modified (diff)
Note: See TracTickets for help on using tickets.