Evaluating matrix polynomials with minimal multiplications

Question

Given a matrix polynomial of degree $n$ what is the fewest number of matrix multiplications needed to evaluate it?

For example, a degree $7$ matrix polynomial can be evaluated in $4$ matrix multiplications. Given a particular value of $A$, we want to evaluate $$a_0+a_1A+a_2A^2+a_3A^3+a_4A^4+a_5A^5+a_6A^6+a_7A^7$$ We with 3 matrix multiplications calculating $A^2, A^4,$ and $A^6$ $$1)\quad\quad B=A\cdot A=A^2 \quad\quad$$ $$2)\quad\quad C=B\cdot B=A^4 \quad\quad$$ $$2)\quad\quad D=B\cdot C=A^6 \quad\quad$$ The polynomial may now be rewritten as $$a_0+a_2B+a_4C+a_6D+A\cdot(a_1+a_3B+a_5C+a_7D)$$ which requires only $1$ more multiplication to evaluate.

Is $4$ the best possible for a degree $7$ polynomial? What about degree $n$ in general?

Answer 1

Seems like this could be bounded in terms of powers of 2.

Example: $n=16$ You would need at least $$B=A^2=A*A$$ $$C=A^4=B*B$$ $$D=A^8=C*C$$ $$E=A^{16}=D*D$$ so 4 multiplications. The most for any degree less than 16 would be degree 15 which would require 3+3=6: $A*B*C*D=A^{15}$

Thus, I think the answer might be $$\lfloor\log_2(n)\rfloor+(\text{sum of the digits of } n \text{ when represented in base 2}) - 1$$ with the $-1$ at the end because there is no cost to calculate the single power of $A$.

Answer 2

This depends on lots of stuff. Keep in mind that matrix-vector multiplication is much faster than matrix-matrix multiplication and that matrix multiplication distributes over addition. Assuming the side of the matrix is $n$ and we are mostly gonna use it for matrix-vector multiplications then ${\bf A}^n{\bf v}$ could be calculated with the same amount of calculations as ${\bf A}^2$.

So there can be a fair chance that a Horner style factorization will be better in that case, especially if memory is limited:

$$((({\bf A}+k_3){\bf A}+k_2){\bf A}+k_1){\bf A}v = ({\bf A}^4+k_3{\bf A}^3+k_3k_2{\bf A}^2+k_3k_2k_1{\bf A})$$

In reality probably some fusion of the two will be most efficient. Maybe precalculating ${\bf B=A}^2$ and combining it with the Horner, but skipping $\bf C$.