Fast Interpolation-based Globality Certificates for Computing Kreiss\n Constants and the Distance to Uncontrollability

We propose a new approach to computing global minimizers of singular value\nfunctions in two real variables. Specifically, we present new algorithms to\ncompute the Kreiss constant of a matrix and the distance to uncontrollability\nof a linear control system, both to arbitrary accuracy. Previous\nstate-of-the-art methods for these two quantities rely on 2D level-set tests\nthat are based on solving large eigenvalue problems. Consequently, these\nmethods are costly, i.e., $\\mathcal{O}(n^6)$ work using dense eigensolvers, and\noften multiple tests are needed before convergence. Divide-and-conquer\ntechniques have been proposed that reduce the work complexity to\n$\\mathcal{O}(n^4)$ on average and $\\mathcal{O}(n^5)$ in the worst case, but\nthese variants are nevertheless still very expensive and can be numerically\nunreliable. In contrast, our new interpolation-based globality certificates\nperform level-set tests by building interpolant approximations to certain\none-variable continuous functions that are both relatively cheap and\nnumerically robust to evaluate. Our new approach has a $\\mathcal{O}(kn^3)$ work\ncomplexity and uses $\\mathcal{O}(n^2)$ memory, where $k$ is the number of\nfunction evaluations necessary to build the interpolants. Not only is this\ninterpolation process mostly "embarrassingly parallel," but also low-fidelity\napproximations typically suffice for all but the final interpolant, which must\nbe built to high accuracy. Even without taking advantage of the aforementioned\nparallelism, $k$ is sufficiently small that our new approach is generally\norders of magnitude faster than the previous state-of-the-art.\n

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.