3
$\begingroup$

I am given a $3 \times 3$ matrix $M$, which only has real entries.

Is there an efficient way to do the following two operations with $M$?

  1. For a given input $n$, compute the $n$-fold tensor product $M^{\otimes n}$, without having to brute-force by manually using KroneckerProduct repeatedly (I want to handle large values of $n$ which makes manual calculation unwieldy).

  2. For the matrix $M^{\otimes n}$, compute the total sum of all the negative entries.

$\endgroup$
5
  • $\begingroup$ What is a general way to do the tensor product --- something that is automated and not brute force? $\endgroup$
    – BlackHat18
    Sep 6 '21 at 19:59
  • $\begingroup$ Do you really need the tensor product -- or only the sum? $\endgroup$ Sep 6 '21 at 20:01
  • $\begingroup$ @HenrikSchumacher I needed both, but even the sum would be helpful. I could at least do the tensor product manually, by brute force, for a few small values of n. $\endgroup$
    – BlackHat18
    Sep 6 '21 at 20:06
  • $\begingroup$ @bbgodfrey I think OP meant tensor product, not matrix product. $\endgroup$ Sep 7 '21 at 7:23
  • $\begingroup$ @HenrikSchumacher Indeed so. Thanks. $\endgroup$
    – bbgodfrey
    Sep 7 '21 at 12:37
5
$\begingroup$

If it is only about the sums of negative entries, then yes.

This is how we can do it without even building the tensor/Kronecker products:

M = RandomReal[{-1, 1}, {3, 3}];
ClearAll[sumPositive];
ClearAll[sumNegative];
sumPositive[1] = Total[Ramp[ M], TensorRank[M]];
sumNegative[1] = Total[Ramp[-M], TensorRank[M]];
sumNegative[n_] := sumNegative[n] = Plus[
    sumPositive[n - 1] sumNegative[1],
    sumNegative[n - 1] sumPositive[1]
    ];
sumPositive[n_] := sumPositive[n] = Plus[
    sumPositive[n - 1] sumPositive[1],
    sumNegative[n - 1] sumNegative[1]
    ];

Test for n = 8:

n = 8;
result1 = sumNegative[n]; // MaxMemoryUsed // AbsoluteTiming
result2 = Total[Ramp[-KroneckerProduct @@ ConstantArray[M, n]], 2]; // MaxMemoryUsed // AbsoluteTiming

result1 == result2

{0.00007, 4080}

{1.63739, 688748008}

True

Notice that sumNegative[n] needs $O(n)$ memory and FLOPs while the brute force approach needs $O(9^n)$ of both.

The key idea that the sum of all entries of a tensor product is just product of the sums:

Total[KroneckerProduct[A, A], 2] == Total[A, 2]^2

Now we only have onlt to keep track of the negative and the nonnegative parts of the tensors... Combined with recursion and memoization, we are lead to sumPositive and sumNegative.

Remark

This can even be sped up by a clever decomposition of n into smaller parts and by exploiting that

sumNegative[m + n] == Plus[
  sumPositive[m] sumNegative[n],
  sumNegative[m] sumPositive[n]
  ]
sumPositive[m + n] == Plus[
  sumPositive[m] sumPositive[n],
  sumNegative[m] sumNegative[n]
  ]

So for a clever decomposition of your number $n$, you can compute the sum of all nonzero entries of $M^{\otimes n}$ in sublinear time. E.g., $n = 2^k$ can be handled in $k = \log_2(k)$ time and memory.

$\endgroup$
5
  • $\begingroup$ Thanks a lot! Might you explain the code? How does it bypass computing the tensor product? $\endgroup$
    – BlackHat18
    Sep 6 '21 at 20:11
  • $\begingroup$ One specific question, what is the reasoning behind the Ramp function in Total[Ramp[M], 2]? $\endgroup$
    – BlackHat18
    Sep 6 '21 at 20:17
  • $\begingroup$ Ramp takes just the nonnegative part of all entries in the tensor (and zeroes the negative ones). $\endgroup$ Sep 6 '21 at 20:18
  • $\begingroup$ Will the same code work if $M$ is a $k \times k$ matrix (for a known $k$), instead of a $3 \times 3$ matrix? $\endgroup$
    – BlackHat18
    Sep 7 '21 at 18:56
  • 2
    $\begingroup$ Well, you can try for yourself... But the answer is "yes". It should work for arbitrary tensors... $\endgroup$ Sep 7 '21 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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