#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):
We want to perform arithmetic with asymptotic expressions, in particular
we need to do efficiently:
1) addition (and multiplication)
2) merging/absorbing terms, e.g.
{{{
n^4 + 2*n^2 + 3*n + O(1) + O(n^2) = n^4 + O(n^2)
}}}
or
{{{
O(n*t) + n + t = O(n*t)
}}}
3) removing elements of the poset, because of 2)
To make them efficent, we store successors and predecessors of each
element in the poset. These are updated when inserting/removing elements.
Note that an asymptotic expression can contain several O-terms, e.g.
{{{
O(n^3 t^2) + O(n^4 t^1) + O(n^2 t^3)
}}}
is a valid expression. In the poset each O-term is a minimal
element and they are all pairwise incomparable (thus, the O terms
will be an antichain in the poset). Anyhow, non-O-terms be be
compareable to other elements, e.g. in
{{{
3*n*t + O(n) + O(t)
}}}
we have {{{n*t >= n}}} and {{{n*t >= t}}}.
We also need to deal with situations where we want to insert an
element of the same growth: E.g. {{{4n+3n = 7n}}}, {{{4n+O(n) = O(n)}}},
thus, the elements themselves can change during addition. When
merging/absorbing and working with O-Terms with explicit
O-constants, this also occurrs frequently (even with terms of
different growth).
--
Ticket URL: <http://trac.sagemath.org/ticket/17693#comment:5>
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.
