×

Checking robust nonsingularity of tridiagonal matrices in linear time. (English) Zbl 0848.65029

It is known that the problem of checking regularity (i.e., robust nonsingularity) of interval matrices is NP-hard [cf. S. Poljak and J. Rohn, Math. Control Signals Syst. 6, No. 1, 1-9 (1993; Zbl 0780.93027)]. In the present paper it is proved that for tridiagonal interval matrices regularity check can be performed by a linear time algorithm.
Reviewer: J.Rohn (Praha)

MSC:

65F30 Other matrix algorithms (MSC2010)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65G30 Interval and finite arithmetic

Citations:

Zbl 0780.93027

Software:

Algorithm 694
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] I. Bar-On and M. Leoncini,Reliable sequential algorithms for solving bidiagonal systems of linear equations, submitted. · Zbl 0997.65048
[2] A. Deif,Sensitivity Analysis in Linear Systems, Springer-Verlag, 1986. · Zbl 0624.65019
[3] G. Alefeld and J. Herzberger,Introduction to Interval Computations, Academic Press, New York, 1983. · Zbl 0552.65041
[4] G. H. Golub and C. F. V. Loan,Matrix Computations 2nd ed., The Johns Hopkins University Press, Baltimore, 1989. · Zbl 0733.65016
[5] J. W. Demmel,On Condition Numbers and the distance to the nearest ill-posed problem, Numer. Math., 51 (1987), pp. 251–289. · Zbl 0597.65036
[6] J. W. Demmel,The Componentwise distance to the nearest singular matrix, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 10–19. · Zbl 0749.65031
[7] N. J. Higham,Bounding the error in Gaussian elimination for tridiagonal systems, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 521–530. · Zbl 0716.65025
[8] N. J. Higham,Algorithm 694: A collection of test matrices in MATLAB, ACM Trans. Math. Softw., 17 (1991), pp. 289–305. · Zbl 0900.65120
[9] W. Kahan,Numerical Linear Algebra, Canadian Math. Bull., 9 (1966), pp. 757–801. · Zbl 0236.65025
[10] J. C. Doyle,Analysis of feedback systems with structured uncertainties, in Proc. IEEE 129 (1982), pp. 242–250.
[11] K. Knopp,Elements of the Theory of Functions, Dover, New York, 1952. · Zbl 0048.30802
[12] M. Mansour,Robust stability of interval matrices, in Proceedings of the 28th Conference on Decision and Control, Tampa, FL, 1989, pp. 46–51.
[13] MATLAB,The Math Works, Inc., Natick, MA., 1994.
[14] A. Nemirovskii,Several NP-Hard problems arising in robust stability analysis, Mathematics of Control, Signals, and Systems, 6 (1993), pp. 99–105. · Zbl 0792.93100
[15] A. Neumaier,Interval Methods for Systems of Equations, Cambridge University Press, 1990. · Zbl 0715.65030
[16] W. Oettli and W. Prager,Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6 (1964), pp. 405–409. · Zbl 0133.08603
[17] S. Poljak and J. Rohn,Checking robust nonsingularity is NP-Hard, Mathematics of Control, Signals, and Systems, 6 (1993), pp. 1–9. · Zbl 0780.93027
[18] J. Rohn and V. Kreinovich,Computing exact componentwise bounds for the solution of linear systems with interval data is NP-Hard, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 415–420. · Zbl 0824.65011
[19] S. M. Rump,Bounds for the componentwise distance to the nearest singular matrix, Berichte 95.3, Technische Universität Hamburg, Germany, May 1995.
[20] R. Skeel,Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach., 26 (1979), pp. 494–526. · Zbl 0435.65035
[21] G. Stewart and J. Sun,Matrix Perturbation Theory, Academic Press, 1990. · Zbl 0706.65013
[22] J. H. Wilkinson,The Algebraic Eigenvalue Problem, Oxford University Press, 1965. Reprinted in Oxford Science Publications, 1988. · Zbl 0258.65037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.