Binary exponentiation is a well-known method for evaluating positive integer powers of a matrix, $A^p, \; A\in\mathbb C^{n\times n},\,p\in\mathbb Z^+$.

However, I am not seeing an obvious way to adapt this algorithm to the problem of computing its *action* on a vector, $A^pv,\; v\in\mathbb C^n$. For a reasonably-sized matrix, I could certainly form $A^p$ first before multiplying it with $v$, but what I actually have is a matrix that is too huge to be formed explicitly (in fact, all I have is a black-box routine for evaluating the product $Av$).

How can I adapt binary exponentiation to compute the action of an integer-order matrix power on a vector? Alternatively, are there other methods to compute this if binary exponentiation isn't feasible?

defective). $\endgroup$ – J. M. is not a mathematician May 15 '17 at 13:48