I have a huge list of matrix i.e A = {M0, M1, M2 .. Mn}.I have a task to find the product of all the matrices in a given range {x,y} i.e Mx * Mx+1 * Mx+2 ... * My.I would like to know if there is any algorithm or data structures that might efficiently compute this query.I have tried creating a 2D matrix of all possible combination of range but as my initial matrix is very big this does not seem like a practical solution.
Matrix multiplication range queries
algorithms;data structures;trees
Instead of precomputing all the possible combinations, just precompute levels of power of 2.So first would be M0_1=M0*M1, M2_3=M2*M3, M4_5=M4*M5, ...Second would be M0_3=M0*M1*M2*M3, M4_7=M4*M5*M6*M7, ...And so on, until biggest power of 2 that is smaller than n. This will take only 2x more memory.Then, you can pick subdivide the range so that the biggest blocks are part of the calculation. For example, for range {1,8} you would multiply M1*M2_3*M4_7*M8. That is only 3 multiplications instead of 8. In general worst case amount of multiplications is logarithmic function of length of the range.Also, picking the proper sub-ranges might be optimized using some clever binary logic. So that part has constant time complexity.