  We establish the first globally convergent algorithms for computing the
Kreiss constant of a matrix to arbitrary accuracy. We propose three different
iterations for continuous-time Kreiss constants and analogues for discrete-time
Kreiss constants. With standard eigensolvers, the methods do $\mathcal{O}(n^6)$
work, but we show how this theoretical work complexity can be lowered to
$\mathcal{O}(n^4)$ on average and $\mathcal{O}(n^5)$ in the worst case via
divide-and-conquer variants. Finally, locally optimal Kreiss constant
approximations can be efficiently obtained for large-scale matrices via
optimization.
