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?

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?