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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communitySuppose 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?