Computational Mathematics and Scientific Computing Seminar

---

Computing the Kreiss Constant of a Matrix

Speaker: Tim Mitchell, Max Planck Institute, Magdeburg

Location: Warren Weaver Hall 1302

Date: Dec. 13, 2019, 10 a.m.

Synopsis:

The Kreiss constant of a square matrix bounds the transient behavior of its associated ordinary differential equation or difference equation. Introduced by H.-O. Kreiss in 1962, until recently no algorithm has been given to actually compute it, which is equivalent to solving certain global optimization problems. Local optimizers of these problems can be obtained relatively easily via standard optimization techniques, even for large-scale matrices, but the resulting estimates may be arbitrarily bad. In this talk, we present the first algorithms with theoretical guarantees for computing Kreiss constants, using two different approaches to ensure global convergence. Our first approach is inspired by state-of-the-art techniques for computing the distance to uncontrollability, which all trace back to a novel 2D level-set test developed by M. Gu in 2000. However, these methods are very expensive. In our second approach, we propose alternative level-set tests based on the idea of building interpolant approximations to certain one-variable distance functions. These newer level-set tests can be orders of magnitude faster to compute and seem to be more reliable in practice, thus enabling continuous- and discrete-time Kreiss constants and the distance to uncontrollability to be efficiently computed for much larger problems.