Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
matrix power; interval matrix; interval computations; NP-hardness
matrix power; interval matrix; interval computations; NP-hardness
Summary:
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.
References:
[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),\99999DOI99999 10.1007/978-1-84628-859-3 . MR 2375210 | Zbl 1162.93025
[2] Buck, R. C.: Partition of space. Am. Math. Mon. 50 (1943), 541-544 \99999DOI99999 10.1080/00029890.1943.11991447 . MR 0009119 | Zbl 0061.30609
[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 \99999DOI99999 10.1016/j.csda.2014.06.007 . MR 3240473 | Zbl 06984073
[4] Collins, G. E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Quantifier Elimination and Cylindrical Algebraic Decomposition Texts and Monographs in Symbolic Computation. Springer, Wien (1998), 85-121. DOI 10.1007/978-3-7091-9459-1_4 | MR 1634190 | Zbl 0900.03055
[5] Edelsbrunner, H., Guibas, L. J.: Topologically sweeping an arrangement. J. Comput. Syst. Sci. 38 (1989), 165-194. DOI 10.1016/0022-0000(89)90038-X | MR 0990055 | Zbl 0676.68013
[6] Garloff, J., Popova, E. D., Smith, A. P.: Solving linear systems with polynomial parameter dependency with application to the verified solution of problems in structural mechanics. Optimization, Simulation, and Control Springer Optimization and Its Applications 76. Springer, New York (2013), 301-318. DOI 10.1007/978-1-4614-5131-0_19 | MR 3929639 | Zbl 1311.65033
[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. MR 3035665
[8] Goldsztejn, A., Neumaier, A.: On the exponentiation of interval matrices. Reliab. Comput. 20 (2014), 53-72. MR 3268402
[9] Hansen, E. R.: Sharpness in interval computations. Reliab. Comput. 3 (1997), 17-29. DOI 10.1023/A:1009917818868 | MR 1614399 | Zbl 0881.65032
[10] Hartman, D., Hladík, M.: Tight bounds on the radius of nonsingularity. Scientific Computing, Computer Arithmetic, and Validated Numerics Lecture Notes in Computer Science 9553. Springer, Cham (2016), 109-115. DOI 10.1007/978-3-319-31769-4_9 | MR 3516767 | Zbl 1354.65081
[11] Hartman, D., Hladík, M.: Regularity radius: Properties, approximation and a not a priori exponential algorithm. Electron. J. Linear Algebra 33 (2018), 122-136. DOI 10.13001/1081-3810.3749 | MR 3962259 | Zbl 07007507
[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.: An overview of polynomially computable characteristics of special interval matrices. Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications Studies in Computational Intelligence 835. Springer, Cham (2020), 295-310. DOI 10.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.: Computing the cube of an interval matrix is NP-hard. SAC '05: Proceedings of the 2005 ACM Symposium on Applied Computing, Volume 2 ACM, New York (2005), 1449-1453. DOI 10.1145/1066677.1067007
[16] Kreinovich, V., Lakeyev, A., Rohn, J., Kahl, P.: Computational Complexity and Feasibility of Data Processing and Interval Computations. Applied Optimization 10. Kluwer Academic Publishers, Dordrecht (1998). DOI 10.1007/978-1-4757-2793-7 | MR 1491092 | Zbl 0945.68077
[17] Leroy, R.: Convergence under subdivision and complexity of polynomial minimization in the simplicial Bernstein basis. Reliab. Comput. 17 (2012), 11-21 \99999MR99999 3008243 . MR 3008243
[18] Mayer, G.: Interval Analysis and Automatic Result Verification. De Gruyter Studies in Mathematics 65. De Gruyter, Berlin (2017). DOI 10.1515/9783110499469 | MR 3726854 | Zbl 1373.65036
[19] Moore, R. E., Kearfott, R. B., Cloud, M. J.: Introduction to Interval Analysis. SIAM, Philadelphia (2009). DOI 10.1137/1.9780898717716 | MR 2482682 | Zbl 1168.65002
[20] Oppenheimer, E. P., Michel, A. N.: Application of interval analysis techniques to linear systems. II. The interval matrix exponential function. IEEE Trans. Circuits Syst. 35 (1988), 1230-1242. DOI 10.1109/31.7598 | MR 0960775
[21] Poljak, S., Rohn, J.: Checking robust nonsingularity is NP-hard. Math. Control Signals Syst. 6 (1993), 1-9. DOI 10.1007/BF01213466 | MR 1358057 | Zbl 0780.93027
[22] Rohn, J.: Computing the norm $\|A\|_{\infty,1}$ is NP-hard. Linear Multilinear Algebra 47 (2000), 195-204. DOI 10.1080/03081080008818644 | MR 1785027 | Zbl 0964.65049
[23] Skalna, I.: Parametric Interval Algebraic Systems. Studies in Computational Intelligence 766. Springer, Cham (2018). DOI 10.1007/978-3-319-75187-0 | MR 3852878 | Zbl 06999249
[24] Skalna, I., Hladík, M.: Direct and iterative methods for interval parametric algebraic systems producing parametric solutions. Numer. Linear Algebra Appl. 26 (2019), Article ID e2229, 24 pages. DOI 10.1002/nla.2229 | MR 3946064 | Zbl 07088855
[25] Tarski, A.: A Decision Method for Elementary Algebra and Geometry. RAND Corporation, Santa Monica, California (1948). MR 0028796 | Zbl 0035.00602
[26] Zhang, Y. M., Kovacevic, R.: Robust control of interval plants: A time domain method. IEE Proc., Control Theory Appl. 144 (1997), 347-353. DOI 10.1049/ip-cta:19971170 | Zbl 0885.93040
Search
Partner of
