How to compute powers of square matrices? Suppose we are given a matrix $A \in \mathbb R^{N\times N}$, and let $m \in \mathbb N_0$. How fast can we compute the power $A^m$ of that matrix?

The next best thing in comparison to computing $m$-products is to utilize fast exponentation, that requires $\mathcal O(\log m )$ matrix products.

For diagonalizable matrices, the eigenvalue decomposition can be used. It's natural generalization, Jordan decomposition, is unstable under pertubation and therefore does not count (afaik).

Can matrix exponentiation in the general case be sped up?

Fast exponentation suggest a variation of this question is useful, too:

Can the square of a general matrix $A$ be computed faster than by known matrix multiplication algorithms?
As you note, computing $A^m$ can be done in $O(\log m)$ times the number of operations for matrix multiplication on $N \times N$ matrices. The answer to your second question is no, at least for asymptotic complexity -- matrix squaring and matrix multiplication have equivalent time/arithmetic complexity (up to constant factors). Reducing squaring to matrix multiplication is obvious. To reduce multiplication to squaring, suppose we wish to compute the product of $A$ and $B$. Form the $2n \times 2n$ matrix $C$ with the block structure:

$[0~~A]$

$[B~~0]$

That is, $C$ has an $n \times n$ all-zeroes matrix in its upper-left quadrant and lower-right quadrant. Note that $C^2$ contains $A\cdot B$ in its upper-left quadrant.