#17716: AsymptoticExpression
-----------------------------+----------------------------------
Reporter: behackl | Owner:
Type: PLEASE CHANGE | Status: new
Priority: major | Milestone: sage-6.5
Component: symbolics | Keywords: asymptotics
Merged in: | Authors: Benjamin Hackl
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/ticket/17716>
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.
