Bit Complexity of Jordan Normal Form and Spectral Factorization

Papri Dey, Ravi Kannan, Nick Ryder +1

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^{ω+3}a+n^4a^2+n^ω\log(1/ε))…