  We study the bit complexity of two related fundamental computational problems
in linear algebra and control theory. Our results are: (1) An
$\tilde{O}(n^{\omega+3}a+n^4a^2+n^\omega\log(1/\epsilon))$ time algorithm for
finding an $\epsilon-$approximation to the Jordan Normal form of an integer
matrix with $a-$bit entries, where $\omega$ is the exponent of matrix
multiplication. (2) An $\tilde{O}(n^6d^6a+n^4d^4a^2+n^3d^3\log(1/\epsilon))$
time algorithm for $\epsilon$-approximately computing the spectral
factorization $P(x)=Q^*(x)Q(x)$ of a given monic $n\times n$ rational matrix
polynomial of degree $2d$ with rational $a-$bit coefficients having $a-$bit
common denominators, which satisfies $P(x)\succeq 0$ for all real $x$. The
first algorithm is used as a subroutine in the second one.
  Despite its being of central importance, polynomial complexity bounds were
not previously known for spectral factorization, and for Jordan form the best
previous best running time was an unspecified polynomial in $n$ of degree at
least twelve \cite{cai1994computing}. Our algorithms are simple and judiciously
combine techniques from numerical and symbolic computation, yielding
significant advantages over either approach by itself.
