Post History

While there are no doubt even more clever things you can do, the most straightforward approach, which will likely make a significant improvement, is to move from matrix-matrix multiplication to matrix-vector multiplication.

Let $e_k$ be a (column) vector with all $0$s except the $k$-th entry is $1$. To get the $k$-th row of a matrix, you just multiply it on the right by $e_k^T$, i.e. $e_k^T M$. Then, instead of computing $e_k^T (M^K)$, you compute $(\cdots((e_k^T M)M)\cdots M)$. You won't be able to exploit repeated squaring, but this takes $O(KN^2)$ time, so if $K < N$ this is faster than doing even a single matrix-matrix multiplication. If $K > N$, you can square $M$ to halve $K$ and quickly get $K < N$. You can do some simple algebra to figure out how many squarings are worthwhile. However, when $K$ is much greater than $N$, you may be better off doing diagonalization-based techniques. If your matrix is diagonalizable (e.g. if it is positive definite), then there are algorithms to diagonalize in $O(N^3)$ time. Once you have the diagonalized form, exponentiation is just exponentiating the components of the diagonal matrix. You would then have something like $O(N^3 + N\log K)$. There are very many techniques to do better at this problem if your matrix has some known special structure.