Convert Frobenius canonical form to Jordan canonical form recently I've come across a few cases where I had to evaluate $e^{At}$ (differential equations) where A is in Frobenius canonical form. The algorithm looks like:
$$e^{At} = Pe^{Jt}P^{-1}$$ so I need to do Jordan decomposition. From Frobenius canonical form I can easily write the characteristic equation => compute the roots which are eigenvalues and write the Jordan canonical form.
This was the easy part. Now the other part: compute matrices $P$ and $P^{-1}$.
Is there any standard form of those matrices if matrix A is in a Frobenius canonical form?
 A: 
The matrix P is the matrix of coefficients of certain divisors of the characteristic polynomial of the Frobenius canonical form.

In fact this works for any companion matrix, not just the companion matrix of a power of an irreducible polynomial.
Suppose a matrix A has 1s above the diagonal, and the last row is [ v0, v1, v2, v3, ..., vn ], so
$$ A = \begin{bmatrix}
0 & 1 & 0 & 0 & \ldots & 0 & 0 \\
0 & 0 & 1 & 0 & \ldots & 0 & 0 \\
0 & 0 & 0 & 1 & \ldots & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & 0 & \ldots & 1 & 0 \\
0 & 0 & 0 & 0 & \ldots & 0 & 1 \\
v_0 & v_1 & v_2 & v_3 & \ldots & v_{n-1} & v_n \\
\end{bmatrix}.$$  Then
$$ A^{(n+1)} = v_0 A^0 + v_1 A^1 + v_2 A^2 + \ldots + v_n A^n$$
Suppose $x-\alpha$ is a factor of
$$
f(x) = x^{(n+1)} - v_n x^n - \ldots - v_1 x^1 - v_0 x^0
$$
and write
$$
f(x)/(x-\alpha) = w_n x^n + w_{n-1} x^{(n-1)} + \ldots + w_1 x^1 + w_0 x^0
$$
where of course $w_n = 1$.  Then
$w = [ w_0, w_1, w_2, \ldots, w_n ]$ is a left eigenvector of A, since $wA = \alpha w$.
In more detail, $$wA = [ v_0, w_0 + v_1, w_1 + v_2, \ldots, w_{n-1} + v_n ]$$
and
$$f(x) = (x-\alpha)( w_n x^n + w_{n-1} x^{(n-1)} + \ldots + w_1 x^1 + w_0 x^0)
= x^{n+1} - (-\alpha+w_{n-1}) x^{n} \ldots$$
so by equating coefficients of $x^n$, one gets $v_n = \alpha - w_{n-1}$ and $v_n + w_{n-1} = \alpha w_n$.  Similarly, $v_{n-1} = \alpha w_{n-1} - w_{n-2}$, and in general $v_i = \alpha w_i - w_{i-1}$ so $v_i + w_{i-1} = \alpha w_i$ and $wA = \alpha w$.
Something similar works with repeated roots even, to give you Jordan blocks.
So to find your matrix P, find each root α of f(x) with multiplicity k, and then the rows of P are the coefficients (in increasing order of power of x) of f(x)/(x−α)i, from i=1 to k, with corresponding diagonal entry of the matrix just being α, and the run from 1 to k forming the Jordan block.

Example 1
Find the JCF of
$$A = \begin{bmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\-1&4&-6&4\end{bmatrix}$$
The characteristic polynomial is just $f(x) = x^4-4x^3+6x^2-4x+1$ since it is a companion matrix of $f$.  Of course, $f(x) = (x-1)^4$ is easy to factor.
We calculate 
$$f(x)/(x-1) = 1x^3 - 3x^2 + 3x - 1,$$
$$f(x)/(x-1)^2 = 0x^3+1x^2-2x+1,$$
$$f(x)/(x-1)^3 = 0x^3+0x^2+x-1,\text{ and}$$
$$f(x)/(x-1)^4 = 0x^3+0x^2+0x+1.$$
We then write down the coefficients (in reverse order, I guess):
$$P = \begin{bmatrix} -1 & 3 & -3 & 1 \\ 1 & -2 & 1 & 0 \\ -1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$
so that
$$ P A P^{-1} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \end{bmatrix}$$
