Hi Volker, On 2012-11-22, Volker Braun <vbraun.n...@gmail.com> wrote: > ------=_Part_1271_8275328.1353589681337 > Content-Type: text/plain; charset=ISO-8859-1 > > On Thursday, November 22, 2012 7:37:49 AM UTC, Simon King wrote: > >> Bit packed exponents? What does that mean in a path algebra? I thought >> that monomials (i.e., paths in the quiver) would rather be represented by >> lists of integers, the integers being the labels of arrows in the quiver. >> > > What would be nice is to have a more compact representation where paths (up > to some maximal length obviously) are represented by a fixed-size memory > object.
That's perhaps a good idea - namely, in my application, I am dealing with basic algebras, i.e., with *finite* dimensional path algebra quotients. I do need elements of the non-quotiented path algebra as well (namely as signatures in a non-commutative F5 algorithm), but here the lengths are bounded as well. However, that's only *my* application - but I want it to be useful to other people. So, a bounded length may not work. > Really you only need to know the starting point and, sequentially, which > arrow you are following at each node. OK, that could be more compact, since you may have many arrows in the quiver, but on each vertex you would typically have much less, so that you need fewer bits to store the index. > The most naive storage scheme would > be to just save the index of a path in a table of paths up to a > predetermined maximal length, though that would make composition a painful > table lookup. Sounds painful. In addition, for monomials m and n, I need to be able to quickly find out whether n is a factor of m, i.e., whether there are monomials a, b such that m=a*n*b. That would be difficult when only storing the monomials in a table. > But you > could, for example, store the path info as the lowest x bits of a machine > integer such that composition is bit-shift and addition. If the maximal number of arrows starting at a vertex fits into n bits, then each path of length l can be stored as a sequence of l*n bits. The alternative would be: If the *total* number of arrows fits into m bits, then a path of length l can be stored as a sequence of l*m bits, which is of course greater than l*n. Concatenation is easy in both representations: *IF* one is lucky and l*n (resp. l*m) is less than the word length, then it is indeed just bit-shift and addition. But I am not so sure we can rely on l*n being short enough. I will mainly work with a (negative) degree lexicographic ordering - which would be easy to implement in both representations. Concerning divisibility, I think the l*m-representation is a little easier than the l*n-representation. Best regards, Simon -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-devel@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
