In which order should the following product of four matrices ABCD be evaluated so as to perform the least number of operations?
A is a 1 by 5 matrix, B is a 5 by 100 matrix, C is a 100 by 10 matrix, D is a 10 by 5 matrix.
I have what seems to be conflicting information on how to solve this problem. Research on the internet leads me to believe that I compute the efficiency one way, however my professor seems to have given me an entirely different and conflicting formula. I'm not sure if two different approaches are used two solve two slightly different wordings of similar questions, like solving for total number of operations versus solving for total number of multiplications.
From what I have read on the internet, I believe that the answer to this problem would be (((AB)C)D) is the order with the least amount of operations, with a total number of operations calculated at 1550.
To elaborate on my conflicting sources of information, here is an example. Given the above values, if we were to multiply (AB)C:
The internet has shown me the # of operations is (1)(5)(10) + (1)(100)(10).
Contrast this with my professor's in class example of: (1)(100)(2(5) - 1) + (1)(10)(2(100) - 1).
These are clearly very different approaches to solving this problem, and I am wondering where my misunderstanding is. Are these two approaches solving a different problem entirely (such as number of multiplications vs number of operations)? Or is one approach completely wrong? Thanks in advance for any input.
I think I see the problem now. The number of operations also include the addition of the numbers after you multiply them out. Although $p\times q$ multiplied by $q \times r$ is $pqr$ multiplications, there are also $(q-1)$ additions for each of the $p\times r$ entries, making a total of $pr\times(2q-1)$ operations.
The best algorithm to find the number of operations may not be similar to the best algorithm to find the number of multiplications, but an easy to understand algorithm to do both so is of $O(n^3)$ time complexity, with $n$ being the number of matrices. Basically, it relies on finding the number of operations required to multiply a subarray of matrices in order to find the number of operations required to multiply larger subarrays of matrices.