Let's say we have a Matrix M and a column vector v like below
Assume we can only perform multiplication, addition and substraction operation.
With normal approach we need 3 multipliction and 3 addition to calculate
row1 = v_1 + 2v_2 + 2v_3 + 4v_4.
However we can do it smartly by
t1 = v_1 + 2*v_3 t2 = v_2 + 2*v_4 row1 = t1 + 2 * t2 row2 = t2 - t1 row3 = ...
Totally we only need 4 multiplication and 5 addition/substraction to do the calculation.
Is there any algorithm or approach to figure out the minimum number of operations?
P.S. I know sub-expression elimination algorithm can be used for this kind of problem. However I am trying to figure out whether it can be solve by linear algebra method or explaination.