| Title:
|
Complexity of computing interval matrix powers for special classes of matrices (English) |
| Author:
|
Hartman, David |
| Author:
|
Hladík, Milan |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
65 |
| Issue:
|
5 |
| Year:
|
2020 |
| Pages:
|
645-663 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
matrix power |
| Keyword:
|
interval matrix |
| Keyword:
|
interval computations |
| Keyword:
|
NP-hardness |
| MSC:
|
15Bxx |
| MSC:
|
65G40 |
| idZBL:
|
07285950 |
| idMR:
|
MR4160786 |
| DOI:
|
10.21136/AM.2020.0379-19 |
| . |
| Date available:
|
2020-09-23T13:50:17Z |
| Last updated:
|
2022-11-07 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148370 |
| . |
| Reference:
|
[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 . Zbl 1162.93025, MR 2375210 |
| Reference:
|
[2] Buck, R. C.: Partition of space.Am. Math. Mon. 50 (1943), 541-544 \99999DOI99999 10.1080/00029890.1943.11991447 . Zbl 0061.30609, MR 0009119 |
| Reference:
|
[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 . Zbl 06984073, MR 3240473 |
| Reference:
|
[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. Zbl 0900.03055, MR 1634190, 10.1007/978-3-7091-9459-1_4 |
| Reference:
|
[5] Edelsbrunner, H., Guibas, L. J.: Topologically sweeping an arrangement.J. Comput. Syst. Sci. 38 (1989), 165-194. Zbl 0676.68013, MR 0990055, 10.1016/0022-0000(89)90038-X |
| Reference:
|
[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. Zbl 1311.65033, MR 3929639, 10.1007/978-1-4614-5131-0_19 |
| Reference:
|
[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 |
| Reference:
|
[8] Goldsztejn, A., Neumaier, A.: On the exponentiation of interval matrices.Reliab. Comput. 20 (2014), 53-72. MR 3268402 |
| Reference:
|
[9] Hansen, E. R.: Sharpness in interval computations.Reliab. Comput. 3 (1997), 17-29. Zbl 0881.65032, MR 1614399, 10.1023/A:1009917818868 |
| Reference:
|
[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. Zbl 1354.65081, MR 3516767, 10.1007/978-3-319-31769-4_9 |
| Reference:
|
[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. Zbl 07007507, MR 3962259, 10.13001/1081-3810.3749 |
| Reference:
|
[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. |
| Reference:
|
[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. 10.1007/978-3-030-31041-7_16 |
| Reference:
|
[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. |
| Reference:
|
[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. 10.1145/1066677.1067007 |
| Reference:
|
[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). Zbl 0945.68077, MR 1491092, 10.1007/978-1-4757-2793-7 |
| Reference:
|
[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 |
| Reference:
|
[18] Mayer, G.: Interval Analysis and Automatic Result Verification.De Gruyter Studies in Mathematics 65. De Gruyter, Berlin (2017). Zbl 1373.65036, MR 3726854, 10.1515/9783110499469 |
| Reference:
|
[19] Moore, R. E., Kearfott, R. B., Cloud, M. J.: Introduction to Interval Analysis.SIAM, Philadelphia (2009). Zbl 1168.65002, MR 2482682, 10.1137/1.9780898717716 |
| Reference:
|
[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. MR 0960775, 10.1109/31.7598 |
| Reference:
|
[21] Poljak, S., Rohn, J.: Checking robust nonsingularity is NP-hard.Math. Control Signals Syst. 6 (1993), 1-9. Zbl 0780.93027, MR 1358057, 10.1007/BF01213466 |
| Reference:
|
[22] Rohn, J.: Computing the norm $\|A\|_{\infty,1}$ is NP-hard.Linear Multilinear Algebra 47 (2000), 195-204. Zbl 0964.65049, MR 1785027, 10.1080/03081080008818644 |
| Reference:
|
[23] Skalna, I.: Parametric Interval Algebraic Systems.Studies in Computational Intelligence 766. Springer, Cham (2018). Zbl 06999249, MR 3852878, 10.1007/978-3-319-75187-0 |
| Reference:
|
[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. Zbl 07088855, MR 3946064, 10.1002/nla.2229 |
| Reference:
|
[25] Tarski, A.: A Decision Method for Elementary Algebra and Geometry.RAND Corporation, Santa Monica, California (1948). Zbl 0035.00602, MR 0028796 |
| Reference:
|
[26] Zhang, Y. M., Kovacevic, R.: Robust control of interval plants: A time domain method.IEE Proc., Control Theory Appl. 144 (1997), 347-353. Zbl 0885.93040, 10.1049/ip-cta:19971170 |
| . |
