Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
FWIW, some optimizing compilers can do (a not entirely clever version of) it so you don't have to when producing binaries. Of course, sometimes a clever human can do better than a compiler. –  J. M. Dec 7 '10 at 17:00
    
All optimization rules I know work on system level and exploit characteristics of a specific machine (model). On this abstract level, all you can do (imho) is keep the computation tree as balanced as possible. –  Raphael Dec 7 '10 at 19:55
    
Can't you reduce this problem to 3-SAT? Doesn't that make it NP-Complete (in general)? –  user4143 Dec 7 '10 at 20:09
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
1  
Forget about a good algorithm, how could one compute the (matrix) rank of a tensor whose (order) rank is higher then two? Wikipedia gives "Thinking of matrices as tensors, the tensor rank generalizes to arbitrary tensors; note that for tensors of order greater than 2 (matrices are order 2 tensors), rank is very hard to compute, unlike for matrices.", but no references. –  Hooked Dec 7 '10 at 18:19
    
Doh! Well at least that's evidence that the original question probably doesn't have a practical answer. –  Noah Snyder Dec 7 '10 at 18:29
    
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.) –  Tsuyoshi Ito Dec 14 '10 at 6:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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