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

<p>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 <a href="http://www.cs.man.ac.uk/~hsimmons/DOCUMENTS/PAPERSandNOTES/TPoCM.pdf" rel="nofollow">this paper</a> for an example on the constructing their tensor product in the commutative case.</p>

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

CC BY-SA 3.0
2014-09-12T20:20:51.387Z
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
CC BY-SA 3.0
2014-09-12T20:44:01.417Z
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
CC BY-SA 3.0
2014-09-12T20:47:27.003Z
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
CC BY-SA 4.0
2018-06-23T01:42:38.813Z
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
<reference-request><ds.data-structures><linear-algebra>
efficient data structures for generalized tensor products
Mike Izbicki
# efficient data structures for generalized tensor products

(Asked by: username_0 on 2014-09-12)

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](http://www.cs.man.ac.uk/~hsimmons/DOCUMENTS/PAPERSandNOTES/TPoCM.pdf) 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?

**Tags:** reference-request, ds.data-structures, linear-algebra
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_0**: 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?  
> **username_2**: 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}$.  

---

## 0 answers

