Meta ticket: Asymptotic Expansions in SageMath

[behackl]

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

n² + n^3/2 + O(n^1/2),

but also with expansions such as

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

or even multivariate expansions such as

3*k/n + O(k² / n²) 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 the documentation files for a more examples and a detailed description. A working prototype is include in SageMath 6.10 and a version
containing all features can be found in branch public/asy/trunk.

---

Roadmap:

• Implementing a minimal working example

  • AsymptoticGrowthElement #17600 (AsymptoticGrowthElement): elements which handle the asymptotic growth. Such an element holds, e.g. n² 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.
  • GrowthGroup: short notation factory #18930: Factory for user-friendly generation of growth groups
  • AsymptoticTerm #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).
  • mutable poset: a data structure for asymptotic expressions #17693 (MutablePoset): data structure for storing asymptotic terms within an asymptotic expansions.
  • AsymptoticRing and AsymptoticExpression #17716 (AsymptoticRing and AsymptoticExpansion): sum of asymptotic terms.

• Extending the functionality of growth groups

  • cartesian products of growth groups #18587: cartesian products for growth groups (allowing the construction of more complicated univariate as well as multivariate asymptotic expansions)
    • cartesian products with orders #18223: cartesian products with orders
    • passing on parameters and extra_category for cartesian products #18586: passing on parameters and extra_category for cartesian products
  • ExponentialGrowthGroup #19028: More growth group implementations: exponential growth groups.

• Extending the functionality of the AsymptoticRing and AsymptoticExpansion

  • AsymptoticRing: an_element #19048: AsymptoticRing.an_element()
    • let QQ.some_elements return more than one element #19047: QQ.some_elements()
    • iterator over products on diagonals a la Cantor #19319: iterator over pairs on diagonals a la Cantor pairing
  • AsymptoticRing: inversion #19068: Implement Division for asymptotic expansions.
  • categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups #19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups
    • pushout construction and finding common parents for/including cartesian products #18182: pushout construction and finding common parents for/including cartesian products
    • ConstructionFunctor: remove __str__ #19079: ConstructionFunctor: remove __str__
  • AsymptoticRing: exp & log, cleanup, some improvements, documentation #19083: AsymptoticRing: exp, log, cleanup, some improvements, documentation.
    • contains exp & log for the AsymptoticRing #19094: Implement higher-order operations like exp and log for asymptotic expansions
  • move documentation of asymptotic expansion to sage.asymptotic #19400: move documentation to sage.asymptotic

• Additional dependencies

  • improving the big_oh interface + passing keywords #19017: Easy access to the O-constructor in big_oh.py.
  • QQ(0)^-1 raises SIGFPE (which is caught) #19110: QQ(0)^-1 raises SIGFPE (which is caught)

• We have a working prototype (made of the tickets above).

• Arithmetic, categories and coercion (bugs and improvements)

  • let category of growth group be determined by input #19399: let category of growth group be determined by input
  • compute asymptotic expansion to some rational directly #19316: compute asymptotic expansion to some rational directly
  • hidden but caught infinite loop in action of cartesian products of growth groups #19411: hidden but caught infinite loop in action of cartesian products of growth groups
  • log of an asymptotic expansion ignores coefficient ring #19412: log of an asymptotic expansion ignores coefficient ring
  • make log of growth elements to the base of some powers of elements possible #19420: make log of growth elements to the base of some powers of elements possible
  • AsymptoticExpansion: combine shared code of invert, log, exp #19423: AsymptoticExpansion: combine shared code of invert, log, exp
  • performance improvement of mutable poset used for univariate asymptotic expansions #19577: performance improvement of mutable poset used for univariate asymptotic expansions
  • sqrt of AsymptoticExpansion #20000: sqrt of AsymptoticExpansion
  • AsymptoticRing: multiplication with zero fails #20043: multiplication with zero fails
  • calculate asymptotic expansions to some asymptotic expansions exponents directly #20044: calculate asymptotic expansions to some asymptotic expansions exponents directly
  • AsymptoticRing.substitute fails with exponents in QQbar #21665: AsymptoticRing.substitute fails with exponents in QQbar
  • AsymptoticRing default_prec lost with coercion #22396: AsymptoticRing default_prec lost with coercion
  • check for subs of AsymptoticExpansion #22414: check for subs of AsymptoticExpansion

• Conversion (bugs and improvements)

  • let asymptotic terms accept multivariate polynomials #19421: let asymptotic terms accept multivariate polynomials
  • AsymptoticRing: convert Orders of symbolic ring #19426: AsymptoticRing: convert Orders of symbolic ring
    • Order in symbolic ring: error calling operator #19425: Order in symbolic ring: error calling operator
  • extend conversion from SR to growth groups: allow inverses #19429: extend conversion from SR to growth groups: allow inverses
  • convert asymptotic expansion to the symbolic ring #19431: convert asymptotic expansion to the symbolic ring
    • fixup of 19431: convert asymptotic expansion to the symbolic ring #19436: fixup of convert asymptotic expansion to the symbolic ring #19431
    • SR.symbol: correct parent in inherting classes of SymbolicRing #19437: SR.symbol: correct parent in inherting classes of SymbolicRing
  • Handle zero coefficients when converting asymptotic rings #19921: handle zero coefficients when converting asymptotic rings
  • Fix Rational.__pow__ #19945: Asymptotic Ring: cannot construct (1/2)^n
  • Asymptotic Ring: cannot construct 2^n when coefficient ring is SR #19946: Asymptotic Ring: cannot construct 2ⁿ when coefficient ring is SR
    • mention rpow of asymptotic ring in module doc/examples more prominently #19961: mention rpow of asymptotic ring in module doc/examples more prominently
    • parent of exponent getting too large in exponentiation in asymptotic ring #19965: parent of exponent getting too large in exponentiation in asymptotic ring
  • conversion SR to asymptotic ring #19947: conversion SR to asymptotic ring

• Other bugs and minor improvements

  • MutablePoset.remove: compare algorithms #19300: Run benchmarks on MutablePoset.remove to decide between two algorithms.
  • enable TestSuite for AsymptoticRing #19424: enable TestSuite for AsymptoticRing
  • AsymptoticExpansion: Implement sensible __hash__ function #19504: better implementation of AsymptoticExpansion.__hash__
  • parentheses around coefficients of asymptotic expansions #19576: parentheses around coefficients of asymptotic expansions
  • use locals() in growth group factory #19580: use locals() in growth group factory
  • is_exact for asymptotic ring #19981: implementation of is_exact for asymptotic expansions
  • LaTeX representation of asymptotic expansions #19987: LaTeX-representation of asymptotic expansions
  • Exponential growth group: q^x and (-q)^x are incomparable #19999: infinite recursion creating certain asymptotic expansion
  • move wrongly imported series_precision in AsymptoticRing #20045: move wrongly imported series_precision in AsymptoticRing
  • remove "import sage" from sage.rings.asymptotic.* #22140: remove "import sage" from sage.rings.asymptotic.*
  • Coefficient of an AsymptoticExpansion #22340: coefficient of an AsymptoticExpansion
  • ordering of (O-)terms: absolute values, real parts, etc. #22395: ordering of (O-)terms: absolute values, real parts, etc.
  • remove experimental warning of asymptotic ring #22944: remove experimental warning of asymptotic ring

• Generators for asymptotic expansions

  • common generators for asymptotic expansions #19306: common generators for asymptotic expansions
    • subrings of the symbolic ring #19259: subrings of the symbolic ring
  • asymptotic expansion generator for binomial(kn, n) #19510: generator for binomial(kn, n)
    • wrong inverse action when using ConstructionFunctor.coercion_reversed #19521: wrong inverse action when using ConstructionFunctor.coercion_reversed
  • AsymptoticExpansion: Generator for expansion of harmonic number #19898: generator for expansion of harmonic number

• Singularity analysis

  • asymptotic expansion generators related to singularity analysis #19532: generators related to singularity analysis
  • asymptotic expansion generator: singularity analysis (log-type) #19969: enhancement of SA-generators: log-type singularities
    • Arb: parse symbolic expressions #19993: Arb: parse symbolic expressions
  • asymptotic expansions: singularity analysis #19944: singularity analysis
  • asymptotic expansion generator: singularity analysis (log-type) without renormalization #20020: singularity analysis (log-type) without renormalization
  • Singularity analysis method for log-type singularities #20040: singularity analysis method for log-type singularities
  • singularity in formula in docstring of SingularityAnalysis-generator #20049: singularity in formula in docstring of SingularityAnalysis-generator
  • Rename AsymptoticRing.singularity_analysis to coefficients_of_generating_function #20056: rename AsymptoticRing.singularity_analysis to coefficients_of_generating_function
  • Singularity analysis: fix and speed up singularity analysis (log-type) without renormalization #20051: speed up singularity analysis (log-type) without renormalization
  • Singularity analysis: allow symbolic expressions #20052: allow symbolic expressions
  • Singularity analysis for given singular expansions #20053: allow singular expansions as input
  • Singularity analysis: Intelligent choice of precision #20054: intelligent choice of precision
  • Singularity analysis: non-integral exponents beta also outside of generators #20055: non-integral exponents beta also outside of generators
  • AsymptoticRing.coefficients_of_generating_function: hardcoded exponents in QQ #21659: coefficients_of_generating_function: hardcoded exponents in QQ
  • singularity analysis: raise proper OZero-exception (instead of AttributeError) #22360: raise proper !OZero-exception (instead of AttributeError)

• More features

  • substitution of asymptotic expansions #19305: substitution of asymptotic expansions
  • map_coefficients for asymptotic expansions #19528: map_coefficients for asymptotic expansions
  • exact_part for asymptotic expansions #19931: exact_part for asymptotic expansions
  • AsymptoticExpansion.factorial #19540: factorial
  • Asymptotic ring: list plot comparing values #19957: list plot comparing values

• Further plans

  • for growth groups
    • implement dependencies like |k| <= n^1/2 for different growth group variables.
    • Asymptotic: growth groups with asymptotic at a non-infinity point #20050: growth groups with asymptotic at a non-infinity point
      • MultivariatePuiseuxSeriesRing
  • other
    • Deal with comparison for asymptotic expansions.
    • Check and improve the performance of computations in the AsymptoticRing.
      • Asymptotic Expansions: adaptive precision #20065: Asymptotic Expansions: adaptive precision
    • Implementation of more types of asymptotic terms (little-oh terms, omega-terms, variations of big-Oh terms ...)

• Other related tickets:

  • analytic combinatorics: new code for computing asymptotics for multivariate generating functions #10519: analytic combinatorics: new code for computing asymptotics for multivariate generating functions
    • asymptotics for multivariate generating functions: zero division error on last coordinate #19989: asymptotics for multivariate generating functions: zero division error on last coordinate
  • evaluating symbolic expressions (without conversion to SR, i.e., staying in ring of values) #18092: evaluating symbolic expressions
  • provide <=, <, >=, > for poset elements by the category #18222: provide <=, <, >=, > for poset elements by the category (depends on Revamp __hash__, __cmp__ and __richcmp__ #10130)
  • Multiline doctests fail when using angle notation (preparser) #19088: multi-line doctests fail when using angle notation (preparser)
  • add category Posets to ZZ and QQ #19269: add category Posets to ZZ and QQ

Depends on #17600
Depends on #17693
Depends on #17715
Depends on #17716
Depends on #18182
Depends on #18222
Depends on #18223
Depends on #18586
Depends on #18587
Depends on #18930
Depends on #19017
Depends on #19028
Depends on #19047
Depends on #19048
Depends on #19068
Depends on #19073
Depends on #19079
Depends on #19083
Depends on #19088
Depends on #19094
Depends on #19110
Depends on #19259
Depends on #19269
Depends on #19300
Depends on #19305
Depends on #19306
Depends on #19316
Depends on #19319
Depends on #19399
Depends on #19400
Depends on #19411
Depends on #19412
Depends on #19420
Depends on #19421
Depends on #19423
Depends on #19424
Depends on #19425
Depends on #19426
Depends on #19429
Depends on #19431
Depends on #19436
Depends on #19437
Depends on #19504
Depends on #19510
Depends on #19521
Depends on #19528
Depends on #19532
Depends on #19540
Depends on #19576
Depends on #19577
Depends on #19580
Depends on #19898
Depends on #19921
Depends on #19931
Depends on #19944
Depends on #19945
Depends on #19946
Depends on #19957
Depends on #19961
Depends on #19965
Depends on #19969
Depends on #19981
Depends on #19987
Depends on #19999
Depends on #20000
Depends on #20020
Depends on #20040
Depends on #20043
Depends on #20044
Depends on #20045
Depends on #20049
Depends on #20050
Depends on #20051
Depends on #20052
Depends on #20053
Depends on #20054
Depends on #20055
Depends on #20056
Depends on #20065
Depends on #21659
Depends on #21665
Depends on #22140
Depends on #22340
Depends on #22360
Depends on #22395
Depends on #22396
Depends on #22414
Depends on #22944

CC: @dkrenn @cheuberg @nathanncohen @videlec @malb @mezzarobba @rwst @kalvotom

Component: asymptotic expansions

Keywords: gsoc15

Author: Benjamin Hackl, Daniel Krenn, Clemens Heuberger

Branch/Commit: public/asy/trunk @ db96be9

Issue created by migration from https://trac.sagemath.org/ticket/17601

[behackl]

Dependencies: 17600

[behackl]

Changed dependencies from 17600 to #17600

[tscrim]

comment:3

#10519 might be of interest.

[dkrenn]

comment:4

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.

[dkrenn]

Changed dependencies from #17600 to #17600, #17693

[behackl]

Changed dependencies from #17600, #17693 to #17600, #17693, #17715, #17716

[fredrik-johansson]

comment:11

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?

[videlec]

comment:13

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

[cheuberg]

comment:14

Replying to @videlec:

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

[dkrenn]

Changed dependencies from #17600, #17693, #17715, #17716 to #17600, #17693, #17715, #17716, #18182, #18222, #18223

[dkrenn]

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587

[behackl]

Changed keywords from none to gsoc15

[behackl]

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930

[behackl]

Changed dependencies from #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930 to #17600, #17693, #17715, #17716, #18182, #18222, #18223, #18586, #18587, #18930, #19017, #19028

[dkrenn]

Changed dependencies 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360, #22395

[dkrenn]

Changed dependencies 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360, #22395 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360, #22395, #22396

[dkrenn]

Changed dependencies 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360, #22395, #22396 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360, #22395, #22396, #22414

[dkrenn]

Changed dependencies 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360, #22395, #22396, #22414 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, #19532, #19540, #19576, #19577, #19580, #19898, #19921, #19931, #19944, #19945, #19946, #19957, #19961, #19965, #19969, #19981, #19987, #19999, #20000, #20020, #20040, #20043, #20044, #20045, #20049, #20050, #20051, #20052, #20053, #20054, #20055, #20056, #20065, #21659, #21665, #22140, #22340, #22360, #22395, #22396, #22414, #22944