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

What is the best algorithm to compute its Jordan decomposition? What would the dependence on $n$ be?