2
$\begingroup$

I originally asked a question on the Mathematica stack exchange on a similar topic here.

But it seems like my question actually extends beyond Mathematica. The issue is the following. Let $a,b,d$ be elements of some vector space $V$ over $\mathbb{R}$, and let $c_1,c_2 \in \mathbb{R}$. I have some tensor product expression $a \otimes b$ that is non commutative, but is distributive over addition and linear and such: $$(c_1 a + c_2 b) \otimes d = c_1 a \otimes b + c_2 a \otimes d.$$

Given some long expression involving the sum of many tensor products. Something like:

$$a_1 \otimes b_1 + a_2 \otimes b_2 + a_1 \otimes d + a_2 \otimes d$$

I would like an algorithm that will find a factored expression with the minimum number of tensor products. For the above, that would be just two:

$$a_1 \otimes (b_1 + d) + a_2 \otimes (b_2 + d).$$

At the moment, my 'algorithm' is to:

  1. Expand all tensor products so I do truly have a sum of single products
  2. Recursively apply rules like $c_1 a\otimes b + c_2 a \otimes d \to a \otimes (c_1 b + c_2 d)$
  3. Hope for the best.

This is working fine-ish, but is definitely not guaranteed to arrive at the factorization with the fewest terms. Because of the order that my program implements things it can get stuck on, for example:

$$a_1 \otimes b_1 + a_2 \otimes b_2 + (a_1+a_2) \otimes d$$

and doesn't realize this can be simplified further by instead grouping the $a$ terms together to get:

$$a_1 \otimes (b_1 + d) + a_2 \otimes (b_2 + d).$$

This is because I "group from the right" before I "group from the left" but regardless of which way I do it, there will be an analagous case to above where that runs into trouble.

This really feels like a problem that is common enough there should be a procedure for handling it. In fact, perhaps even one in Mathematica. I would be curious about a general thought as to a good algorithm, if I were to implement such a thing homebrew, or something specific to Mathematica.

In essence my problem is that my current algorithm is greedy, and not looking at the big picture

$\endgroup$

1 Answer 1

2
$\begingroup$

I think this could be solved with linear algebra and binary search. I don't know whether there is a better algorithm.

Given $k$, I will describe an algorithm to determine whether it is possible to rewrite the expression using at most $k$ tensor products. Then, you can use binary search on $k$ to find the smallest $k$ for which this is possible.

So, let's assume $k$ is fixed, and we want to know whether we can rewrite the expression to use at most $k$ tensor products. Let $S \subset V$ denote the set of vectors that appear in the original expression. Expand the original expression into the following form:

$$\sum_{s,t \in S} c_{s,t} \cdot (s \otimes t),$$

where the $c_{s,t} \in \mathbb{R}$ are known constants. I assume that any factored expression will have the form

$$\sum_{i=1}^k \left(\sum_{s \in S} d_{i,s} s\right) \otimes \left(\sum_{t \in S} d'_{i,t} t\right),$$

for some constants $d_{i,s},d'_{i,t} \in \mathbb{R}$. I believe this is a fully general form of your factored expressions. Now we want the original expression to be equal to the factored expression, i.e., we want to have

$$\sum_{s,t \in S} c_{s,t} \cdot (s \otimes t) = \sum_{i=1}^k \left(\sum_{s \in S} d_{i,s} s\right) \otimes \left(\sum_{t \in S} d'_{i,t} t\right).$$

This imposes some requirements on the constants $c_{s,t},d_{i,s},d'_{i,t}$. Let's work out what the requirements are. If we expand the factored expression, we find

$$\sum_{i=1}^k \left(\sum_{s \in S} d_{i,s} s\right) \otimes \left(\sum_{t \in S} d'_{i,t} t\right) = \sum_{s,t \in S} \left(\sum_{i=1}^k d_{i,s} d'_{i,t}\right) (s \otimes t).$$

We want the above to be equal to the original expression, i.e., we want

$$\sum_{s,t \in S} c_{s,t} \cdot (s \otimes t) = \sum_{s,t \in S} \left(\sum_{i=1}^k d_{i,s} d'_{i,t}\right) (s \otimes t).$$

This holds if for all $s,t \in S$, we have

$$c_{s,t} = \sum_{i=1}^k d_{i,s} d'_{i,t}.$$

Notice that this is a system of $|S|^2$ linear equations on the $2k|S|$ unknowns $d_{i,s},d'_{i,t}$. Therefore, we can check whether there is any solution to this system of linear equations, e.g., using Gaussian elimination.

Finally, if there is a solution to this system of linear equations, then we have found a factored expression that is equivalent to the original expression and uses at most $k$ tensor products. If there is no solution to this system of linear equations, then there is no factored expression of the listed form that uses at most $k$ tensor products and is equivalent to the original expression. This gives us the claimed algorithm.

$\endgroup$
1
  • 1
    $\begingroup$ This is a truly wonderful answer. I am very grateful. The final step of solving for the $d$ and $d'$ matrices can be done easily using the singular value decomposition. If it is of interest to future readers I describe such an implementation in this post: math.stackexchange.com/questions/4946689/…, where I also ask if anyone knows of a way to generalize the use of the singular value decomposition to the factorization of tensor product expressions involving more than one tensor product symbol. $\endgroup$
    – Jack
    Commented 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.