CS Paper Radar

Exact Decisions and Certified Values in $L_\infty$-Norm Computation from State-Space Representations

Alban Quadrat, Fabrice Rouillier, Grace Younes

cs.SC math.OC ·submitted 2026-11-11 09:46 UTC · v1
benchmark

Abstract

Computing the $L_\infty$-norm of a time-invariant linear ordinary differential control system is a routine task in robust control, usually delegated to floating-point routines that perform well on most practical systems. Behind the numerical value, however, lies a discrete decision: whether a pole lies on the imaginary axis, and whether a mode of a realization is actually a pole of the transfer matrix. Floating-point arithmetic can only replace this decision with a tolerance. This paper explains, for a control audience, what reliable symbolic-numeric computation offers for this problem: exact arithmetic where a decision has to be made, and certified enclosures where a value has to be computed. We show how the problem is turned into a small polynomial system directly from state-space data, how this system is solved in practice, and what it costs. A benchmark on the {\tt COMPleib} library and on families of systems with known norms shows that two standard numerical routines err in opposite directions on the imaginary-axis decision, and never on the same system, while the certified method decides it correctly on every instance tested and computes the norm at a cost comparable to that of the numerical routines on most systems. We conclude with practical guidelines for users of numerical tools.

Comment
6 pages, 1 table. Submitted to the European Control Conference (ECC 2027)

Closest papers

Nearest neighbours by meaning across the whole index.

Floating-point, exact and certified computation for control: paradigms, pitfalls, and how to combine them

cs.SC ·2026-11-11 ·Christina Katsamaki, Fabrice Rouillier
similarity 0.71
Abstract

Many questions in linear systems theory have a discrete answer: is a polynomial Hurwitz, is a 2-D system structurally stable, is the peak gain finite, which solution of a Riccati equation is stabilizing? Algorithms implemented in floating point usually answer such questions, but often with a limited, or even no, guarantee on the result, which depends on a tolerance fixed a priori. Computer algebra and interval arithmetic provide other ways of computing, which give guarantees on the result, but usually at a higher cost. In this paper, we propose a short guide to these approaches: floating-point, exact, multiprecision and interval arithmetic, certified root isolation and certified Newton methods. Using small examples from control theory (each of them runs in a few seconds), we show what each approach guarantees and in which situations it fails, and how several approaches can be combined, for example by certifying a numerical solution, or by reducing a problem exactly before solving it with certified real solving. We then revisit the structural stability of 2-D systems (with and without parameters) and the computation of the $H_\infty$ norm, and we list the available implementations. The main examples are given as reproducible worksheets based on the PACE ecosystem.

0.32

One Polynomial Field for Every Euler Step and the Flow: Polynomial Dynamics for P and PSPACE

cs.CC cs.LOmath.DS ·2026-10-29 ·Olivier Bournez
similarity 0.57
Abstract · 93 pages. Ancillary files: exact local checks (Python 3, standard library only). v2: explicit horizon in Corollary 55, minor corrections

We construct, for each deterministic Turing machine that halts on all inputs, one polynomial vector field with rational coefficients that performs the same logical computation at unit Euler step, at every smaller or variable step in $(0,1]$ with divergent sum, and along the flow. This unifies discrete-time and continuous-time computation by polynomial dynamics, which earlier characterizations treated separately. For a machine making $T$ transitions in space $H$, a logical scale $h=2^{-s}$ with $s=O(H)$ suffices, with physical time $O(s(T+s))$, drift disturbances up to $h^{2K}$ for a fixed exponent $K$, and $2Ks+3$ fractional bits at unit step. On a fixed compact domain, polynomial time and robust eventual decision characterize P and PSPACE, respectively, with polynomial scale thresholds and no supplied stabilization horizon in the space case. Without sign, floor or conditional primitives, margin amplification at bounded speed, overlapping polynomial gates and interval-product estimates give the common realization, from which we derive shared logical traces, fixed-field PSPACE-complete prediction and a robust safety family with polynomial certificates common to all Euler steps and the flow.

0.30

PSPACE-Completeness of the Reachability Relation of Robust Dynamical Systems

cs.CC ·2026-10-19 ·Manon Blanc
theory similarity 0.56
Abstract

Dynamical systems are a widely used model of computation and an intuitive representation of many natural phenomena in many applied fields. The last decades have seen an impressive use of computers in studying and analysing them, with several visible theoretical breakthroughs. The question of reachability for dynamical systems is central: given two points, is there a trajectory between them in the dynamical system? Reachability, in particular over the reals, is undecidable in the general case: it is only computably enumerable, even under reasonable hypotheses, e.g. for a computable dynamics in general. But it is known to become decidable, and even lies in PSPACE, under suitably quantified robustness assumptions. In this paper, we focus on PSPACE-completeness results over the reals, in the sense of computable analysis, regarding discrete-time and continuous-time robust dynamical systems. We prove that, under some additional and rather reasonable hypotheses, the reachability relation becomes even PSPACE-complete for both classical and second-order complexity second-order complexity, for an adapted notion of reduction. As a side-effect, we also prove an improvement of an algebraic Ordinary Differential Equations-based characterisation of PSPACE, removing one of the base functions of the algebra. By doing so, we link results from dynamical systems and complexity over the reals, including the models of computable analysis and second-order complexity.

0.29

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations

cs.DS cs.CCmath.NA ·2026-09-29 ·Jonathan A. Kelner
similarity 0.56
Abstract

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $ε$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $κ$.

0.09

Reliable Computation of the $L_{\infty}$-Norm of Linear Time-Invariant Systems Depending on One Parameter

cs.SC ·2026-11-09 ·Florent Corniquel, Alban Quadrat, Fabrice Rouillier, Grace Younes
unusual similarity 0.56
Abstract

The $L_{\infty}$-norm of a linear time-invariant system is a central quantity in robust control, used in robust stability tests, stability margins, and $H_{\infty}$ controller design. Physical models depend on parameters, such as masses, stiffnesses, or gains, so the $L_{\infty}$-norm becomes a function of these parameters. This computation reduces to studying the real critical points of a plane algebraic curve whose coefficients depend on the parameters. Previous approaches based on cylindrical algebraic decomposition describe the $L_{\infty}$-norm on the whole parameter space, but their cost grows very quickly with the number of parameters. In this paper, we propose instead to compute a generic parametrisation of the solutions, valid outside an explicitly characterised set of non-generic parameter values. In the case of one parameter, this parametrisation is obtained by interpolation from a certified solver for the non-parametric case. The resulting algorithm is fully certified, relying on a priori bounds and multimodular computations rather than on Gröbner bases. It is illustrated on examples from the robust control literature.

0.34

FPScan: An Automated Constraint-Based Analyzer for Floating-Point Anomaly Detection

cs.SE math.NA ·2026-09-07 ·Julien Bortolussi, Dorra Ben Khalifa, Pierre-Loïc Garoche
benchmark similarity 0.55
Abstract · 12 pages , 7 Figures, 28th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

Writing error-free floating-point programs is a challenging task, especially for programmers who lack a strong background in numerical analysis and rounding-error propagation. State-of-the-art techniques typically aim to bound such errors using static or dynamic analysis. However, only a few tools explicitly address critical floating-point pitfalls such as absorption and catastrophic cancellation. These anomalies represent situations in which rounding errors are significantly amplified, causing the semantics of the finite-precision computation to deviate substantially from the real-number semantics. In this article, we present FPScan, a novel tool to formally define and detect both catastrophic cancellation and absorption in floating-point programs. Our approach starts with a custom static analyzer based on abstract interpretation to infer the order of magnitude of all program variables. This magnitude information is then used to build a set of first-order constraints that model error propagation and numerical precision within the program. Finally, we employ an off-the-shelf SMT solver to determine whether the program exhibits any of these critical numerical pitfalls. Experiments were conducted on FPBench, a well-known benchmark suite of floating-point programs, to evaluate the effectiveness of our tool. We also present a comparison with state-of-the-art tools regarding soundness and analysis time.

0.26

Algorithmic Cost in "Exact Real Computation"

cs.LO math.NAcs.PL ·2026-08-20 ·Jihoon Hyun, Holger Thies, Martin Ziegler
similarity 0.55
Abstract

Turing completeness of a programming language or system characterizes its expressive power; and the strong Church-Turing hypo-/thesis refines such from qualitative to polynomial-time equivalence. Exact Real Computation (ERC) is a novel numerical programming language paradigm: for the imperative processing of continuous data as entities appearing as exact, i.e. devoid of rounding errors [doi:10.1007/978-3-662-44199-2_107]. ERC has been designed [doi:10.46298/lmcs-20(2:17)2024] as convenient and practical alternative, namely proven qualitatively equivalent, to the Turing machines originally underlying Computable Analysis [doi:10.1007/978-3-642-56999-9,doi:10.1007/978-1-4684-6802-1]. The present work quantitatively strengthens this qualitative Turing-completeness: We assign bit-costs to ERC's operational primitives (including partial/multivalued tests) in such a way that any real function incurring polynomial cost becomes Turing-computable in polynomial time, and vice versa. Runtime measurements on implementations in the iRRAM C++ library confirm our theoretical performance predictions.

0.28

Data-to-Certificates (D2C): Koopman Supereigenfunctions for Stability, Safety, and Control

eess.SY math.OC ·2026-09-16 ·Umesh Vaidya
theory similarity 0.55
Abstract

Traditional dynamical system models, including Koopman operator representations, are fundamentally equality-based, whereas many analysis and control tools rely on inequalities. This mismatch motivates representations that are intrinsically aligned with certification tasks involved in the analysis and control synthesis problems. In this paper, we propose a \emph{data-to-certificates (D2C)} paradigm that bypasses explicit model construction and directly learns certificates from data. We introduce \emph{supereigenfunctions} of the Koopman operator as an inequality-based generalization of eigenfunctions that define exponential growth envelopes encoding stability, safety, and uncertainty propagation, thereby serving as certificates for a range of control objectives. We establish their theoretical foundations and show that the associated rates recover intrinsic dynamical quantities such as Lyapunov exponents. Two complementary constructions are developed: a geometric approach based on the multiplicative ergodic theorem (MET), and a resolvent/Gramian formulation that enables computation directly from trajectory data. The resulting framework yields certificates that can be used for stability and contraction analysis, as well as stabilizing and safety-critical control synthesis via convex quadratic programming-based optimization program. Numerical examples demonstrate the effectiveness of the proposed data-driven certification approach for stabilization, contraction, and safe control design.

0.22