Let's say we have a Matrix M and a column vector v like below

enter image description here


enter image description here


enter image description here

Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 multipliction and 3 addition to calculate row1 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.

  • 1
    $\begingroup$ This is very specific for the matrix you have. Is that really what you want? You'd have to find the optimal solution for every new matrix. $\endgroup$ – Wolfgang Bangerth Aug 2 '19 at 3:51
  • $\begingroup$ @WolfgangBangerth , that matrix is only an example. consider matrix all M has small constant integers. $\endgroup$ – worldterminator Aug 2 '19 at 3:53

Your Answer

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

Browse other questions tagged or ask your own question.