Opened 5 years ago
Last modified 3 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 )
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
- 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 higher-order operations like
exp
andlog
for asymptotic expansions. - #19083: AsymptoticRing: cleanup, some improvements, documentation.
- #19048:
- 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
- for growth groups
- Additional dependencies
Change History (49)
comment:1 Changed 5 years ago by
- Dependencies set to 17600
comment:2 Changed 5 years ago by
- Dependencies changed from 17600 to #17600
comment:3 follow-up: ↓ 4 Changed 5 years ago by
comment:4 in reply to: ↑ 3 Changed 5 years ago by
comment:5 Changed 5 years ago by
- Cc ncohen added
comment:6 Changed 5 years ago by
- Dependencies changed from #17600 to #17600, #17693
- Description modified (diff)
comment:7 Changed 5 years ago by
- Cc vdelecroix added
comment:8 Changed 5 years ago by
- Dependencies changed from #17600, #17693 to #17600, #17693, #17715, #17716
- Description modified (diff)
comment:9 Changed 5 years ago by
- Cc malb added
comment:10 Changed 5 years ago by
- Cc mmezzarobba added
comment:11 Changed 5 years ago by
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
- Cc rws added
- Milestone changed from sage-6.5 to sage-6.6
comment:13 follow-up: ↓ 14 Changed 5 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 5 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 (non-integer exponents, several (not completely independent) variables).
comment:15 Changed 5 years ago by
- Cc kalvotom added
comment:16 Changed 5 years ago by
- 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
- 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
- Description modified (diff)
- Keywords gsoc15 added
comment:19 Changed 4 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 4 years ago by
- Description modified (diff)
comment:21 Changed 4 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 4 years ago by
- Description modified (diff)
comment:23 Changed 4 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 4 years ago by
- Description modified (diff)
comment:25 Changed 4 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 4 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 4 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 4 years ago by
- Description modified (diff)
comment:29 Changed 4 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 4 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 4 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 4 years ago by
- Summary changed from Meta-Ticket: Asymptotic Expressions in Sage to Meta-Ticket: Asymptotic Expansions in SageMath
comment:33 Changed 4 years ago by
- Description modified (diff)
comment:34 Changed 4 years ago by
- Description modified (diff)
comment:35 Changed 4 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/ring-exp-log' 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 doc-index-file
|
0720b14 | fix doctests: update since TestSuite now checks for cardinality
|
14f9a9a | Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype
|
9aba4b6 | make entry in reference/index
|
70abf65 | include misc
|
comment:36 Changed 4 years ago by
- Description modified (diff)
comment:37 Changed 4 years ago by
- Component changed from symbolics to asymptotic expansions
comment:38 Changed 4 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 4 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/18182-on-6.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 remote-tracking branch 'trac/u/dkrenn/18182/pushout' into t/19073/asy/groups-coercion
|
d50cc55 | Merge branch 't/19073/asy/groups-coercion' into t/19094/asy/ring-exp-log
|
44fbccc | Merge remote-tracking branch 'origin/u/dkrenn/asy/ring-exp-log' into t/19094/asy/ring-exp-log
|
09032ee | Merge branch 't/19094/asy/ring-exp-log' into t/19083/asy/prototype
|
b0e228b | Merge remote-tracking branch 'origin/u/dkrenn/asy/prototype' into t/19083/asy/prototype
|
comment:40 Changed 4 years ago by
- Commit changed from b0e228b4870e49cfdc9594c5f85173bb889f6722 to 1109ce002874d776617102f2ccc295b410e4a3b6
comment:41 Changed 4 years ago by
- Milestone changed from sage-6.6 to sage-6.9
comment:42 Changed 4 years ago by
- 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
- 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
- Description modified (diff)
comment:45 Changed 4 years ago by
- Description modified (diff)
comment:46 Changed 4 years ago by
- Description modified (diff)
comment:47 Changed 4 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 4 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
comment:49 Changed 4 years ago by
- Description modified (diff)
#10519 might be of interest.