Complexity of the LTI system trajectory boundedness problem
(2021) 2021 60th IEEE Conference on Decision and Control (CDC) — Location: Virtual (13.December.2021)
Files
Complexity_of_the_LTI_system_trajectory_boundedness_problem.pdf
Open Access - Adobe PDF
- 362.8 KB
Details
- Authors
- Abstract
- We study the algorithmic complexity of the problem of deciding whether a Linear Time Invariant dynamical system with rational coefficients has bounded trajectories. Despite its ubiquitous and elementary nature in Systems and Control, it turns out that this question is quite intricate, and, to the best of our knowledge, unsolved in the literature. We show that classical tools, such as Gaussian Elimination, the Routh--Hurwitz Criterion, and the Euclidean Algorithm for GCD of polynomials indeed allow for an algorithm that is polynomial in the bit size of the instance. However, all these tools have to be implemented with care, and in a non-standard way, which relies on an advanced analysis.
- Affiliations
Citations
Berger, G., & Jungers, R. (2021). Complexity of the LTI system trajectory boundedness problem. Published. 2021 60th IEEE Conference on Decision and Control (CDC), Virtual.