I am looking for references to anything interesting thats know about matrix product chains that take the vector $\{1\}$ to another vector $\{n\}$ (the end result of an addition chain). Each matrix operation adds two entries together to form a new entry and chooses to keep or discard each entry used in the sum. The maximal dimension of the vector at an arbitrary step is tightly bound by the small step count of the addition chain. It's the number of temporary variables the addition chain needs to be computed. So we have: $\{n\} = M_{l(n)}..M_1M_2\{1\}$.

Splitting the matrix product into two:

$P = M_1M_2...M_p$.

$Q = M_{p+1}M_{p+2}...M_{l(n)}$.

Gives a pair of problems. One an addition sequence problem and the other a vector addition chain problem. This is used for the fastest known algorithm for computing optimal addition chains. This is my area of interest.

When I try searching for matrix product chains I am swamped by the standard dynamic programming exercise to compute a matrix product efficiently. So can't find anything interesting on matrix product chains at all.



Browse other questions tagged or ask your own question.