Evaluating matrix polynomials with minimal multiplications 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?
 A: 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$.
A: 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$.
A: Implementation of polyvalm function in MATLAB 2019b.
function Y = polyvalm(p,X)
%POLYVALM Evaluate polynomial with matrix argument.
%   Y = POLYVALM(P,X), when P is a vector of length N+1 whose elements
%   are the coefficients of a polynomial, is the value of the
%   polynomial evaluated with matrix argument X.  X must be a 
%   square matrix. 
%
%       Y = P(1)*X^N + P(2)*X^(N-1) + ... + P(N)*X + P(N+1)*I
%
%   Class support for inputs p, X:
%      float: double, single
%
%   See also POLYVAL, POLYFIT.

%   Copyright 1984-2007 The MathWorks, Inc.

% Polynomial evaluation p(x) using Horner's method.

% Check input is a vector
if ~(isvector(p) || isempty(p))
    error(message('MATLAB:polyvalm:InvalidP'));
end

np = length(p);
[m,n] = size(X);
if m ~= n
    error(message('MATLAB:polyvalm:NonSquareMatrix'))
end

if np == 1    %Quick return if possible.
    Y = diag(p(1) * ones(m,1,superiorfloat(p,X))); 
    return
end    

Y = zeros(m,superiorfloat(p,X));
for i = 1:np
    Y = X * Y + diag(p(i) * ones(m,1));
end

```

