3
$\begingroup$

Lets say I take a computation that involves only addition and multiplication:

(a+b)*(c+d) 

which can be done in many other ways, eg.

a*(c+d) + b*(c+d) a*c + a*d + b*c + b*d 

In terms of additions and multiplications the number of operations required for each of the three examples shown are (2,1) (3,2) (3,4) respectively. Clearly, if the goal is to reduce the total number of operations the first is superior. Is there a way, given an arbitrary expression to find the computation order that requires the least number of operations?

  • 0
    Can't you reduce this problem to 3-SAT? Doesn't that make it NP-Complete (in general)?2010-12-07

1 Answers 1

5

Here's a closely related question which is easier to answer. Suppose you only care about the number of multiplications. (This is reasonable in many situations where addition is cheap but multiplication is expensive, so you want to minimize the number of multiplications you're going to do.) So suppose someone gives you an expression like a*c + a*d + b*c + b*d and you want to rearrange using as few multiplications as possible.

In this case what you're doing is computing the "rank" of a tensor. (Warning: "rank" of a tensor can mean two totally different things, this is the rank that's analogous to rank of a matrix, not the rank that tells you which kind of tensor you're looking at.)

For example, suppose your expression only ever involves products of two things, then this becomes computing the rank of a matrix. In your example, a*c + a*d + b*c + b*d, you're looking at a 4x4 matrix (since there are 4 variables: a,b,c,d) which is:

$\begin{pmatrix}0&0&1&1\\ 0&0&1&1 \\ 0&0&0&0 \\ 0&0&0&0 \end{pmatrix}$

This matrix has rank 1 as is easily seen using row-reduction, hence it can be written using only one multiplication.

I don't know whether there are good algorithms for computing ranks of higher tensors the way there are for matrices.

  • 0
    I do not think that the minimum number of multiplications is equal to the rank of the tensor naturally defined from the polynomial when the polynomial is not quadratic. (It may be approximately equal in some sense.)2010-12-14