#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):
Note that all the terms (individual summands) support one
operation, namely these can be multiplied, maybe coercion is
used, e.g.
{{{
4*n^2*t * O(n) --> O(n^2*t) * O(n) --> O(n^3*t)
}}}
Thus we have monoids here. "Addition" of terms is more complicated
since not always possible. E.g.
{{{
n + O(t) = n + O(t)
}}}
But since this is an operation we want to have, the data
structure has to take this into consideration.
Here an example of the addition of two asymptotic expressions, to
see what the poset should do:
{{{
B = n^2*t + n + O(1)
C = n*t^2 + O(n)
}}}
Steps in computing B + C:
1) calculate: B.poset union C.poset
This gives
{{{
poset(n^2*t, n, O(1), n*t^2, O(n)).
}}}
2) simplify: returns
{{{
poset(n^2*t, n*t^2, O(n))
}}}
To achieve this, we have to search for what can be "absorbed" by the
O-term {{{O(n)}}}. These are exactly all the predecessors of {{{O(n)}}}
(not only
the direct, but also the predecessors of the predecessors...)
Thus some kind of caching of predecessors is necessary, but "cache"
has to be updated when modifying the poset.
Note that this data structure does a preprocessing of its relations, which
is definitely good for nonsmall instances. At the moment this class should
provide an interface for the needed routines. A fine tuning (w.r.t. speed
optimization for various sizes) can be done later (if the performance is
too bad).
To conclude, the data structure needed in an asymptotic expression needs
to deal with dynamic changes (mutability) and do some caching to provide
efficient methods. And it needs to do more than a poset which is made
mutable. In particular, it has to provide the methods for the above
mentioned merging and absorbing.
--
Ticket URL: <http://trac.sagemath.org/ticket/17693#comment:6>
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.
