#12630: Add representations of quivers and quiver algebras to sage
-------------------------------------------+--------------------------------
Reporter: JStarx | Owner: AlexGhitza
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.10
Component: algebra | Resolution:
Keywords: algebra, quiver, module | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Jim Stark | Merged in:
Dependencies: #12412, #12413 | Stopgaps:
-------------------------------------------+--------------------------------
Comment (by SimonKing):
In the past few weeks (or even months) I have been a bit too busy with
other things. So, I'm sorry for my silence.
Let me try to summarise what your code does (correct me if I am wrong) and
ask my questions on it, followed by a summary of what I soon need for my
project. Then I suggest a code structure that might be useful (but is
perhaps biased, as it is influenced from my project). Hopefully we can
then make a plan how to avoid duplication of work.
__What the code provides__
* a `QuiverFactory`, that returns immutable quivers (a new sub-class of
`DiGraph`) and uses caching. The factory refuses to create quivers with
loops.
* algebras of acyclic quivers (thus, finite dimensional) and their
elements; no quotient algebras.
* representation of acyclic quivers.
* a class `QuiverPath`, that is a `UniqueRepresentation` and defines
multiplication and stuff, but does not implement the elements of anything.
* various classes that together implement representation of quivers,
homsets etc.
The code is entirely in Python, so, does likely not address speed. Having
quotients of acyclic quiver algebras is considered phase 2, having
quotients of general quivers is considered phase 3. It is stated that most
of the quiver code would work with cycles, only the algebras would need
significant changes.
__Questions on your code__
* You state that most of the code would work with cyclic quivers. So, why
do you require acyclicity ''everywhere''? Why don't you just provide a
(cached) method `is_acyclic` that is called when you really need
acylicity, raising an error if there are cycles?
* What is the rôle of `QuiverPath`? It is not inheriting from any
algebraic base class, and is not even the element of anything. I'd rather
expect that a `QuiverPath` is element of a `Quiver`.
* Why do you use `UniqueRepresentation` on `QuiverPath`? Assume that you
have two quivers, and assume they are labelled in such a way that both
quivers contain a path that starts at vertex 1 and ends at vertex 2 with
edge sequence a, b, c, d. Would you really say that these two paths, that
belong to totally different quivers, are ''identical''?
__What I need '''soon'''__
I try to provide an efficient implementation of my non-commutative version
of the F5 algorithm for modules over basic algebras (hence, modules over
finite dimensional quotients of quiver algebras). The background is that
the F5 algorithm (in contrast to other Gröbner basis algorithms) would
also allow to compute a minimal generating set for the module (actually:
Loewy layers of the module), provided that a negative degree monomial
ordering is used. The quivers I'm working with will typically contain
cycles.
Hence, I need
* Quivers. Would be good to have a unique representation and immutability.
''Must'' allow cycles.
* The algebraic structure formed by the paths in a quiver, subject to
concatenation of paths. How to call it? Florent suggests "monoidoid", I
suggest "multimonoid". In any case, it is an associative magma. It might
be possible to identify the quiver with this algebraic structure; hence, a
quiver would not just be a digraph, but would also inherit from some
algebraic base class and would belong to the category of associative
magmas. Of course I want elements of this algebraic structure.
* I need to be able to choose a monomial ordering on the paths (i.e.,
compatible with concatenation of paths). It ''must'' be possible to choose
an ordering that first compares paths by ''negative'' length.
* Quiver algebras, i.e., the algebra generated by the afore-mentioned
associative magma that is given by the paths in a quiver, with a monomial
ordering inherited from the ordering of paths. I guess that some generic
(and already existing!) code would just work.
* Finite dimensional quotients of quiver algebras, and their elements.
* Modules over finite dimensional quotients of quiver algebras. Note that
modules over non-commutative rings are currently not implemented.
__My speed requirements__
The following operations should be super fast:
In the quiver (considered as an associative magma)
* concatenation of paths
* comparison of paths
* hashing of paths
* test whether a given path w starts with a given path v
Speed in the quiver algebra is not essential (hence, I could really live
with slow generic code here). However, multiplication in the finite
dimensional path algebra quotients should be very fast.
__Suggested code structure__
* Quivers are not just finite digraphs, but they should IMHO be identified
with the associative magma given by path concatenation. Hence, the base
class `Quiver_generic` should use a unique factory and inherit from
`DiGraph` (this is what you do) ''and'' should inherit from Parent, being
initialised in the category `AssociativeMagmas()` (create this category,
if it does not exist already).
* `QuiverPath` should use some algebraic base class and should be used to
construct the element class of a quiver.
* `QuiverPath` should be cythoned. I have some experimental code, that
unfortunately is spread over different machines. Approaches that I tested:
- Encode a path as an integer (if the quiver has n arrows then you read
the integer as an n-adic number, and the sequence of digits yields the
sequence of arrows in the path
- Encode a path as `*unsigned char`. Hence, you have a list of at most
255 arrows of your quiver, and a sequence of bytes corresponds to a
sequence of arrows.
- Same as the previous, but use a dense representation: If you have less
arrows, then squeeze several arrows into one byte. By consequence, you
need less memory.
- Number the arrows ''locally''. Hence, if you are at a certain vertex,
then your numbering takes into account only the outgoing arrows that start
at this vertex. Hence, if you use `*unsigned char`, then you can work with
quivers that may have much more than 255 arrows, as long as each vertex
has not more than 255 outgoing arrows.
- Same as the previous, but use a dense representation.
It seems to be that the last approach was best for my applications, but
I really need to test again, as the code rotted for a couple of months.
* We could use (existing?) general code for obtaining the quiver algebra
of a general quiver, and use your code if the quiver happens to be
acyclic.
* I have experimental code (rotting since months) for finite dimensional
quotients of quiver algebras. Multiplication in the quotient is
implemented by matrix multiplication, and a vector space basis of the
algebra quotient is given by those paths that are not leading monomial of
a quotient relation.
__Plans to combine work__
It seems that our projects intersect only in one point: We use quivers.
You would proceed with representations of acyclic quivers (which is not in
my focus), while I would proceed with finite dimensional quotients of
quiver algebras (which is not in your focus).
But we could combine forces in the implementation of quivers. Do you think
it would work for you that your `QuiverFactory` is modified such that it
also allows to create quivers with cycles? Would it work for you that
`Quiver_generic` inherits from both `DiGraph` and `Parent` and is
initialised as an associative magma, using `QuiverPath` as element class?
Would it work for you that `QuiverPath` is cythoned, using whatever dense
representation as described above, with comparison by negative length? I
think your code concerning representations for the special case of acyclic
quivers would still work.
In any case, I should try to reconstruct my experimental code...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12630#comment:31>
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?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
