Suppose we are given $n\times n$ rational matrix, $A$ with at most $k$ nonzero elements in each row and each column with $k<<n$.

What is the best algorithm to compute its Jordan decompistion? What would the dependence of $n$ be?