Computing very high powers of a particular Jordan block Let $J$ be the following $k-by-k$ Jordan block:
$$
J:=
\begin{bmatrix}
e^{i \theta} & 1 & \\
 & e^{i \theta} & 1 \\
 & & \ddots & \ddots \\
 & & & \ddots & 1 \\
 & & & & e^{i \theta}
\end{bmatrix}.
$$
Is there an efficient way to compute the action of large powers of $J$, ie:
$$J^n x$$
to within tolerance $\epsilon$, when $n$ is extremely large? 
Notes,


*

*The goal is to find a computational procedure $f_n$, so that $||f_n(x)-J^nx||<\epsilon$ for all $x$, and computing $f_n(x)$ takes (significantly) less work than iteratively applying $J$ over and over.

*Feel free to make $n$ depend on $k$ and $\epsilon$ and let $n$ it be as large as you want - I'm interested in the asymptotic behavior.

*$\theta/2\pi$ could be irrational

 A: I do not see much problem. Write $J = e^{i \theta} I \; + \; K,$ where $I$ is the identity matrix and $K$ is the matrix of $1$'s just above the main diagonal. The point, of course, is that $KI = IK = K$ and $K^k = 0.$ So 
$$  (e^{i \theta} I  +  K)^n =  \sum_{w = 0}^{k-1}  \; \binom{n}{w}  e^{i (n-w) \theta} \; K^w  $$
where $K^0 = I.$
I almost used $N$ for the nilpotent part but felt $K$ worked better here. Note that the nonzero entries in $K^w$ are $1$'s in postions $ij,$ meaning row $i$ and column $j,$ with $1 \leq i \leq k - w$ and $j = i + w.$ So these are parallel to the main diagonal. By the time we get to $w= k-1,$ the only nonzero entry in $K^{k-1}$ is a single $1$ in position $1k.$ And then $K^k =0.$ So, for what it may be worth, the recipe above gives an explicit value for each of the relevant $(k^2 + k)/2$ nonzero entries. How you feel about the potential accuracy of these individual entries, $ \binom{n}{w}  e^{i (n-w) \theta}, $ is another matter, as the binomial coefficient may be huge.  
On the note of accuracy, I did want to indicate my answer at this one $\sin(A)$, where $A$ is a matrix , mention the gerbils, but also mention the comment underneath with an article about numerically dubious ways to find $e^A$ for a square matrix $A.$ I think the message is that you match methods to needs. See pdf at DUBIOUS 
