An Algorithm for Checking Regularity of Interval Matrices
Authors:
- Christian JanssonCJChristian Jansson
- Jiri RohnJRJiri Rohn
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 20 (3) , 756-776
Abstract
Checking regularity (or singularity) of interval matrices is a known NP-hard problem. In this paper a general algorithm for checking regularity/singularity is presented which is not a priori exponential. The algorithm is based on a theoretical result according to which regularity may be judged from any single component of the solution set of an associated system of linear interval equations. Numerical experiments (with interval matrices up to the size n = 50) confirm that this approach brings an essential decrease in the amount of operations needed.Keywords
This publication has 15 references indexed in Scilit:
- Computational Complexity and Feasibility of Data Processing and Interval Computations1998
- Bounds for the Componentwise Distance to the Nearest Singular MatrixSIAM Journal on Matrix Analysis and Applications, 1997
- Calculation of exact bounds for the solution set of linear interval systemsLinear Algebra and its Applications, 1997
- Interval P-MatricesSIAM Journal on Matrix Analysis and Applications, 1996
- Checking robust nonsingularity of tridiagonal matrices in linear timeBIT Numerical Mathematics, 1996
- Positive Definiteness and Stability of Interval MatricesSIAM Journal on Matrix Analysis and Applications, 1994
- Several NP-hard problems arising in robust stability analysisMathematics of Control, Signals, and Systems, 1993
- Checking robust nonsingularity is NP-hardMathematics of Control, Signals, and Systems, 1993
- Systems of linear interval equationsLinear Algebra and its Applications, 1989
- Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sidesNumerische Mathematik, 1964