some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section.
The problem is: finding the most efficient way to multiply a series of matrices together, using an algorithm of some sort, and comparing these algorithms to find the most efficient one.
The dynamic algorithm approach works at a time complexity of theta of N^3.
My question is, what is the runtime of this algorithm:
A= 5x2 B= 2x7 C= 7x3
1) First, find the matrix with the lowest dimension ( a matrix which has the lower number from the rows or columns of all the matrices).
*If the lowest number is in the last dimension, it is the same like putting the entire sequence in parentheses.
*There is no guidance as to what to do if the lowest number appears twice in the sequence, so I suggest the algorithm just takes 1 randomly.
2) Then divide the sequence to 2: (A)(B•C). The parentheses will close on the matrix from the right and open on the next matrix. This way they will divide the series to 2 parts.
Then repeat the process for the 2 parts. Stop when you have 1 (or 2) matrices in the sequence.
Is this algorithm optimal? It has to be better than N^3 (the usual algorithm)