#17716: AsymptoticExpression
-------------------------------------+-------------------------------------
Reporter: behackl | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.5
Component: symbolics | Resolution:
Keywords: asymptotics, | Merged in:
gsoc15 | Reviewers:
Authors: Benjamin Hackl | Work issues:
Report Upstream: N/A | Commit:
Branch: | 8dc7df1fd1c8cee8ff4ac8f6eb8eb2fc4d1b3e3b
u/behackl/asy/asymptoticExpression | Stopgaps:
Dependencies: #17600, #17693, |
#17715 |
-------------------------------------+-------------------------------------
Changes (by behackl):
* keywords: asymptotics => asymptotics, gsoc15
* commit: => 8dc7df1fd1c8cee8ff4ac8f6eb8eb2fc4d1b3e3b
* dependencies: => #17600, #17693, #17715
* branch: => u/behackl/asy/asymptoticExpression
Old description:
> We want to implement asymptotic expressions like (5 * n * 2^n^ - 2 *
> n^2/3^ + O(n * log(n))) based on our implementation of asymptotic terms
> (i.e. objects which contain a growth and possibly some additional
> information; see ticket #17715) and the !MutablePoset data structure (see
> ticket #17693).
>
> Basically, an asymptotic expression represents the sum of asymptotic
> terms. The terms are stored within an !MutablePoset, which is helpful for
> the management of the terms, as absorption of terms (and their
> predecessors w.r.t. growth) can be handled efficiently.
>
> For example:
> (n^3^ + n^2^ + n + 1) + (O(n^2^)) evaluates to (n^3^ + O(n^2^)),
> because the O term absorbs n^2^ and its predecessors, which is
> information that is stored in the !MutablePoset.
>
> Another more complex example would be:
> (4 * n^2^ * t + 3 * n * t^2^ + O(n)) + (O(n^2^ * t^3/2^)) evaluates
> to (3 * n * t^2^ + O(n^2^ * t^3/2^)).
> Here, the !MutablePoset behind the term (4 * n^2^ * t + 3 * n * t^2^
> + O(n)) incorporates the relations `n <= 4 * n^2 * t` and `n <= 3 * n *
> t^2`, whereas the expression (O(n^2^ * t^3/2^)) only contains the term
> n^2^ * t^3/2^, and thus the corresponding !MutablePoset contains no
> relations. Adding these two terms translates into merging the two
> underlying posets. By inserting the term O(n^2^ * t^3/2^) into the first
> poset, new relations `4 * n^2 * t <= n^2 * t^(3/2)` and `n <= n^2 *
> t^(3/2)` are discovered.
> As O terms absorb terms of weaker or equal growth, the term 4 * n^2^
> * t and O(n) are removed from the poset. As noted above, the remaining
> elements form the asymptotic expression (3 * n * t^2^ + O(n^2^ *
> t^3/2^)).
>
> Concretely, we plan to implement the elements !AsymptoticExpression (with
> parent !AsymptoticRing) whose objects act as described above.
>
> See meta-ticket #17601 for the planned structure.
New description:
We want to implement asymptotic expressions like (5 * n * 2^n^ - 2 *
n^2/3^ + O(n * log(n))) based on our implementation of asymptotic terms
(i.e. objects which contain a growth and possibly some additional
information; see ticket #17715) and the !MutablePoset data structure (see
ticket #17693).
Basically, an asymptotic expression represents the sum of asymptotic
terms. The terms are stored within an !MutablePoset, which is helpful for
the management of the terms, as absorption of terms (and their
predecessors w.r.t. growth) can be handled efficiently.
For example:
(n^3^ + n^2^ + n + 1) + (O(n^2^)) evaluates to (n^3^ + O(n^2^)),
because the O term absorbs n^2^ and its predecessors, which is
information that is stored in the !MutablePoset.
Another more complex example would be:
(4 * n^2^ * t + 3 * n * t^2^ + O(n)) + (O(n^2^ * t^3/2^)) evaluates to
(3 * n * t^2^ + O(n^2^ * t^3/2^)).
Here, the !MutablePoset behind the term (4 * n^2^ * t + 3 * n * t^2^ +
O(n)) incorporates the relations `n <= 4 * n^2 * t` and `n <= 3 * n *
t^2`, whereas the expression (O(n^2^ * t^3/2^)) only contains the term
n^2^ * t^3/2^, and thus the corresponding !MutablePoset contains no
relations. Adding these two terms translates into merging the two
underlying posets. By inserting the term O(n^2^ * t^3/2^) into the first
poset, new relations `4 * n^2 * t <= n^2 * t^(3/2)` and `n <= n^2 *
t^(3/2)` are discovered.
As O terms absorb terms of weaker or equal growth, the term 4 * n^2^ *
t and O(n) are removed from the poset. As noted above, the remaining
elements form the asymptotic expression (3 * n * t^2^ + O(n^2^ * t^3/2^)).
Concretely, we plan to implement the elements !AsymptoticExpression (with
parent !AsymptoticRing) whose objects act as described above.
Within this ticket, a **minimal working prototype** shall be implemented,
such that ''univariate'', ''polynomial'' expressions can be handeled.
See meta-ticket #17601 for the planned structure and a roadmap.
--
--
Ticket URL: <http://trac.sagemath.org/ticket/17716#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
