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
-

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
Wow. I actually did that decomposition and wrote down that formula, but didn't think to eliminate the terms $j>k$. Thank you. I'm going to think about it a little bit and then when I've thought it over fully I'll award the bounty. –  Nick Alger Oct 1 '12 at 5:27