We study the problem of computing the maximal and minimal possible eigenvalues of a symmetric matrix when the matrix entries vary within compact intervals. In particular, we focus on computational complexity of determining these extremal eigenvalues with some approximation error. Besides the classical absolute and relative approximation errors, which turn out not to be suitable for this problem, we adapt a less known one related to the relative error, and also propose a novel approximation error. We show in which error factors the problem is polynomially solvable and in which factors it becomes NP-hard.
@article{bwmeta1.element.doi-10_1515_math-2015-0015,
author = {Milan Hlad\'\i k},
title = {Complexity issues for the symmetric interval eigenvalue problem},
journal = {Open Mathematics},
volume = {13},
year = {2015},
zbl = {1309.65040},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_1515_math-2015-0015}
}
Milan Hladík. Complexity issues for the symmetric interval eigenvalue problem. Open Mathematics, Tome 13 (2015) . http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_1515_math-2015-0015/
[1] R. E. Moore, R. B. Kearfott, and M. J. Cloud, Introduction to interval analysis. Philadelphia, PA: SIAM, 2009. | Zbl 1168.65002
[2] A. Neumaier, Interval methods for systems of equations. Cambridge: Cambridge University Press, 1990. | Zbl 0715.65030
[3] V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl, Computational complexity and feasibility of data processing and interval computations. Kluwer, 1998. | Zbl 0945.68077
[4] J. Rohn, “Checking properties of interval matrices,” Technical Report 686, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 1996.
[5] J. Rohn, “A handbook of results on interval linear problems,” Technical Report 1163, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2012.
[6] D. Hertz, “The extreme eigenvalues and stability of real symmetric interval matrices,” IEEE Trans. Autom. Control, vol. 37, no. 4, pp. 532–535, 1992. [Crossref]
[7] M. Hladík, D. Daney, and E. P. Tsigaridas, “Characterizing and approximating eigenvalue sets of symmetric interval matrices,” Comput. Math. Appl., vol. 62, no. 8, pp. 3152–3163, 2011. [WoS][Crossref] | Zbl 1232.65060
[8] Y. Becis-Aubry and N. Ramdani, “State-bounding estimation for nonlinear models with multiple measurements,” in American Control Conference (ACC 2012), (Montréal, Canada), pp. 1883–1888, IEEE Computer Society, 2012.
[9] M. S. Darup, M. Kastsian, S. Mross, and M. Mönnigmann, “Efficient computation of spectral bounds for hessian matrices on hyperrectangles for global optimization,” J. Glob. Optim., pp. 1–22, 2013. DOI: 10.1007/s10898-013-0099-1. [WoS][Crossref] | Zbl 1338.90325
[10] M. Hladík, D. Daney, and E. Tsigaridas, “Bounds on real eigenvalues and singular values of interval matrices,” SIAM J. Matrix Anal. Appl., vol. 31, no. 4, pp. 2116–2129, 2010. [Crossref][WoS] | Zbl 1203.65076
[11] L. V. Kolev, “Outer interval solution of the eigenvalue problem under general form parametric dependencies,” Reliab. Comput., vol. 12, no. 2, pp. 121–140, 2006. | Zbl 1085.65032
[12] L. V. Kolev, “Determining the positive definiteness margin of interval matrices,” Reliab. Comput., vol. 13, no. 6, pp. 445–466, 2007. [WoS] | Zbl 1154.65025
[13] M.-H. Matcovschi and O. Pastravanu, “A generalized Hertz-type approach to the eigenvalue bounds of complex interval matrices,” in IEEE 51st Annual Conference on Decision and Control (CDC 2012), (Hawaii, USA), pp. 2195–2200, IEEE Computer Society, 2012.
[14] O. Beaumont, “An algorithm for symmetric interval eigenvalue problem,” Tech. Rep. IRISA-PI-00-1314, Institut de recherche en informatique et systèmes aléatoires, Rennes, France, 2000.
[15] M. Hladík, D. Daney, and E. P. Tsigaridas, “A filtering method for the interval eigenvalue problem,” Appl. Math. Comput., vol. 217, no. 12, pp. 5236–5242, 2011. [WoS] | Zbl 1221.65095
[16] J. Rohn, “An algorithm for checking stability of symmetric interval matrices,” IEEE Trans. Autom. Control, vol. 41, no. 1, pp. 133–136, 1996. [Crossref] | Zbl 0842.93057
[17] Q. Yuan, Z. He, and H. Leng, “An evolution strategy method for computing eigenvalue bounds of interval matrices,” Appl. Math. Comput., vol. 196, no. 1, pp. 257–265, 2008. [WoS] | Zbl 1133.65021
[18] S. Miyajima, T. Ogita, S. Rump, and S. Oishi, “Fast verification for all eigenpairs in symmetric positive definite generalized eigenvalue problems,” Reliab. Comput., vol. 14, pp. 24–45, 2010.
[19] S. M. Rump, “Verification methods: Rigorous results using floating-point arithmetic,” Acta Numer., vol. 19, pp. 287–449, 2010. [WoS][Crossref] | Zbl 1323.65046
[20] J. Rohn, “Checking positive definiteness or stability of symmetric interval matrices is NP-hard,” Commentat. Math. Univ. Carol., vol. 35, no. 4, pp. 795–797, 1994. | Zbl 0818.65032
[21] A. Nemirovskii, “Several NP-hard problems arising in robust stability analysis,” Math. Control Signals Syst., vol. 6, no. 2, pp. 99–105, 1993. | Zbl 0792.93100
[22] J. Rohn, “Interval matrices: Singularity and real eigenvalues,” SIAM J. Matrix Anal. Appl., vol. 14, no. 1, pp. 82–91, 1993. | Zbl 0769.15004
[23] V. Kreinovich, “How to define relative approximation error of an interval estimate: A proposal,” Appl. Math. Sci., vol. 7, no. 5, pp. 211–216, 2013.
[24] I. C. F. Ipsen, “Relative perturbation results for matrix eigenvalues and singular values,” Acta Numer., vol. 7, pp. 151–201, 1998. [Crossref] | Zbl 0916.15008
[25] J. Rohn, “Computing the norm kAk1;1 is NP-hard,” Linear Multilinear Algebra, vol. 47, no. 3, pp. 195–204, 2000. | Zbl 0964.65049
[26] G. H. Golub and C. F. Van Loan, Matrix computations. Baltimore: Johns Hopkins University Press, 3rd ed., 1996. | Zbl 0865.65009