Performance of CanonicalBasis/iterators of path algebras

[HereComesTheMoon]

To make matters short: The computation of CanonicalBasis(KQ), where KQ is a path algebras, scales like O(n!), where n is the number of arrows. If someone wanted to say, compute the transpose (or AR-translate) of a module M over a path algebra with 10+ vertices, then this process becomes unbearably slow (say, several seconds), since this computation constructs a canonical basis.

The same computation for a module over the quotient of a path algebra finishes within milliseconds.

To my understanding the culprit is the NextPath function located in quivers.gi. This one is called by CanonicalBasis(KQ) to create a basis element for every path which we can find. To explain the issue, assume that we are given some quiver Q with arrows a_1, a_2, ..., a_n.

NextPath constructs the paths of length 2 as follows: It tests all possible products of two arrows, ie. it computes a_i a_j for all values of i and j, and returns those which are not zero. Similarly, for all paths of length 3 it computes all products a_i a_j * ak for all possible values of i, j, and k, and so on. To construct a canonical basis we will thus compute a total of \sum^n{k=0} k! paths.

Suggestions: It should be possible to rewrite the algorithm to take the graph structure of our quiver into account, and cull unnecessary computations. Alternatively, it might be possible to use the CanonicalBasis algorithm which is employed for quotients of path algebras. It uses a Gröbner basis approach, and is much faster. I am not familiar enough with the topic of Gröbner bases to know if this would be possible.

I am considering to write a fix myself, but figured I should open an issue about it first.

[sunnyquiver]

In https://github.com/sunnyquiver/QPA2/ there is a similar function (I think) FilteredPathIterator, and there one has used OutgoingArrows or equivalently OutgoingArrowsOfVertex in QPA1. So is the fix to used the latter function in BuildPath? I must admit that I not totally sure how the NextPath function works.

[HereComesTheMoon]

I was a little busy (among other things, with wrapping up some of the work for which I used GAP, it's now on my own GitHub), but I'm currently working on fixing this issue.

In https://github.com/sunnyquiver/QPA2/ there is a similar function (I think) FilteredPathIterator, and there one has used OutgoingArrows or equivalently OutgoingArrowsOfVertex in QPA1. So is the fix to used the latter function in BuildPath? I must admit that I not totally sure how the NextPath function works. I have not looked at QPA2 much, I admit. Using OutgoingArrowsOfVertex is absolutely the right way to go when it comes to fixing this, though, and that's how I did it. The code can be found at [https://github.com/HereComesTheMoon/qpa/blob/nextpathfix/lib/quiver.gi](my own fork of QPA), and I plan to open a pull request once I figured out how to deal with the final issue.

The last issue is that I'm still not sure how to deal with the

  true, 
  [ IsQuiverEnumerator, IsPosInt ],
  0,
  function( enum, number )

block in quiver.gi. It calls NextPath, and I don't really get why this function exists, or how to change it to accommodate the new NextPath.

[HereComesTheMoon]

As a side note, I used the following code to test the functions:

testn := function(n)
#Test speed of computation of nextpath for linear An quiver
    local orientation, Q, i, t0;
    orientation := [];
    for i in [1..n-1] do
        Add(orientation, "r");
    od;
    Q := DynkinQuiver("A", n, orientation);
    t0 := NanosecondsSinceEpoch();
    for i in Iterator(Q) do
    od;
    return NanosecondsSinceEpoch() - t0;
end;

The old code requires several minutes to compute this call for n = 10, the fixed version computes needs less than a second to call this function for all values up to n = 100.

[HereComesTheMoon]

Alright, I opened #82 to merge my changes.