Complexity of computing interval matrix powers for special classes of matrices

David Hartman; Milan Hladík

Applications of Mathematics (2020)

  • Volume: 65, Issue: 5, page 645-663
  • ISSN: 0862-7940

Abstract

top
Computing powers of interval matrices is a computationally hard problem. Indeed, it is NP-hard even when the exponent is 3 and the matrices only have interval components in one row and one column. Motivated by this result, we consider special types of interval matrices where the interval components occupy specific positions. We show that computing the third power of matrices with only one column occupied by interval components can be solved in cubic time; so the asymptotic time complexity is the same as for the real case (considering the textbook matrix product method). We further show that for a fixed exponent k and for each interval matrix (of an arbitrary size) whose k th power has components that can be expressed as polynomials in a fixed number of interval variables, the computation of the k th power is polynomial up to a given accuracy. Polynomiality is shown by using the Tarski method of quantifier elimination. This result is used to show the polynomiality of computing the cube of interval band matrices, among others. Additionally, we study parametric matrices and prove NP-hardness already for their squares. We also describe one specific class of interval parametric matrices that can be squared by a polynomial algorithm.

How to cite

top

Hartman, David, and Hladík, Milan. "Complexity of computing interval matrix powers for special classes of matrices." Applications of Mathematics 65.5 (2020): 645-663. <http://eudml.org/doc/297056>.

@article{Hartman2020,
abstract = {Computing powers of interval matrices is a computationally hard problem. Indeed, it is NP-hard even when the exponent is 3 and the matrices only have interval components in one row and one column. Motivated by this result, we consider special types of interval matrices where the interval components occupy specific positions. We show that computing the third power of matrices with only one column occupied by interval components can be solved in cubic time; so the asymptotic time complexity is the same as for the real case (considering the textbook matrix product method). We further show that for a fixed exponent $k$ and for each interval matrix (of an arbitrary size) whose $k$th power has components that can be expressed as polynomials in a fixed number of interval variables, the computation of the $k$th power is polynomial up to a given accuracy. Polynomiality is shown by using the Tarski method of quantifier elimination. This result is used to show the polynomiality of computing the cube of interval band matrices, among others. Additionally, we study parametric matrices and prove NP-hardness already for their squares. We also describe one specific class of interval parametric matrices that can be squared by a polynomial algorithm.},
author = {Hartman, David, Hladík, Milan},
journal = {Applications of Mathematics},
keywords = {matrix power; interval matrix; interval computations; NP-hardness},
language = {eng},
number = {5},
pages = {645-663},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Complexity of computing interval matrix powers for special classes of matrices},
url = {http://eudml.org/doc/297056},
volume = {65},
year = {2020},
}

TY - JOUR
AU - Hartman, David
AU - Hladík, Milan
TI - Complexity of computing interval matrix powers for special classes of matrices
JO - Applications of Mathematics
PY - 2020
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 5
SP - 645
EP - 663
AB - Computing powers of interval matrices is a computationally hard problem. Indeed, it is NP-hard even when the exponent is 3 and the matrices only have interval components in one row and one column. Motivated by this result, we consider special types of interval matrices where the interval components occupy specific positions. We show that computing the third power of matrices with only one column occupied by interval components can be solved in cubic time; so the asymptotic time complexity is the same as for the real case (considering the textbook matrix product method). We further show that for a fixed exponent $k$ and for each interval matrix (of an arbitrary size) whose $k$th power has components that can be expressed as polynomials in a fixed number of interval variables, the computation of the $k$th power is polynomial up to a given accuracy. Polynomiality is shown by using the Tarski method of quantifier elimination. This result is used to show the polynomiality of computing the cube of interval band matrices, among others. Additionally, we study parametric matrices and prove NP-hardness already for their squares. We also describe one specific class of interval parametric matrices that can be squared by a polynomial algorithm.
LA - eng
KW - matrix power; interval matrix; interval computations; NP-hardness
UR - http://eudml.org/doc/297056
ER -

References

top
  1. Ahn, H.-S., Moore, K. L., Chen, Y. Q., Iterative Learning Control: Robustness and Monotonic Convergence for Interval Systems, Communications and Control Engineering. Springer, London (2007),9999DOI99999 10.1007/978-1-84628-859-3 . (2007) Zbl1162.93025MR2375210
  2. Buck, R. C., Partition of space, Am. Math. Mon. 50 (1943), 541-544 9999DOI99999 10.1080/00029890.1943.11991447 . (1943) Zbl0061.30609MR0009119
  3. Černý, M., Hladík, M., The complexity of computation and approximation of the t -ratio over one-dimensional interval data, Comput. Stat. Data Anal. 80 (2014), 26-43 9999DOI99999 10.1016/j.csda.2014.06.007 . (2014) Zbl06984073MR3240473
  4. Collins, G. E., 10.1007/978-3-7091-9459-1_4, Quantifier Elimination and Cylindrical Algebraic Decomposition Texts and Monographs in Symbolic Computation. Springer, Wien (1998), 85-121. (1998) Zbl0900.03055MR1634190DOI10.1007/978-3-7091-9459-1_4
  5. Edelsbrunner, H., Guibas, L. J., 10.1016/0022-0000(89)90038-X, J. Comput. Syst. Sci. 38 (1989), 165-194. (1989) Zbl0676.68013MR0990055DOI10.1016/0022-0000(89)90038-X
  6. Garloff, J., Popova, E. D., Smith, A. P., 10.1007/978-1-4614-5131-0_19, Optimization, Simulation, and Control Springer Optimization and Its Applications 76. Springer, New York (2013), 301-318. (2013) Zbl1311.65033MR3929639DOI10.1007/978-1-4614-5131-0_19
  7. Garloff, J., Smith, A. P., Preface (Special issue on the use of Bernstein polynomials in reliable computing: A centennial anniversary), Reliab. Comput. 17 (2012), i--vii. (2012) MR3035665
  8. Goldsztejn, A., Neumaier, A., On the exponentiation of interval matrices, Reliab. Comput. 20 (2014), 53-72. (2014) MR3268402
  9. Hansen, E. R., 10.1023/A:1009917818868, Reliab. Comput. 3 (1997), 17-29. (1997) Zbl0881.65032MR1614399DOI10.1023/A:1009917818868
  10. Hartman, D., Hladík, M., 10.1007/978-3-319-31769-4_9, Scientific Computing, Computer Arithmetic, and Validated Numerics Lecture Notes in Computer Science 9553. Springer, Cham (2016), 109-115. (2016) Zbl1354.65081MR3516767DOI10.1007/978-3-319-31769-4_9
  11. Hartman, D., Hladík, M., 10.13001/1081-3810.3749, Electron. J. Linear Algebra 33 (2018), 122-136. (2018) Zbl07007507MR3962259DOI10.13001/1081-3810.3749
  12. Hartman, D., Hladík, M., Říha, D., Computing the spectral decomposition of interval matrices and a study on interval matrix power, Available at https://arxiv.org/abs/1912.05275. 
  13. Hladík, M., 10.1007/978-3-030-31041-7_16, Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications Studies in Computational Intelligence 835. Springer, Cham (2020), 295-310. (2020) DOI10.1007/978-3-030-31041-7_16
  14. Hladík, M., Černý, M., Rada, M., A new polynomially solvable class of quadratic optimization problems with box constraints, Available at https://arxiv.org/abs/1911.10877. 
  15. Kosheleva, O., Kreinovich, V., Mayer, G., Nguyen, H. T., 10.1145/1066677.1067007, SAC '05: Proceedings of the 2005 ACM Symposium on Applied Computing, Volume 2 ACM, New York (2005), 1449-1453. (2005) DOI10.1145/1066677.1067007
  16. Kreinovich, V., Lakeyev, A., Rohn, J., Kahl, P., 10.1007/978-1-4757-2793-7, Applied Optimization 10. Kluwer Academic Publishers, Dordrecht (1998). (1998) Zbl0945.68077MR1491092DOI10.1007/978-1-4757-2793-7
  17. Leroy, R., Convergence under subdivision and complexity of polynomial minimization in the simplicial Bernstein basis, Reliab. Comput. 17 (2012), 11-21 9999MR99999 3008243 . (2012) MR3008243
  18. Mayer, G., 10.1515/9783110499469, De Gruyter Studies in Mathematics 65. De Gruyter, Berlin (2017). (2017) Zbl1373.65036MR3726854DOI10.1515/9783110499469
  19. Moore, R. E., Kearfott, R. B., Cloud, M. J., 10.1137/1.9780898717716, SIAM, Philadelphia (2009). (2009) Zbl1168.65002MR2482682DOI10.1137/1.9780898717716
  20. Oppenheimer, E. P., Michel, A. N., 10.1109/31.7598, IEEE Trans. Circuits Syst. 35 (1988), 1230-1242. (1988) MR0960775DOI10.1109/31.7598
  21. Poljak, S., Rohn, J., 10.1007/BF01213466, Math. Control Signals Syst. 6 (1993), 1-9. (1993) Zbl0780.93027MR1358057DOI10.1007/BF01213466
  22. Rohn, J., 10.1080/03081080008818644, Linear Multilinear Algebra 47 (2000), 195-204. (2000) Zbl0964.65049MR1785027DOI10.1080/03081080008818644
  23. Skalna, I., 10.1007/978-3-319-75187-0, Studies in Computational Intelligence 766. Springer, Cham (2018). (2018) Zbl06999249MR3852878DOI10.1007/978-3-319-75187-0
  24. Skalna, I., Hladík, M., 10.1002/nla.2229, Numer. Linear Algebra Appl. 26 (2019), Article ID e2229, 24 pages. (2019) Zbl07088855MR3946064DOI10.1002/nla.2229
  25. Tarski, A., A Decision Method for Elementary Algebra and Geometry, RAND Corporation, Santa Monica, California (1948). (1948) Zbl0035.00602MR0028796
  26. Zhang, Y. M., Kovacevic, R., 10.1049/ip-cta:19971170, IEE Proc., Control Theory Appl. 144 (1997), 347-353. (1997) Zbl0885.93040DOI10.1049/ip-cta:19971170

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.