I'm looking for the most efficient way to calculate a single entry of a matrix that was $n$ times multiplied with itself .
Pet example and motivation:
Let us denote the Stirling numbers of the second kind as
$$
\left\{n\atop k\right\}
$$
As far as I know, there is no closed formula for $\left\{n\atop k\right\}$.
However, one formula for $\left\{n\atop k\right\}$ is the following:
Let
$$
A:= \begin{pmatrix}
k & 1 &&&&\\
& k-1 &1 &&&\\
& & \ddots & \ddots &&\\
&&&1&1\\
&&&&0
\end{pmatrix}
$$
Then we have $\left\{n\atop k\right\} = (A^n)_{1,k+1}$.
Let $A\in\mathbb{R}^{k\times k}$. I'm looking for the most efficient (exact or approximate) ways to calculate the cell $(i,j)$ of $A^n$ (further denoted as $(A^n)_{i,j}$).
Methods I've got so far:
- Direct calculation:
By computing iteratively $A^i$ for all $i$'s that are powers of $2$ and then multiplying together all those appearing in the binary notation of $n$, we can calculate $A^n$ in $O(k^3 \log_2(n))$
- Direct substitution: $$ (A^1)_{i,j} = (A^1)_{i,j} \rightarrow O(1) \\ (A^2)_{i,j} = \sum_{k=1}^n (A^1)_{i,k} (A^1)_{k,j} \rightarrow O(n) \\ (A^3)_{i,j} = \sum_{k=1}^n (A^2)_{i,k} (A^2)_{k,j} =\sum_{k=1}^n \left(\sum_{l=1}^n A_{i,l} A_{l,k} \right) \left(\sum_{l=1}^n A_{k,l} A_{l,j} \right) \rightarrow O(n^2) \\ $$
So at least for $n=1,2$ we have complexity significantly lower than by approach 1. Using memoization, the recursive algorithm admits the probably fastest elementary approach to the problem, though I doubt that it'll perform faster than $O(k^3 n)$ in the end.
- Using the generating function:
Discrete mathematics tells us that $$f(x) = \sum_{n\ge 0}(A^n)_{i,j} x^n = (-1)^{i+j}\frac{\det((I-Ax)^{(j,i)})}{\det(I-Ax)\qquad\,}$$
However, just calculating those characteristic polynomials is in $O(k^4)$ (and I don't know how expensive calculating $[x^n] f(x)$ actually is)