#17693: mutable poset: a data structure for asymptotic expressions
-------------------------------------+-------------------------------------
Reporter: dkrenn | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.5
Component: misc | Resolution:
Keywords: asymptotics | Merged in:
Authors: Daniel Krenn | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/dkrenn/asy/mutable_poset | e2f884f56743c7d8780586c4b04b3d2e8242ce73
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by dkrenn):
This series of comments are the result of an email discussion. Its aim is
to give a better understanding of the needs of the data structure used in
an asymptotic expression.
An example of an asymptotic expression in say 2 variables (n->oo, t->oo)
is
{{{
A = n^3*t^2 + 42*n^2*t^2 + 3*n*t^4 + O(t)
}}}
This is stored in the mutable poset in the following way: the elements of
the poset are exactly the summands of the expression above. This means
{{{
sage: A.data # or however this may be called
poset(n^3*t^2, 42*n^2*t^2, 3*n*t^4, O(t))
}}}
The growth of these summands is partially ordered:
a) {{{n^3*t^2 >= n^2*t^2}}}
b) {{{n^3*t^2 >= t}}}
c) {{{n^2*t^2 >= t}}}
d) {{{n*t^4 >= t}}}
The mutable poset stores/caches the direct successors/predecessors, i.e.,
only the relations a), c), d), but not b), since this follows by
transitivity out of a) and c). Thus, for the example above, we have the
following information stored
{{{
poset
- term O(t)
successors: n^3*t^2, 42*n^2*t^2, 3*n*t^4
no predecessors
- term 3*n*t^4
no successors
predecessors: O(t)
- term 42*n^2*t^2
successors: n^3*t^2
predecessors: O(t)
- term n^3*t^2
no successors
predecessors: 42*n^2*t^2
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/17693#comment:4>
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.
