#15820: Improve efficiency of the path semigroup
--------------------------------------------------+------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.2
Component: algebra | Resolution:
Keywords: quiver path algebra efficiency | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: #12630 | Stopgaps:
--------------------------------------------------+------------------------
Comment (by SimonKing):
Hi Nicolas,
Replying to [comment:2 nthiery]:
> - Some implementation without limitations (the one from the previous
ticket I guess)
An implementation which represents edges by `unsigned long long` can be
considered "unlimited".
> - Whichever of 1-4 that covers your needs (256 edges for Gröbner bases
> calculations this should be already quite big, right?)
Yes, but I want a general code.
> - As much as possible of the code shared between all implementations to
make it easy to add new ones if deemed useful.
Actually, on the level of paths, the implementations come in pairs: The
compressed representations differ from the non-compressed---at the end of
the day, we just have different ways of representing sequences of
integers. Only when it comes to interpreting a sequence of integers as a
path in a quiver will we have further differences: Does "[1,2]" mean
"start with arrow 1 of the quiver and continue with arrow 2 of the
quiver", or does it mean "travel along the outgoing arrow 1 of the vertex
we are currently located at, and then continue with outgoing arrow 2 of
the vertex we just arrived at".
Currently, I prefer a compressed representation by `unsigned long long*`.
Rationale:
- This will work even for extremely large quivers---the only restriction
is, that the number of edges can be represented as an `unsigned long long`
(a larger quiver won't fit into computer's memory anyway).
- For small quivers, even paths of length 10 will easily fit into a single
`unsigned long long`. That's quite efficient, both memory- and speed-wise.
A bit later I will post experimental code (not yet talking about quiver
paths but about sequences of integers) giving some evidence on efficiency.
And then we can still see how we interpret the integer sequences: Having a
global or a local list of arrows?
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#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/groups/opt_out.
