Opened 6 years ago
Last modified 4 years ago
#17601 new enhancement
Meta ticket: Asymptotic Expansions in SageMath — at Version 48
Reported by:  behackl  Owned by:  

Priority:  major  Milestone:  sage7.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 )
We intend to implement asymptotic expansions in SageMath. We would like to do computations with simple expansions such as
n^{2} + n^{3/2} + O(n^{1/2}),
but also with expansions such as
2^{n} * n + O(n*log(n))
or even multivariate expansions such as
3*k/n + O(k^{2} / n^{2}) 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 Oconstants 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. n^{2} 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 userfriendly 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 bigOh 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
 Extending the functionality of the AsymptoticRing and AsymptoticExpansion
 #19048:
AsymptoticRing.an_element()
 #19047:
QQ.some_elements()
 #19047:
 #19068: Implement Division for asymptotic expansions.
 #19073: categorial constructions, pushout and coercions (extended) for asymptotic ring and growth groups
 #19094: Implement higherorder operations like
exp
andlog
for asymptotic expansions.  #19083: AsymptoticRing: cleanup, some improvements, documentation.
 #19048:
 Further plans
 for growth groups
 implement dependencies like k <= n^{1/2} for different growth group variables.
 growth groups with asymptotic at a noninfinity 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 (littleoh terms, omegaterms, variations of bigOh terms ...)
 #19300: Run benchmarks on
MutablePoset.remove
to decide between two algorithms.  #19305: substitution of asymptotic expansions
 #19306: common generators for asymptotic expansions
 for growth groups
 Additional dependencies
Change History (48)
comment:1 Changed 6 years ago by
 Dependencies set to 17600
comment:2 Changed 6 years ago by
 Dependencies changed from 17600 to #17600
comment:3 followup: ↓ 4 Changed 6 years ago by
comment:4 in reply to: ↑ 3 Changed 6 years ago by
comment:5 Changed 6 years ago by
 Cc ncohen added
comment:6 Changed 6 years ago by
 Dependencies changed from #17600 to #17600, #17693
 Description modified (diff)
comment:7 Changed 6 years ago by
 Cc vdelecroix added
comment:8 Changed 6 years ago by
 Dependencies changed from #17600, #17693 to #17600, #17693, #17715, #17716
 Description modified (diff)
comment:9 Changed 6 years ago by
 Cc malb added
comment:10 Changed 6 years ago by
 Cc mmezzarobba added
comment:11 Changed 6 years ago by
Are "asymptotic expressions" equivalent to "transseries" (http://arxiv.org/abs/0801.4877, http://www.texmacs.org/joris/ln/lnabs.html)? Or are they more general, less general, or partially overlapping in scope?
comment:12 Changed 6 years ago by
 Cc rws added
 Milestone changed from sage6.5 to sage6.6
comment:13 followup: ↓ 14 Changed 6 years ago by
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
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 (noninteger exponents, several (not completely independent) variables).
comment:15 Changed 6 years ago by
 Cc kalvotom added
comment:16 Changed 6 years ago by
 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
 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
 Description modified (diff)
 Keywords gsoc15 added
comment:19 Changed 5 years ago by
 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
 Description modified (diff)
comment:21 Changed 5 years ago by
 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
 Description modified (diff)
comment:23 Changed 5 years ago by
 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
 Description modified (diff)
comment:25 Changed 5 years ago by
 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
 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
 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
 Description modified (diff)
comment:29 Changed 5 years ago by
 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
 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
 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
 Summary changed from MetaTicket: Asymptotic Expressions in Sage to MetaTicket: Asymptotic Expansions in SageMath
comment:33 Changed 5 years ago by
 Description modified (diff)
comment:34 Changed 5 years ago by
 Description modified (diff)
comment:35 Changed 5 years ago by
 Branch set to u/dkrenn/asy/prototype
 Commit set to 70abf65739587016ed71a953585ff56af33e325b
 Description modified (diff)
Last 10 new commits:
47894c8  Merge branch 't/19094/asy/ringexplog' into t/19083/asy/prototype

8894fce  Merge branch 't/17716/asy/asymptoticExpression' into t/19068/asy/inversion

106eacd  Merge branch 't/19068/asy/inversion' into t/19083/asy/prototype

1108cfc  Merge branch 't/17716/asy/asymptoticExpression' into t/19048/asy/an_element

3c2fa0c  Merge branch 't/19048/asy/an_element' into t/19083/asy/prototype

1812a5e  rename docindexfile

0720b14  fix doctests: update since TestSuite now checks for cardinality

14f9a9a  Merge branch 't/19094/asy/ringexplog' into t/19083/asy/prototype

9aba4b6  make entry in reference/index

70abf65  include misc

comment:36 Changed 5 years ago by
 Description modified (diff)
comment:37 Changed 5 years ago by
 Component changed from symbolics to asymptotic expansions
comment:38 Changed 5 years ago by
 Commit changed from 70abf65739587016ed71a953585ff56af33e325b to 2e4a415d7859d3968f612932b36c98318e1823d2
Branch pushed to git repo; I updated commit sha1. New commits:
2e4a415  rename title

comment:39 Changed 5 years ago by
 Commit changed from 2e4a415d7859d3968f612932b36c98318e1823d2 to b0e228b4870e49cfdc9594c5f85173bb889f6722
Branch pushed to git repo; I updated commit sha1. New commits:
cd17673  Merge tag '6.9.beta6' into t/18182/18182on6.8

3eefe25  correct typo in AUTHORS

5fe52e4  fix doctests since name of cartesian product functor has changed

60b9375  revert changes in base_ring of category_object and adapt doctests

8d6de43  Merge remotetracking branch 'trac/u/dkrenn/18182/pushout' into t/19073/asy/groupscoercion

d50cc55  Merge branch 't/19073/asy/groupscoercion' into t/19094/asy/ringexplog

44fbccc  Merge remotetracking branch 'origin/u/dkrenn/asy/ringexplog' into t/19094/asy/ringexplog

09032ee  Merge branch 't/19094/asy/ringexplog' into t/19083/asy/prototype

b0e228b  Merge remotetracking branch 'origin/u/dkrenn/asy/prototype' into t/19083/asy/prototype

comment:40 Changed 5 years ago by
 Commit changed from b0e228b4870e49cfdc9594c5f85173bb889f6722 to 1109ce002874d776617102f2ccc295b410e4a3b6
comment:41 Changed 5 years ago by
 Milestone changed from sage6.6 to sage6.9
comment:42 Changed 5 years ago by
 Description modified (diff)
 Summary changed from MetaTicket: Asymptotic Expansions in SageMath to Metaticket: Asymptotic Expansions in SageMath
comment:43 Changed 5 years ago by
 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
 Description modified (diff)
comment:45 Changed 5 years ago by
 Description modified (diff)
comment:46 Changed 5 years ago by
 Description modified (diff)
comment:47 Changed 5 years ago by
 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
 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
#10519 might be of interest.