Complexity issues for the symmetric interval eigenvalue problem

Milan Hladík

Open Mathematics (2015)

  • Volume: 13, Issue: 1, page 157-164, electronic only
  • ISSN: 2391-5455

Abstract

top
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.

How to cite

top

Milan Hladík. "Complexity issues for the symmetric interval eigenvalue problem." Open Mathematics 13.1 (2015): 157-164, electronic only. <http://eudml.org/doc/268861>.

@article{MilanHladík2015,
abstract = {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.},
author = {Milan Hladík},
journal = {Open Mathematics},
keywords = {Interval matrix; Interval analysis; Eigenvalue; Eigenvalue bounds; NP-hardness; interval matrix; interval analysis; eigenvalue; eigenvalue bounds; symmetric matrix; computational complexity; extremal eigenvalue},
language = {eng},
number = {1},
pages = {157-164, electronic only},
title = {Complexity issues for the symmetric interval eigenvalue problem},
url = {http://eudml.org/doc/268861},
volume = {13},
year = {2015},
}

TY - JOUR
AU - Milan Hladík
TI - Complexity issues for the symmetric interval eigenvalue problem
JO - Open Mathematics
PY - 2015
VL - 13
IS - 1
SP - 157
EP - 164, electronic only
AB - 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.
LA - eng
KW - Interval matrix; Interval analysis; Eigenvalue; Eigenvalue bounds; NP-hardness; interval matrix; interval analysis; eigenvalue; eigenvalue bounds; symmetric matrix; computational complexity; extremal eigenvalue
UR - http://eudml.org/doc/268861
ER -

References

top
  1. [1] R. E. Moore, R. B. Kearfott, and M. J. Cloud, Introduction to interval analysis. Philadelphia, PA: SIAM, 2009. Zbl1168.65002
  2. [2] A. Neumaier, Interval methods for systems of equations. Cambridge: Cambridge University Press, 1990. Zbl0715.65030
  3. [3] V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl, Computational complexity and feasibility of data processing and interval computations. Kluwer, 1998. Zbl0945.68077
  4. [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. [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. [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. [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] Zbl1232.65060
  8. [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. [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] Zbl1338.90325
  10. [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] Zbl1203.65076
  11. [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. Zbl1085.65032
  12. [12] L. V. Kolev, “Determining the positive definiteness margin of interval matrices,” Reliab. Comput., vol. 13, no. 6, pp. 445–466, 2007. [WoS] Zbl1154.65025
  13. [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. [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. [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] Zbl1221.65095
  16. [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] Zbl0842.93057
  17. [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] Zbl1133.65021
  18. [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. [19] S. M. Rump, “Verification methods: Rigorous results using floating-point arithmetic,” Acta Numer., vol. 19, pp. 287–449, 2010. [WoS][Crossref] Zbl1323.65046
  20. [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. Zbl0818.65032
  21. [21] A. Nemirovskii, “Several NP-hard problems arising in robust stability analysis,” Math. Control Signals Syst., vol. 6, no. 2, pp. 99–105, 1993. Zbl0792.93100
  22. [22] J. Rohn, “Interval matrices: Singularity and real eigenvalues,” SIAM J. Matrix Anal. Appl., vol. 14, no. 1, pp. 82–91, 1993. Zbl0769.15004
  23. [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. [24] I. C. F. Ipsen, “Relative perturbation results for matrix eigenvalues and singular values,” Acta Numer., vol. 7, pp. 151–201, 1998. [Crossref] Zbl0916.15008
  25. [25] J. Rohn, “Computing the norm kAk1;1 is NP-hard,” Linear Multilinear Algebra, vol. 47, no. 3, pp. 195–204, 2000. Zbl0964.65049
  26. [26] G. H. Golub and C. F. Van Loan, Matrix computations. Baltimore: Johns Hopkins University Press, 3rd ed., 1996. Zbl0865.65009

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.