#16453: Cythonize quiver paths
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: algebra | Resolution:
Keywords: | Merged in:
Authors: Simon King | Reviewers:
Report Upstream: N/A | Work issues: Fix issue in bounded
Branch: | integer sequences
u/SimonKing/cythonize_quiver_paths | Commit:
Dependencies: #15820 | 73b65398410ca968bff08f7d3d1c399a8caaecee
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by SimonKing):
Currently, I encode paths as a sequence of integers, where each integer
uniquely determines an arrow in the quiver: The integers are bounded from
above by the number of oriented arrows of the quiver.
There would be an alternative, sparser encoding as a sequence of integers,
if one additionally provides the starting point: Each integer uniquely
determines an outgoing arrow at one given vertex.
Example: Assume that the underlying graph is just a cycle formed by 8
edges, and we have one arrow in each direction for each edge. Let x be the
starting vertex of arrow 1, and the consecutive arrows in an oriented
circle are numbered 1,...,8, and in the opposite circle are numbered
9,...16. Then, to encode the cycle starting at x, we currently present it
as `<1,2,3,4,5,6,7,8>` in one and `<9,10,11,12,13,14,15,16>` in the other
orientation.
But with the alternative encoding, we observe that there is exactly two
outgoing arrows at each vertex. One directed circle starting at x could
just be encoded as `(x, <1,1,1,1,1,1,1,1>)` and the opposite direction as
`(x, <2,2,2,2,2,2,2,2>)`.
In other words, the bounded integer sequence in the current implementation
has bound 17, but in the alternative implementation only has bound 3. It
require less memory and thus some arithmetic operations might be faster.
Detection of a sub-path will be slower, since it involves more work than
testing a sub-sequence of a bounded integer sequence.
I am not sure what will be better for my application (computing Gröbner
bases does involve detection of sub-paths!).
My strategical question: Can I wait with the decision of what
implementation to choose? Should it better be settled right away?
Actually, some operations (such as concatenation!) would stay exactly the
same as they are now, and also note that currently I store start and end
point of a path as cdef attributes of the path anyway. So, it may even be
possible to have a parameter to choose the implementation at run time.
What do you think of it?
--
Ticket URL: <http://trac.sagemath.org/ticket/16453#comment:59>
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.
