2
$\begingroup$

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

enter image description here

multiply

enter image description here

equals

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.

|cite|improve this question
$\endgroup$
  • 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.