Checking robust nonsingularity is NP-hard

DOI10.1007/BF01213466zbMath0780.93027OpenAlexW2022602688WikidataQ92958254 ScholiaQ92958254MaRDI QIDQ1802197

Publication date: 26 January 1994

Published in: MCSS. Mathematics of Control, Signals, and Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01213466

zbMATH Keywords

interval matrices robust nonsingularity radius of nonsingularity

Mathematics Subject Classification ID

Sensitivity (robustness) (93B35)

Related Items

A probabilistic framework for problems with real structured uncertainty in systems and control, Regularity radius and real eigenvalue range, The P-matrix problem is co-NP-complete, Radii of solvability and unsolvability of linear systems, On the stability of a convex set of matrices, Helly-type theorems and generalized linear programming, A survey of randomized algorithms for control synthesis and performance verification, Enclosing solutions of linear interval equations is NP-hard, Worst-case and average \(\mathcal{H}_2\) performance analysis against real constant parametric uncertainty, Inversion error, condition number, and approximate inverses of uncertain matrices, Checking bounds on solutions of linear interval equations is NP-hard, The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix, Characteristic polynomial assignment for plants with semialgebraic uncertainty: A robust diophantine equation approach, Static output feedback -- a survey, Complexity issues in robust stability of linear delay-differential systems, Real eigenvalue bounds of standard and generalized real interval eigenvalue problems, On Relation Between P-Matrices and Regularity of Interval Matrices, On distributional robustness of systems with complex uncertainty, A bright side of NP-hardness of interval computations: Interval heuristics applied to NP-problems, Approximate linear algebra is intractable, Minimum phase robustness for uncertain state-space systems, Theorems of Perron-Frobenius type for matrices without sign restrictions, Checking robust nonsingularity of tridiagonal matrices in linear time, Mixed robustness: analysis of systems with uncertain deterministic and random parameters by the example of linear systems, Verified inclusions for a nearest matrix of specified rank deficiency via a generalization of Wedin's \(\sin (\theta)\) theorem, Guardian map approach to robust stability of interval systems, On computational complexity of invalidating structured uncertainty models, On the complexity of the robust stability problem for linear parameter varying systems, Relations between various methods for solving linear interval and parametric equations, Generalized eigenvalue for even order tensors via Einstein product and its applications in multilinear control systems, A note on checking regularity of interval matrices, Performance and accuracy of the basic closure algorithm of quadrature-based moment methods, Sufficient regularity conditions for complex interval matrices and approximations of eigenvalues sets, On real structured controllability/stabilizability/stability radius: complexity and unified rank-relaxation based methods, An algorithm for addressing the real interval eigenvalue problem, Computing nearby non-trivial Smith forms, A note on regularity and positive definiteness of interval matrices, How to determine basis stability in interval linear programming, Almost Sharp Bounds for the Componentwise Distance to the Nearest Singular Matrix, Fast interval matrix multiplication, A nonlinear programming technique to compute a~tight~lower bound for the real structured singular value, Complexity of computing interval matrix powers for special classes of matrices., Tolerances, robustness and parametrization of matrix properties related to optimization problems, Structured singular value approach for systems with parametric uncertainty, Strong NP-completeness of a matrix similarity problem, Computing the spectral decomposition of interval matrices and a study on interval matrix powers, Branch and bound algorithm with applications to robust stability, Nonsingularity, positive definiteness, and positive invertibility under fixed-point data rounding., A survey of computational complexity results in systems and control, A theorem of the alternatives for the equationAx+B|x| =b, Rank one interval enclosure of the parametric united solution set, A theorem of the alternatives for the equation \(|Ax|-|B||x|=b\), On the computation of structured singular values and pseudospectra, On solving vague systems of linear equations with pattern-shaped columns, Positively regular vague matrices, Worst‐case stability and performance with mixed parametric and dynamic uncertainties, On the complexity of matrix rank and rigidity, Randomized algorithms for robust controller synthesis using statistical learning theory, Probabilistic solutions to some NP-hard matrix problems, Low-rank matrix approximation in the infinity norm, Linear interval parametric approach to testing pseudoconvexity, Computing lower rank approximations of matrix polynomials, Calculation of exact bounds for the solution set of linear interval systems, Verified error bounds for multiple roots of systems of nonlinear equations, Monte Carlo and Las Vegas randomized algorithms for systems and control. An introduction, Randomized algorithms for robust controller synthesis using statistical learning theory: a tutorial overview, Tight Bounds on the Radius of Nonsingularity, Letter to the editor, A survey of extreme point results for robustness of control systems, A new vertex result for robustness problems with interval matrix uncertainty, Discussion on: ``Why is resorting to fate wise? A critical look at randomized algorithms in systems and control, Stability of the linear complementarity problem properties under interval uncertainty, Regularity radius: Properties, approximation and a not a priori exponential algorithm, On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation, Worst-case properties of the uniform distribution and randomized algorithms for robustness analysis, Componentwise pseudospectrum of a matrix, The maximum row length nonsingularity radius, Eigenvectors of interval matrices over max--plus algebra, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, How strong is strong regularity?, The boundedness of all products of a pair of matrices is undecidable, A characterization of convex cones of matrices with constant regular inertia, Computing the norm ∥A∥∞,1 is NP-hard^∗, Linear Programming with Inexact Data is NP‐Hard, Several NP-hard problems arising in robust stability analysis, A pair of matrices sharing common Lyapunov solutions--A closer look, Regularity of interval matrices and theorems of the alternatives, Nonsmooth bundle trust-region algorithm with applications to robust stability, On \(P\)-matrices

Cites Work