# efficient data structures for generalized tensor products

The usual tensor product of vectors is a matrix. There has been tons of research into efficiently storing and operating on matrices in computers.

But we can generalize the tensor product quite a bit. For example, a monoid is like a vector that's forgotten a lot of it's properties. The only structure it has is associative addition. We can take the tensor product of two monoids to be the "most general, generalized bilinear operator." See this paper for an example on the constructing their tensor product in the commutative case.

My question is: what are some efficient data structures for representing these generalized tensor products on a computer?

• What do you want to do with these? It seems to me that if you are talking about commutative monoids, what you have is almost a $\mathbb Z$-module (except that, lacking negation, it is more like an $\mathbb N$-module). Iterated tensor products of monoids, $M \otimes M \otimes \cdots \otimes M$, will have size increasing with the number of tensor factors; there will be no "efficient representation" in general, but this doesn't mean that there is no efficient representation for whatever you have in mind. – Niel de Beaudrap Sep 12 '14 at 20:20
• I don't have anything particular in mind, just curious. I suspect that there are efficient implementations, though. Any reasonable linear algebra lib (e.g. BLAS) is going to pay a lot of attention to how matrices represented to ensure cache efficiency. Multilinear libraries have a much more complicated task of doing this, but that is still their main goal. I'm curious how much easier/harder this task becomes when we have less structure than a vector space to work with. – Mike Izbicki Sep 12 '14 at 20:44
• Also, I'm not just interested in the commutative monoid case, but more generally. For example, $\mathbb{Z}$-modules seem like they should be very similar to vector spaces, but they often behave very differently. They might not even have a basis! Therefore, does it still make sense to represent the tensor product as a matrix? Are there some tensor products of $\mathbb{Z}$-modules that cannot be represented this way? – Mike Izbicki Sep 12 '14 at 20:47
• Elements of the tensor product of two $\mathbb{Z}$-modules can always be represented by an integer matrix, where certain entries are considered modulo $n$ for various $n$. See, for example, the paper of Hillar and Rhea explicating the structure of $Aut(A)$ where $A$ is an abelian group. See also Smith Normal Form. I don't know of any highly optimized packages that do this - maybe GAP or MAGMA? For tensor products of more than two vectors, it really depends what you want to do with them, as most problems on 3-tensors are already NP-hard, even for vectors over $\mathbb{C}$. – Joshua Grochow Jun 23 '18 at 1:42